Leetcode-169 – Compares version numbers

[Blog link]

The path to learning at 🐔

The nuggets home page

[B].

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. The revision number is 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:

Return 1 if version1 > version2, -1 if version1 < version2, and 0 otherwise.

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 and version2 contain only numbers and ‘.’
  • Both version1 and version2 are valid versions
  • All revision numbers for version1 and version2 can be stored in 32-bit integers

Related Topics

  • Double pointer
  • string
  • 👍 👎 0 201

Idea 1: Violence simulation

  • Split the character array and compare from v[0]
public int compareVersion(String version1, String version2) {
    String[] v1 = version1.split("\.");
    String[] v2 = version2.split("\.");
    for (int i = 0; i < v1.length && i < v2.length; i++) {
        if (Integer.parseInt(v1[i]) == Integer.parseInt(v2[i])) {
            continue;
        }
        return Integer.parseInt(v1[i]) > Integer.parseInt(v2[i]) ? 1 : -1;
    }
    if (v1.length == v2.length) {
        return 0;
    }
    // Long characters need to be compared to see if subsequent values are >0
    int res = 0;
    String[] temp = v1.length > v2.length ? v1 : v2;
    for (int i = Math.min(v2.length, v1.length); i < Math.max(v2.length, v1.length); i++) {
        res += Integer.parseInt(temp[i]);
    }
    return res == 0 ? 0 : v1.length > v2.length ? 1 : -1;
}
Copy the code
  • Time complexity O(n)
  • Space complexity O(n)