跳转至

165. 比较版本号

题目描述

给你两个 版本号字符串 version1 和 version2 ，请你比较它们。版本号由被点 '.' 分开的修订号组成。修订号的值 是它 转换为整数 并忽略前导零。

比较版本号时，请按 从左到右的顺序 依次比较它们的修订号。如果其中一个版本字符串的修订号较少，则将缺失的修订号视为 0。

返回规则如下：

  • 如果 version1 < version2 返回 -1，
  • 如果 version1 > version2 返回 1，
  • 除此之外返回 0。

 

示例 1：

输入：version1 = "1.2", version2 = "1.10"

输出：-1

解释：

version1 的第二个修订号为 "2"，version2 的第二个修订号为 "10"：2 < 10，所以 version1 < version2。

示例 2：

输入：version1 = "1.01", version2 = "1.001"

输出：0

解释：

忽略前导零，"01" 和 "001" 都代表相同的整数 "1"。

示例 3：

输入：version1 = "1.0", version2 = "1.0.0.0"

输出：0

解释：

version1 有更少的修订号，每个缺失的修订号按 "0" 处理。

 

提示：

  • 1 <= version1.length, version2.length <= 500
  • version1 和 version2 仅包含数字和 '.'
  • version1 和 version2 都是 有效版本号
  • version1 和 version2 的所有修订号都可以存储在 32 位整数 中

解法

方法一：双指针

同时遍历两个字符串，用两个指针 \(i\) 和 \(j\) 分别指向两个字符串的当前位置，初始时 \(i = j = 0\)。

每次取出两个字符串中对应的修订号，记为 \(a\) 和 \(b\)，比较 \(a\) 和 \(b\) 的大小，如果 \(a \lt b\)，则返回 \(-1\)；如果 \(a \gt b\)，则返回 \(1\)；如果 \(a = b\)，则继续比较下一对修订号。

时间复杂度 \(O(\max(m, n))\)，空间复杂度 \(O(1)\)。其中 \(m\) 和 \(n\) 分别是两个字符串的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def compareVersion(self, version1: str, version2: str) -> int:
        m, n = len(version1), len(version2)
        i = j = 0
        while i < m or j < n:
            a = b = 0
            while i < m and version1[i] != '.':
                a = a * 10 + int(version1[i])
                i += 1
            while j < n and version2[j] != '.':
                b = b * 10 + int(version2[j])
                j += 1
            if a != b:
                return -1 if a < b else 1
            i, j = i + 1, j + 1
        return 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int compareVersion(String version1, String version2) {
        int m = version1.length(), n = version2.length();
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1.charAt(i) != '.') {
                a = a * 10 + (version1.charAt(i++) - '0');
            }
            while (j < n && version2.charAt(j) != '.') {
                b = b * 10 + (version2.charAt(j++) - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int compareVersion(string version1, string version2) {
        int m = version1.size(), n = version2.size();
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1[i] != '.') {
                a = a * 10 + (version1[i++] - '0');
            }
            while (j < n && version2[j] != '.') {
                b = b * 10 + (version2[j++] - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func compareVersion(version1 string, version2 string) int {
    m, n := len(version1), len(version2)
    for i, j := 0, 0; i < m || j < n; i, j = i+1, j+1 {
        var a, b int
        for i < m && version1[i] != '.' {
            a = a*10 + int(version1[i]-'0')
            i++
        }
        for j < n && version2[j] != '.' {
            b = b*10 + int(version2[j]-'0')
            j++
        }
        if a < b {
            return -1
        }
        if a > b {
            return 1
        }
    }
    return 0
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function compareVersion(version1: string, version2: string): number {
    const [m, n] = [version1.length, version2.length];
    let [i, j] = [0, 0];
    while (i < m || j < n) {
        let [a, b] = [0, 0];
        while (i < m && version1[i] !== '.') {
            a = a * 10 + +version1[i];
            i++;
        }
        while (j < n && version2[j] !== '.') {
            b = b * 10 + +version2[j];
            j++;
        }
        if (a !== b) {
            return a < b ? -1 : 1;
        }
        i++;
        j++;
    }
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
impl Solution {
    pub fn compare_version(version1: String, version2: String) -> i32 {
        let (bytes1, bytes2) = (version1.as_bytes(), version2.as_bytes());
        let (m, n) = (bytes1.len(), bytes2.len());
        let (mut i, mut j) = (0, 0);

        while i < m || j < n {
            let mut a = 0;
            let mut b = 0;

            while i < m && bytes1[i] != b'.' {
                a = a * 10 + (bytes1[i] - b'0') as i32;
                i += 1;
            }
            while j < n && bytes2[j] != b'.' {
                b = b * 10 + (bytes2[j] - b'0') as i32;
                j += 1;
            }

            if a != b {
                return if a < b { -1 } else { 1 };
            }

            i += 1;
            j += 1;
        }

        0
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
public class Solution {
    public int CompareVersion(string version1, string version2) {
        int m = version1.Length, n = version2.Length;
        for (int i = 0, j = 0; i < m || j < n; ++i, ++j) {
            int a = 0, b = 0;
            while (i < m && version1[i] != '.') {
                a = a * 10 + (version1[i++] - '0');
            }
            while (j < n && version2[j] != '.') {
                b = b * 10 + (version2[j++] - '0');
            }
            if (a != b) {
                return a < b ? -1 : 1;
            }
        }
        return 0;
    }
}

评论