leetcode-165-比较版本号

题目描述：

比较两个版本号 version1 和 version2。
如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1，除此之外返回 0。

你可以假设版本字符串非空，并且只包含数字和 . 字符。

. 字符不代表小数点，而是用于分隔数字序列。

例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。

示例 1:

输入: version1 = "0.1", version2 = "1.1"

输出: -1

示例 2:

输入: version1 = "1.0.1", version2 = "1"

输出: 1

示例 3:

输入: version1 = "7.5.2.4", version2 = "7.5.3"

输出: -1

要完成的函数：

int compareVersion(string version1, string version2)

说明：

1、这道题给定两个字符串，字符串中只含有数字和'.'这个符号，这两个字符串作为版本号，要求判断哪个版本号更大。

如果第一个大于第二个，那么返回1。如果第一个小于第二个，那么返回-1。如果相等返回0。

2、这道题如果用python来做，很容易，split函数按照'.'划分，两个字符串得到多个数字存储在两个list中，把短的list在后面补0直到两个list长度相等。

接着逐个比较list中的元素，得到结论。

但是这道题笔者还是选择了c++来做，思路也是类似的，切分出多个字符串，转成数字，比较数字大小。

一直比较下去，直到两个字符串都没有数字了，或者第一个字符串有数字、第二个字符串没有数字，或者第二个字符串有数字、第一个字符串没有数字。

如果是第一种情况，那么返回0。

如果是第二种情况，我们来看多个例子：

①1.1.2和1.1，那么这个时候第三个数字2大于0，那么返回1。

②1.1.0和1.1，那么第三个数字为0，后面没有数字，那么返回0。

③1.1.0.1和1.1，那么第三个数字为0，继续比较下去，第四个数字为1>0，那么返回1。

如果是第三种情况，同样有多个例子，跟第二种情况类似。

所以我们可以构造出如下代码：（略长，附详解）

    int str2int(string i)//把字符串转为数字，返回得到的数字

    {

        int res=0;

        for(int j=0;j<i.size();j++)

            res=10*res+i[j]-'0';

        return res;

    }

    int compareVersion(string version1, string version2)//要完成的子函数

    {

        if(version1==version2)// 如果相等，直接返回

            return 0;

        int i=0,j=0,s1=version1.size(),s2=version2.size(),start1=0,start2=0,result1,result2;

        while(start1<s1||start2<s2)//start1表示第一个字符串中当前数字从哪里开始，start2同理

        {//只要有一个字符串还有数字，那么就继续比较下去

            if(start1<s1&&start2<s2)//如果两个字符串都有数字

            {

                while(i<s1)//i记录'.'的位置，或者到达字符串最末端i=version1.size()

                {

                    if(version1[i]=='.')

                        break;

                    i++;

                }

                while(j<s2)//j同理，记录'.'的位置或者version2.size()

                {

                    if(version2[j]=='.')

                        break;

                    j++;

                }

                result1=str2int(version1.substr(start1,i-start1));//取出当前子字符串，转化为数字，存储在result1中

                result2=str2int(version2.substr(start2,j-start2));//取出当前子字符串，转化为数字，存储在result2中

                if(result1>result2)//如果第一个大于第二个，那么返回1

                    return 1;

                else if(result1<result2)//如果第一个小于第二个，那么返回-1

                    return -1;

                else//如果当前这两个数字相等，那么继续比较下去

                {

                    start1=i+1;//更新start1的值

                    i=start1;//更新i的值

                    start2=j+1;//更新start2的值

                    j=start2;//更新j的值

                }

            }

            else if(start1<s1)//如果只有第一个字符串还有数字

            {

                while(i<s1)

                {

                    if(version1[i]=='.')

                        break;

                    i++;

                }

                result1=str2int(version1.substr(start1,i-start1));

                if(result1>0)//如果大于0，那么立马返回1，不用再比较了

                    return 1;

                else//如果等于0，那么继续比较下去

                {

                    start1=i+1;

                    i=start1;

                }

            }

            else if(start2<s2)//如果只有第二个字符串有数字

            {

                while(j<s2)

                {

                    if(version2[j]=='.')

                        break;

                    j++;

                }

                result2=str2int(version2.substr(start2,j-start2));

                if(result2>0)//如果大于0，那么停止比较，返回-1

                    return -1;

                else//如果等于0，那么继续比较下去

                {

                    start2=j+1;

                    j=start2;

                }

            }

        }

        return 0;//如果两个字符串都跑完了，都没有比较出结果来，那么这时候必然两个字符串的版本号相等

    }

上述代码实测0ms，beats 100.00% of cpp submissions。

巴特西

leetcode-165-比较版本号

题目描述：

要完成的函数：

说明：

最新文章

热门文章