在本篇文章中，我们将详细解读力扣第165题“比较版本号”。通过学习本篇文章，读者将掌握如何使用多种方法来解决这一问题，并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释和ASCII图解，以便于理解。
问题描述
力扣第165题“比较版本号”描述如下：
给你两个版本号
version1和version2，请你比较它们。版本号由一个或多个修订号组成，各修订号由一个
'.'连接。每个修订号由多位数字组成，可能包含前导零。比较版本号时，请按从左到右的顺序依次比较它们的修订号。
比较规则如下：
- 如果
version1>version2返回1，- 如果
version1<version2返回-1，- 除此之外返回
0。
示例 1:
输入: version1 = "1.01", version2 = "1.001" 输出: 0 解释: 忽略前导零，两版本号是相同的。
示例 2:
输入: version1 = "1.0", version2 = "1.0.0" 输出: 0 解释: 忽略末尾的0，两版本号是相同的。
示例 3:
输入: version1 = "0.1", version2 = "1.1" 输出: -1 解释: version1 < version2
解题思路
方法一：逐个比较
- 初步分析：
- 将版本号字符串通过
'.'分割成修订号列表。 - 逐个比较每个修订号，直到找到不同的修订号或者遍历完所有修订号。
- 步骤：
- 将
version1和version2分别通过'.'分割成修订号列表。 - 使用两个指针逐个比较修订号，如果一个修订号较大，则返回1；如果较小，则返回-1。
- 如果比较完所有修订号仍然相同，则返回0。
代码实现
def compareVersion(version1, version2): v1_parts = version1.split('.') v2_parts = version2.split('.') max_length = max(len(v1_parts), len(v2_parts)) for i in range(max_length): v1 = int(v1_parts[i]) if i < len(v1_parts) else 0 v2 = int(v2_parts[i]) if i < len(v2_parts) else 0 if v1 > v2: return 1 elif v1 < v2: return -1 return 0 # 测试案例 print(compareVersion("1.01", "1.001")) # 输出: 0 print(compareVersion("1.0", "1.0.0")) # 输出: 0 print(compareVersion("0.1", "1.1")) # 输出: -1
ASCII图解
假设输入版本号为 "1.01" 和 "1.001"，图解如下：
版本号1: "1.01" 版本号2: "1.001" 分割后: v1_parts = ["1", "01"] v2_parts = ["1", "001"] 逐个比较: 1 == 1 -> 继续比较 01 == 001 -> 忽略前导零，继续比较 所有修订号相同: 返回 0
方法二：双指针法
- 初步分析：
- 使用双指针法逐个字符比较版本号。
- 当遇到
'.'时，分隔出一个修订号进行比较。
- 步骤：
- 初始化两个指针分别指向
version1和version2的开头。 - 使用两个指针逐个字符遍历版本号，遇到
'.'时将修订号转换为整数进行比较。 - 如果一个修订号较大，则返回1；如果较小，则返回-1。
- 如果比较完所有修订号仍然相同，则返回0。
代码实现
def compareVersion(version1, version2): i, j = 0, 0 n1, n2 = len(version1), len(version2) while i < n1 or j < n2: num1, num2 = 0, 0 while i < n1 and version1[i] != '.': num1 = num1 * 10 + int(version1[i]) i += 1 while j < n2 and version2[j] != '.': num2 = num2 * 10 + int(version2[j]) j += 1 if num1 > num2: return 1 elif num1 < num2: return -1 i += 1 j += 1 return 0 # 测试案例 print(compareVersion("1.01", "1.001")) # 输出: 0 print(compareVersion("1.0", "1.0.0")) # 输出: 0 print(compareVersion("0.1", "1.1")) # 输出: -1
ASCII图解
假设输入版本号为 "1.0" 和 "1.0.0"，图解如下：
版本号1: "1.0" 版本号2: "1.0.0" 初始化指针: i = 0, j = 0 逐个字符比较: num1 = 1, num2 = 1 i = 2, j = 2 继续比较: num1 = 0, num2 = 0 i = 3, j = 4 所有修订号相同: 返回 0
复杂度分析
- 时间复杂度：
- 逐个比较法：O(n + m)，其中 n 和 m 分别是
version1和version2的长度。 - 双指针法：O(n + m)，其中 n 和 m 分别是
version1和version2的长度。
- 空间复杂度：
- 逐个比较法：O(n + m)，用于存储分割后的修订号列表。
- 双指针法：O(1)，只使用了常数空间来存储指针和变量。
模拟面试问答
问题 1：你能描述一下如何解决这个问题的思路吗？
回答：我们需要比较两个版本号，确定它们的大小关系。可以通过将版本号分割成修订号列表，逐个比较修订号，直到找到不同的修订号。如果所有修订号都相同，则版本号相等。另一种方法是使用双指针逐个字符遍历版本号，分隔出修订号进行比较。
问题 2：为什么要忽略版本号中的前导零？
回答：前导零对修订号的大小没有影响。例如，“01” 和 “001” 都表示相同的修订号1。因此在比较时需要忽略前导零，以确保比较结果正确。
问题 3：你的算法如何处理不同长度的版本号？
回答：在逐个比较修订号时，如果一个版本号的修订号数量较少，我们将缺少的部分视为0。例如，比较 “1.0” 和 “1.0.0” 时，末尾的修订号0被忽略，视为相同。
问题 4：你能解释一下双指针法的工作原理吗？
回答：双指针法通过初始化两个指针分别指向 version1 和 version2 的开头。逐个字符遍历版本号，遇到 '.' 时将当前修订号转换为整数进行比较。如果一个修订号较大，则返回1；如果较小，则返回-1。继续遍历直到比较完所有修订号。
问题 5：在代码中如何确保处理完所有修订号？
回答：在双指针法中，我们使用两个指针分别遍历 version1 和 version2，确保在任意一个版本号未遍历完之前继续比较。每次比较后，移动指针到下一个修订号的开头，直到遍历完所有修订号。
问题 6：如何处理版本号为空的情况？
回答：如果版本号为空，则视为版本号为0。例如，比较 “” 和 “1.0” 时，空版本号视为0，因此 “” < “1.0”，返回-1。
问题 7：你能举例说明在面试中如何回答优化问题吗？
回答：在面试中，如果面试官问到如何优化算法，我会首先分析当前算法的瓶颈，如时间复杂度和空间复杂度，然后提出优化方案。例如，对于比较版本号问题，我会提到使用双指针法来减少空间复杂度，解释其原理和优势，并根据具体情况提供代码实现和复杂度分析。
问题 8：你的代码是如何处理多个 '.' 分隔符的？
回答：代码通过 split('.') 方法将版本号字符串分割成修订号列表，逐个比较每个修订号，确保处理多个 '.' 分隔符。双指针法逐个字符遍历版本号，遇到 '.' 时分隔出修订号进行比较，确保正确处理多个分隔符。
问题 9：你如何验证代码的正确性？
回答：通过多个测试案例验证代码的正确性，包括正常情况和边界情况。例如，比较相同版本号、不同长度的版本号、前导零情况等。确保代码在各种情况下都能正确运行。
问题 10：你能解释一下版本号比较的重要性吗？
回答：版本号比较在软件更新和管理中非常重要。例如，确定两个软件版本的先后关系，确保用户获得最新版本的软件。版本号比较还用于自动化部署和升级，确保系统中运行的是兼容且最新的版本。
总结
本文详细解读了力扣第165题“比较版本号”，通过逐个比较和双指针法两种方法，高效地解决了这一问题，并提供了详细的ASCII图解和模拟面试问答。希望读者通过本文的学习，能够在力扣刷题的过程中更加得心应手。
参考资料
- 《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- 力扣官方题解
欢迎关注微信公众号 数据分析螺丝钉
