题目描述

在链接里面,不单独发

解题思路

大体思路上: 是把每两个”.”之间的数字取出来进行比较,如果有大小关系就直接返回,否则继续比较;
细节上: 每次都要判断是否到字符串的末尾,并且取出数字后要把下标加1(跳过”.”)

注意:

    1. 可以使用atoi进行字符串到数字的转换,但是需要用 .c_str() 把字符串转换为字符数组
    2. 数字可能会超过int范围,虽然这个题没有超过

代码 时间复杂度O(n + m),空间复杂度 O(1)

class Solution {
public:
    int compareVersion(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        int i = 0, j = 0;
        while (i < n || j < m) {
            int x = i, y = j, sum1 = 0, sum2 = 0;
            while (x < n && str1[x] != '.') sum1 = sum1 * 10 + str1[x++] - '0';
            while (y < m && str2[y] != '.') sum2 = sum2 * 10 + str2[y++] - '0';
            if (sum1 > sum2) return 1;
            else if (sum1 < sum2) return -1;
            i = x + 1, j = y + 1;
        }
        return 0;
    }
};