LeetCode刷题【165】比较版本号

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 '.' 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

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

 

示例 1：

输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，"01" 和 "001" 都表示相同的整数 "1"

示例 2：

输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有指定下标为 2 的修订号，即视为 "0"

示例 3：

输入：version1 = "0.1", version2 = "1.1"
输出：-1
解释：version1 中下标为 0 的修订号是 "0"，version2 中下标为 0 的修订号是 "1" 。0 < 1，所以 version1 < version2

示例 4：

输入：version1 = "1.0.1", version2 = "1"
输出：1

示例 5：

输入：version1 = "7.5.2.4", version2 = "7.5.3"
输出：-1

 

提示：

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

题解

9月1日的每日一题。好像没啥复杂的。工作中也会有机会用到的一个案例，比如app更新版本号判断，不过一般而言，工作中的版本号格式应该都是固定的，不会出现两个要比较的版本号的分隔符个数不一样的情况。

class Solution {
    public int compareVersion(String version1, String version2) {
        List<Integer> arr1 = versionToArr(version1);
        List<Integer> arr2 = versionToArr(version2);

        int res = 0;
        int i;
        for (i = 0; i < arr1.size() & i < arr2.size(); i++) {
            if (arr1.get(i) < arr2.get(i)){
                return -1;
            }
            if (arr1.get(i) > arr2.get(i)){
                return 1;
            }
        }
        if (arr1.size() < arr2.size()){
            int i1 = i;
            while (i1<arr2.size()){
                if (arr2.get(i1)>0){
                    return -1;
                }
                i1++;
            }
        }
        if (arr1.size() > arr2.size()){
            int i2 = i;
            while (i2<arr1.size()){
                if (arr1.get(i2)>0){
                    return 1;
                }
                i2++;
            }
        }
        return res;
    }

    private List<Integer> versionToArr(String version){
        List<Integer> arr = new ArrayList<>();
        String[] arrStr = version.split("\\.");
        for (String s : arrStr) {
            arr.add(Integer.parseInt(s));
        }
        return arr;
    }

}

有一点小问题就是，下面的while判断一开始没有写，导致提交后

测试用例:"1.0"，"1.0.0"

这个用例过不去，所以这边其实应该有另一个思路：较短版本号的后面不存在的分隔符的部分可以假设为也存在，但是值为零，这样两个版本号的长度（指分隔符的个数）就可以对齐。

好了，有了上面的解法的思路（即，实际是按照分隔符对应比较每段实际数值的大小），和这里不存在的分割断当做0来处理的认知之后，我们可以试试更加简洁的解法。

这里需要结合另一个知识点，字符串转换为数字的方法，从字符串的高位开始遍历相加，每次相加对之前的结果乘以10，这样可以得到实际的数值。即字符串“123”可以按照

((((0+1)*10)+2)*10)+3

这样的方式求和得到

class Solution {
    public int compareVersion(String version1, String version2){
        int index1 = 0,index2 = 0,num1,num2;
        while (index1< version1.length() || index2 < version2.length()){
            num1=0;
            num2=0;
            //一直往后取，取到分隔符的点。注意越界
            while (index1< version1.length() && version1.charAt(index1)!='.'){
                num1 += num1*10 + (version1.charAt(index1)-'0');
                index1++;
            }
            //同num1的
            while (index2 < version2.length() && version2.charAt(index2)!='.'){
                num2 += num2*10 + (version2.charAt(index2)-'0');
                index2++;
            }
            if (num1<num2){
                return -1;
            }
            if (num2< num1){
                return 1;
            }

            //往后进一位，当前位置为分隔符，假如没有越界的话，越界也没关系，上面的求和之前有判断了越界
            index2++;
            index1++;
        }
        return 0;
    }

}

这样是不是一下子就出来了