165. 比较版本号
题目描述
输入两个版本号字符串 version1 和 version2。版本号由若干段修订号组成，段与段之间用 '.' 隔开。每段修订号按整数取值，前导零不影响大小。
比较时从左往右逐段比较对应的修订号。如果某个版本号段数较少，缺的段一律当作 0。
version1 较大时返回 1，较小时返回 -1，两者相等时返回 0。
示例 1
输入：version1 = "1.2", version2 = "1.10" 输出：-1
解释：第二段分别是 2 和 10，2 < 10，所以 version1 更小。
示例 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 <= 500version1和version2只含数字和'.'。version1和version2都是合法的版本号。- 每一段修订号都能用 32 位整数表示。
解题思路：双指针逐段解析
用两个指针 i、j 分别扫描两个字符串。每一轮各自读入一个修订号：遇到数字就用 x = x*10 + d 累加，遇到 . 或末尾停下。前导零在累加中自然消失；一方已经读完时，它的内层循环不执行，得到 0，正好对应“缺少视为 0”。两数不等立即返回结果，否则两个指针都跨过 . 进入下一轮。
为什么正确
每轮开始时，两个版本号在之前已读的所有修订号都两两相等；i、j 分别指向各自下一个修订号的开头（或已越过末尾）。
复杂度分析
时间 O(n + m)，每个字符只读一次；额外空间 O(1)，不需要 split。
易错点
不要按字符串字典序比较修订号（"10" < "2"）；也不要在一方读完时直接结束，另一方后面全是 0 时两者相等。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
i, j = 0, 0
n, m = len(version1), len(version2)
while i < n or j < m:
x = 0
while i < n and version1[i] != '.':
x = x * 10 + int(version1[i])
i += 1
y = 0
while j < m and version2[j] != '.':
y = y * 10 + int(version2[j])
j += 1
if x != y:
return 1 if x > y else -1
i, j = i + 1, j + 1
return 0class Solution {
public int compareVersion(String version1, String version2) {
int i = 0, j = 0;
int n = version1.length(), m = version2.length();
while (i < n || j < m) {
long x = 0;
while (i < n && version1.charAt(i) != '.') {
x = x * 10 + (version1.charAt(i) - '0');
i++;
}
long y = 0;
while (j < m && version2.charAt(j) != '.') {
y = y * 10 + (version2.charAt(j) - '0');
j++;
}
if (x != y) {
return x > y ? 1 : -1;
}
i++; j++;
}
return 0;
}
}class Solution {
public:
int compareVersion(string version1, string version2) {
int i = 0, j = 0;
int n = version1.size(), m = version2.size();
while (i < n || j < m) {
long long x = 0;
while (i < n && version1[i] != '.') {
x = x * 10 + (version1[i] - '0');
i++;
}
long long y = 0;
while (j < m && version2[j] != '.') {
y = y * 10 + (version2[j] - '0');
j++;
}
if (x != y) {
return x > y ? 1 : -1;
}
i++; j++;
}
return 0;
}
};func compareVersion(version1 string, version2 string) int {
i, j := 0, 0
n, m := len(version1), len(version2)
for i < n || j < m {
x := 0
for i < n && version1[i] != '.' {
x = x*10 + int(version1[i]-'0')
i++
}
y := 0
for j < m && version2[j] != '.' {
y = y*10 + int(version2[j]-'0')
j++
}
if x != y {
if x > y {
return 1
}
return -1
}
i, j = i+1, j+1
}
return 0
}var compareVersion = function(version1, version2) {
let i = 0, j = 0;
const n = version1.length, m = version2.length;
while (i < n || j < m) {
let x = 0;
while (i < n && version1[i] !== '.') {
x = x * 10 + Number(version1[i]);
i++;
}
let y = 0;
while (j < m && version2[j] !== '.') {
y = y * 10 + Number(version2[j]);
j++;
}
if (x !== y) {
return x > y ? 1 : -1;
}
i++; j++;
}
return 0;
};function compareVersion(version1: string, version2: string): number {
let i = 0, j = 0;
const n = version1.length, m = version2.length;
while (i < n || j < m) {
let x = 0;
while (i < n && version1[i] !== '.') {
x = x * 10 + Number(version1[i]);
i++;
}
let y = 0;
while (j < m && version2[j] !== '.') {
y = y * 10 + Number(version2[j]);
j++;
}
if (x !== y) {
return x > y ? 1 : -1;
}
i++; j++;
}
return 0;
}其他解法
两种方法都是 O(n+m) 时间；字符串分割先切分再比较，双指针边解析边比较，只用 O(1) 空间。
解法 2：字符串分割 时间 O(n+m)，空间 O(n+m)
按 '.' 把两个版本号切成修订号数组。从左到右比较同一位置的修订号，转成整数后比较，缺少的一侧按 0 计。第一个不相等的位置决定结果。
借助库函数分割和转整数，代码最直观。要保存分割结果，需要 O(n+m) 额外空间。
class Solution:
def compareVersion(self, version1: str, version2: str) -> int:
a = version1.split('.')
b = version2.split('.')
for i in range(max(len(a), len(b))):
x = int(a[i]) if i < len(a) else 0
y = int(b[i]) if i < len(b) else 0
if x != y:
return 1 if x > y else -1
return 0class Solution {
public int compareVersion(String version1, String version2) {
String[] a = version1.split("\\."), b = version2.split("\\.");
int len = Math.max(a.length, b.length);
for (int i = 0; i < len; i++) {
int x = i < a.length ? Integer.parseInt(a[i]) : 0;
int y = i < b.length ? Integer.parseInt(b[i]) : 0;
if (x != y) return x > y ? 1 : -1;
}
return 0;
}
}class Solution {
vector<int> parse(const string& v) {
vector<int> res;
stringstream ss(v);
string part;
while (getline(ss, part, '.')) res.push_back(stoi(part));
return res;
}
public:
int compareVersion(string version1, string version2) {
vector<int> a = parse(version1), b = parse(version2);
int len = max(a.size(), b.size());
for (int i = 0; i < len; i++) {
int x = i < (int)a.size() ? a[i] : 0;
int y = i < (int)b.size() ? b[i] : 0;
if (x != y) return x > y ? 1 : -1;
}
return 0;
}
};func compareVersion(version1 string, version2 string) int {
a, b := strings.Split(version1, "."), strings.Split(version2, ".")
for i := 0; i < len(a) || i < len(b); i++ {
x, y := 0, 0
if i < len(a) {
x, _ = strconv.Atoi(a[i])
}
if i < len(b) {
y, _ = strconv.Atoi(b[i])
}
if x != y {
if x > y {
return 1
}
return -1
}
}
return 0
}var compareVersion = function(version1, version2) {
const a = version1.split('.'), b = version2.split('.');
const len = Math.max(a.length, b.length);
for (let i = 0; i < len; i++) {
const x = i < a.length ? parseInt(a[i], 10) : 0;
const y = i < b.length ? parseInt(b[i], 10) : 0;
if (x !== y) return x > y ? 1 : -1;
}
return 0;
};function compareVersion(version1: string, version2: string): number {
const a = version1.split('.'), b = version2.split('.');
const len = Math.max(a.length, b.length);
for (let i = 0; i < len; i++) {
const x = i < a.length ? parseInt(a[i], 10) : 0;
const y = i < b.length ? parseInt(b[i], 10) : 0;
if (x !== y) return x > y ? 1 : -1;
}
return 0;
};