Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

I. Introduction to the topic

1

Link: LeetCode

2. 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, where 0<1.

Two. Concrete implementation

1. Implementation idea

In fact, in the actual development process, double pointer is also used a lot, so next we see how to do this problem, we can first press the dot (.) If the element in version1 is larger than that in version2, it means that the revision number with subscript 0 of version1 and version2 are the same. Anyway, are they different? Then the results can be obtained by comparing them in sequence.

2. Implementation code

1) Their own way of implementation

public int compareVersion(String version1, String version2) {
    // Split by
    String[] s1 = version1.split("\.");
    String[] s2 = version2.split("\.");
   // Take the longest of the two
    int len = Math.max(s1.length,s2.length);
    int i1 = 0;
    int i2 = 0;
   // Compare elements in sequence by longest traversal
    for(int i=0; i<len; i++){if(s1.length>i && s2.length>i && Integer.valueOf(s1[i])>Integer.valueOf(s2[i])){
            return 1;
        }else if(s1.length>i && s2.length>i && Integer.valueOf(s1[i])<Integer.valueOf(s2[i])){
            return -1;
        }
        if(s1.length>i)
            i1=i1+Integer.valueOf(s1[i]);
        if(s2.length>i)
            i2=i2+Integer.valueOf(s2[i]);
    }
    if(i1>i2)return 1;
    if(i1<i2)return -1;
    return 0;
}
Copy the code

2) How to realize the friend

(Dual pointer)O(n+m) O(n+m) The specific process is as follows:

I = 0; j = 0;

2, two Pointers traverse two strings, parse each revision number separated by the decimal point ‘.’ into a number, and compare the size:

If num1 > num2, return 1;

If num1 < num2, -1 is returned;

3, i++, j++, both Pointers move one step back, the next round of revision number parsing comparison.

If no result is returned, the two strings are equal and 0 is returned.

Code:

3. Running result

3. Think after the question

When I saw this problem, my first thought was to cycle through, but the idea was wrong. Then I went to see my friend’s way of solving the problem and came up with some ideas. Sometimes there is no train of thought can also refer to the practice of topic friends, our ultimate goal is to learn rather than with their own hard kowtows, understanding train of thought, learn its train of thought is also a harvest.