每日一题--比较版本号

题目描述

在许多软件开发和版本管理系统中，版本号用于表示不同的更新或发布。通常版本号由多个修订号组成，这些修订号通过 . 连接。现在给定两个版本号 version1 和 version2，请比较它们的大小，返回以下结果：

• 若 version1 大于 version2，返回 1。
• 若 version1 小于 version2，返回 -1。
• 若二者相等，返回 0。

比较规则

1. 忽略前导零：修订号中可能有前导零，比较时忽略前导零。例如 “0.1” 和 “0.01” 应视为相等。
2. 缺失修订号视为零：如果某个版本号缺少某个修订号，则该修订号视为零。例如 “1.1” 和 “1.1.0” 应视为相等，且 “1.1” 小于 “1.1.1”。
3. 版本号形式：版本号至少包含一个修订号，修订号可能包含多位数字。

9种情况分析

解释

1. 数字字符比较：如果当前字符是数字，则可以通过将字符转换为整数进行比较。
2. 点字符（.）：在版本号中，点字符用于分隔不同的修订号。当遇到点字符时，意味着当前修订号的结束，我们需要比较当前的修订号。
3. 空字符（\0）：当版本号中的字符指针到达字符串结尾时，表示该版本号结束。在此情况下，缺失的修订号应视为 0，因此进行比较时需要考虑这一点。

示例

解题思路

我们可以使用双指针遍历两个版本号字符串，同时按修订号进行比较。具体步骤如下：

1. 处理前导零：通过整数处理修订号时，自动去除前导零。
2. 缺失修订号处理：如果某个版本号没有对应的修订号，我们将该修订号视为 0。
3. 逐个比较修订号：从左到右比较修订号，直到找到大小差异或者比较完所有修订号。

实现步骤

1. 双指针遍历版本号：使用两个指针分别指向两个版本号字符串。
2. 提取修订号：当遇到 . 或字符串结束时，表示一个修订号结束，比较两个修订号的大小。
3. 忽略前导零：在提取修订号时直接计算其值。
4. 处理缺失修订号：如果一个版本号比另一个短，则视缺失的修订号为 0。

代码实现

复杂版本

其实就是按照9种情况讨论：

int compare(char* version1, char* version2 ) {
    int i = 0, j = 0;

    int temp1 = 0;
    int temp2 = 0;
    while (version1[i] != '\0' || version2[j] != '\0') {
        
        if ((version2[j] != '.'&& version2[j] != '\0')&& (version1[i] != '.'&&version1[i] != '\0')) {
            temp1 = temp1 * 10 + (version1[i] - '0');
            i++;
            temp2 = temp2 * 10 + (version2[j] - '0');
            j++;
        } else if ((version2[j] == '.' || version2[j] == '\0') && (version1[i] != '.'&&version1[i] != '\0')) {
            temp1 = temp1 * 10 + (version1[i] - '0');
            i++;
        } else if ((version1[i] == '.' || version1[i] == '\0') && (version2[j] != '.'&&version2[j] != '\0')) {
            temp2 = temp2 * 10 + (version2[j] - '0');
            j++; 
           
        } else if ((version2[j] == '.' || version2[j] == '\0') && (version1[i] == '.' ||
                   version1[i] == '\0')) {
            if (temp1 > temp2)
                return 1;
            if (temp1 < temp2)
                return -1;
            else {
                temp1 = 0;
                temp2 = 0;
                if (version1[i] == '.')i++;
                if (version2[j] == '.')j++;
            }

        } else break;
      
    }
    if (temp1 > temp2){
        
         return 1;}
       
    else if (temp1 < temp2)
        return -1;
    else  return 0;
    // write code here

}

简化版本

其实完全没必要，明明很简单的思路，自己非搞得极度麻烦。

int compare(char* version1, char* version2) {
    int i = 0, j = 0;
    int temp1 = 0, temp2 = 0;
    
    while (version1[i] != '\0' || version2[j] != '\0') {
        // 处理版本号1和版本号2的当前修订号
        temp1 = 0; temp2 = 0;
        
        // 处理version1和version2的当前修订号
        while (version1[i] != '.' && version1[i] != '\0') {
            temp1 = temp1 * 10 + (version1[i] - '0');
            i++;
        }
        
        while (version2[j] != '.' && version2[j] != '\0') {
            temp2 = temp2 * 10 + (version2[j] - '0');
            j++;
        }
        
        // 比较修订号
        if (temp1 > temp2) {
            return 1; // version1 > version2
        }
        if (temp1 < temp2) {
            return -1; // version1 < version2
        }
        
        // 处理 '.' 位置
        if (version1[i] == '.') i++;
        if (version2[j] == '.') j++;
    }
    
    return 0; // version1 == version2
}

代码讲解

1. 初始化：定义两个指针 i 和 j，分别指向 version1 和 version2 的当前位置。temp1 和 temp2 用来存储当前修订号的值。

2. 遍历修订号：

   • 使用两个 while 循环分别提取两个版本号中的当前修订号。每次遇到 . 或字符串结束时，就结束当前修订号的提取。

3. 比较修订号：当提取出两个修订号时，比较它们的大小：

   • 如果 temp1 > temp2，返回 1，表示 version1 更大。
   • 如果 temp1 < temp2，返回 -1，表示 version1 更小。
   • 如果相等，继续处理下一个修订号。

4. 跳过点号：如果当前字符是 .，跳过它，继续处理下一个修订号。

5. 结束条件：当遍历完两个版本号时，如果没有发现大小差异，说明它们相等，返回 0。

复杂度分析

• 时间复杂度：每次我们都在字符串上按修订号进行遍历，因此时间复杂度是 O(n)，其中 n 是两个版本号字符串的最大长度。
• 空间复杂度：只有几个整型变量用于存储索引和临时值，空间复杂度是 O(1)。