“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

1, the title

I give you two version numbers version1 and version2, please compare them.

A version number consists of one or more revision numbers connected by a ‘.’. Each revision number consists of multiple digits that may contain leading zeros. Each version number contains at least one character. Revision numbers are numbered from left to right, with subscripts 0, the leftmost revision number subscript 0, the next revision number subscript 1, and so on. For example, 2.5.33 and 0.1 are valid version numbers.

When comparing version numbers, compare their revision numbers from left to right. When comparing revision numbers, only the integer values after ignoring any leading zeros are compared. That is, revision number 1 is equal to revision number 001. If the version number does not specify a revision number at a subscript, the revision number is treated as 0. For example, version 1.0 is less than version 1.1 because they have the same revision number with subscript 0, and the revision number with subscript 1 is 0 and 1, respectively, with 0 < 1.

The return rule is as follows:

  • ifversion1 > version2return1.
  • if version1 < version2return- 1.
  • Otherwise return0.

Example 1:

Input: version1 = "1.01", version2 = "1.001" Output: 0 Explanation: Ignore leading zeros, "01" and "001" both represent the same integer "1"Copy the code

Example 2:

Input: version1 = "1.0", version2 = "1.0.0" Output: 0Copy the code

Example 3:

Input: version1 = "0.1", version2 = "1.1" Output: -1 Description: In version1, the revision number with subscript 0 is "0"; in version2, the revision number with subscript 0 is "1". 0 < 1, so version1 < version2Copy the code

Example 4:

Input: version1 = "1.0.1", version2 = "1" Output: 1Copy the code

Example 5:

Input: version1 = "7.5.2.4", version2 = "7.5.3" Output: -1Copy the code

Tip:

  • 1 <= version1.length, version2.length <= 500
  • version1 和version2Contains only numbers and'. '
  • version1 和 version2Both are valid version numbers
  • version1 和 version2All revision numbers can be stored in32 An integer 中

2, train of thought

O(Max (n,m))O(Max (n,m))O(Max (n,m))

Compare the size of two version numbers. The version numbers consist of revision numbers separated by ‘.’. The closer the version numbers are to the front of the string, the higher the priority of the revision numbers. Return 1 if v1 > v2, -1 if v1 < v2, and 0 if v1 is equal.

Sample:

As shown in the example, v1= 1.02.3, v2 = 1.02.2, the first two revision numbers are equal, the third revision number of V1 is greater than the third revision number of v2, so v1 > v2, return 1. Here’s how to do double Pointers.

We use two Pointers I and j to point to the beginning of each string, then traverse backwards, stopping when we encounter a decimal point ‘.’ and parse the revision numbers separated by each decimal point ‘.’ into numbers for comparison. The closer we get to the front, the higher priority the revision number takes. Returns the corresponding value based on the revision number size relationship.

Implementation details:

// Convert a contiguous string to a number
while(i < v1.size() && v1[i] ! ='. ') num1 = num1 * 10 + v1[i++] - '0';
Copy the code

This can be done by leading 0 directly, while converting strings to numbers makes it easier to compare sizes.

The specific process is as follows:

  • 1. Define two PointersiandjInitialization,i = 0.j = 0.
  • 2. The two Pointers traverse the two strings separately, placing each decimal point'. 'The separated revision numbers are parsed into numbers and compared in size:
    • ifnum1 > num2To return to1;
    • ifnum1 < num2To return to- 1;
  • 3,i++.j++, both Pointers move back one step for the next round of revision number parsing comparison.
  • 4. If no result is returned after traversing two strings, the two strings are equal0.

Time complexity analysis: Two strings are traversed once, so the time complexity is O(Max (n,m))O(Max (n,m))O(Max (n,m)), where n and m are the length of two strings respectively.

C++ code

class Solution {
public:
    int compareVersion(string v1, string v2) {
        int i = 0, j = 0;
        while(i < v1.size() || j < v2.size())
        {
            int num1 = 0, num2 = 0;
            while(i < v1.size() && v1[i] ! ='. ') num1 = num1 * 10 + v1[i++] - '0';
            while(j < v2.size() && v2[j] ! ='. ') num2 = num2 * 10 + v2[j++] - '0';
            if(num1 > num2) return 1;
            else if( num1 < num2) return - 1;
            i++,j++;
        }
        return 0; }};Copy the code

4. Java code

class Solution {
    public int compareVersion(String v1, String v2) {
        int i = 0, j = 0;
        int n = v1.length(), m = v2.length(); 
        while(i < n || j < m)
        {
            int num1 = 0, num2 = 0;
            while(i < n && v1.charAt(i) ! ='. ') num1 = num1 * 10 + v1.charAt(i++) - '0';
            while(j < m && v2.charAt(j) ! ='. ') num2 = num2 * 10 + v2.charAt(j++) - '0';
            if(num1 > num2) return 1;
            else if( num1 < num2) return -1;
            i++; j++;
        }
        return 0; }}Copy the code

Original link: 165. Compare version numbers