首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode-165-比较版本号

leetcode-165-比较版本号

作者头像
chenjx85
发布2018-09-29 15:25:14
1K0
发布2018-09-29 15:25:14
举报

题目描述:

比较两个版本号 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。

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-09-17 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目描述:
  • 要完成的函数:
  • 说明:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档