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。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程理解

正则表达式(二):断言

上面的例子反映了一个明显的正则匹配规则:贪婪匹配,即在符合正则表达式规则的情况下,总会匹配尽量多内容。 如果想使得正则表达式按最小内容匹配,只需要在次数元符号...

63820
来自专栏小文博客

写出这个数——《C语言代码笔记》

29120
来自专栏我是业余自学C/C++的

redis3.0.7_sds.c_sdsnewlen()

16040
来自专栏Android干货

浅谈Base64编码算法

41260
来自专栏积累沉淀

JavaScript匿名函数与闭包

匿名函数就是没有名字的函数,闭包是可访问一个函数作用域里变量的函数。 一.匿名函数 //普通函数 function box() {//函数名是box retur...

20550
来自专栏C/C++基础

C/C++数组与指针详解

数组大小(元素个数)一般在编译时决定,也有少部分编译器可以运行时动态决定数组大小,比如icpc(Intel C++编译器)。

15620
来自专栏个人随笔

房上的猫:while循环与do-while循环,debug的调试运用

一.循环结构  1.循环不是无休止进行的,满足一定条件的时候循环才会继续,称为"循环条件",循环条件不满足的时候,循环退出  2.循环结构是反复进行相同的或类似...

408110
来自专栏racaljk

关于C++函数返回局部对象的详细分析

以前一直挺好奇的,C++是怎么在函数内返回一个局部对象的。因为按照我之前的想法,函数返回一个基本类型的值是通过存放到ecx实现的(关于浮点不了解),但是局部对象...

50110
来自专栏mwangblog

python函数

17820
来自专栏Golang语言社区

Go语言基本的语法和内置数据类型初探

Go令牌 Go程序包括各种令牌和令牌可以是一个关键字,一个标识符,常量,字符串文字或符号。例如,下面的Go语句由六个令牌: fmt.Println("Hell...

29150

扫码关注云+社区

领取腾讯云代金券