跳至主要內容

165. 比较版本号

165. 比较版本号

🟠   🔖  双指针 字符串  🔗 力扣open in new window LeetCodeopen in new window

题目

Given two version strings , version1 and version2, compare them. A version string consists of revisions separated by dots '.'. The value of the revision is its integer conversion ignoring leading zeros.

To compare version strings, compare their revision values in left-to-right order. If one of the version strings has fewer revisions, treat the missing revision values as 0.

Return the following:

  • If version1 < version2, return -1.
  • If version1 > version2, return 1.
  • Otherwise, return 0.

Example 1:

Input: version1 = "1.2", version2 = "1.10"

Output: -1

Explanation:

version1's second revision is "2" and version2's second revision is "10": 2 < 10, so version1 < version2.

Example 2:

Input: version1 = "1.01", version2 = "1.001"

Output: 0

Explanation:

Ignoring leading zeroes, both "01" and "001" represent the same integer "1".

Example 3:

Input: version1 = "1.0", version2 = "1.0.0.0"

Output: 0

Explanation:

version1 has less revisions, which means every missing revision are treated as "0".

Constraints:

  • 1 <= version1.length, version2.length <= 500
  • version1 and version2 only contain digits and '.'.
  • version1 and version2 are valid version numbers.
  • All the given revisions in version1 and version2 can be stored in a 32-bit integer.

题目大意

给你两个 版本号字符串 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 位整数 中

解题思路

  1. 初始化指针和辅助变量：

    • 定义指针 i 和 j 分别指向 version1 和 version2 的当前位置。
    • 定义 x1 和 x2 用于存储当前部分的数值。

  2. 逐部分比较：

    • 用 while 循环读取两个版本号的当前部分，直到遇到 . 或字符串末尾。
    • 将每个字符转换为数字，并累积计算当前部分的值。
    • 比较当前部分的值 x1 和 x2：
      • 如果 x1 < x2，返回 -1。
      • 如果 x1 > x2，返回 1。

  3. 继续下一部分：

    • 重置 x1 和 x2 为 0，并移动指针 i 和 j 到下一个部分。

  4. 处理不同长度的版本号：

    • 即使 i 或 j 到达末尾，另一个版本号仍可能有剩余部分（例如：1.0 和 1.0.0）。
    • 在这种情况下，将剩余部分视为 0 继续比较。

  5. 返回结果：

    • 如果所有部分都相等，返回 0。

复杂度分析

  • 时间复杂度：O(max(n1, n2))，其中 n1 和 n2 分别是 version1 和 version2 的长度，遍历两个版本号的所有字符。
  • 空间复杂度：O(1)，仅使用了常数级别的额外空间。

代码

/**
 * @param {string} version1
 * @param {string} version2
 * @return {number}
 */
var compareVersion = function (version1, version2) {
	const n1 = version1.length,
		n2 = version2.length;
	let x1 = 0,
		x2 = 0;

	for (let i = 0, j = 0; i < n1 || j < n2; i++, j++) {
		// 读取 version1 的下一段版本号
		while (i < n1 && version1[i] !== '.') {
			x1 = 10 * x1 + Number(version1[i++]);
		}
		// 读取 version2 的下一段版本号
		while (j < n2 && version2[j] !== '.') {
			x2 = 10 * x2 + Number(version2[j++]);
		}

		// 比较两个版本号
		if (x1 < x2) return -1;
		if (x1 > x2) return 1;

		// 重置
		x1 = 0;
		x2 = 0;
	}

	return 0;
};