找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 12871|回复: 17
收起左侧

[米群网刷题小分队] [Leetcode] 新题 Compare Version Numbers

  [复制链接]
发表于 12-16-2014 12:28 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-16-2014 02:00 PM 编辑

Compare two version numbers 【i】version1 and 【i】version1.
If 【i】version1 > 【i】version2 return 1, if 【i】version1 < 【i】version2 return -1, otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.
The . character does not represent a decimal point and is used to separate number sequences.
For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

Here is an example of version numbers ordering:

0.1 < 1.1 < 1.2 < 13.37

Credits:
Special thanks to @ts for adding this problem and creating all test cases.


分析: 题目不难,两个点之间的整数(不知道有没有为空的情况,空就认为0),比较它们的大小。数据似乎比较弱,可以转成int。但是我的建议就是不转换。而且最好别用substr这种东西,否则空间应该不是O(1),我的方法时间复杂度O(n)——n是字符串总长度,空间复杂度O(1)。

关键函数  : int give(string &s, int &begin)

从begin开始沿着s走,走到"."或者s的结束点为止,返回走的长度,注意begin也可能变化,这是为了跳过整数开头的0,这些0是无效的。例如"00110.xx"从开头走,end会走到那个'.',而begin会到“110”的第一个字符‘1’,返回的长度是3。如果begin超过了字符串长度,则end = begin,最后返回长度为0。

我们传入的参数是string的引用,并没有复制任何东西,所以空间复杂度O(1)。

接下来就是比较两个字符串begin1, begin2,长度为length1, length2的部分,当然我们可以转化为整数,也可以substr直接比较。我是自己循环比较的,因为没有首0,长度长的肯定大,长度相同的话,再逐个比较。 所以时间复杂度就是最差把两个串分别扫两遍的复杂度(第一遍确定每个begin,length,第二遍是比较),所以是O(n)的。

代码想写简单明了并不容易:

我的代码:

  1. class Solution {
  2. public:
  3.    int give(string &s, int &begin) {
  4.        for (; (begin < s.length()) && (s[begin] == '0'); ++begin)
  5.        ;
  6.        int end = begin;
  7.        for (; (end < s.length()) && (s[end] != '.'); ++end)
  8.        ;
  9.        return end - begin;
  10.    }

  11.     int compareVersion(string version1, string version2) {
  12.         for (int begin1 = 0, begin2 = 0; begin1 < version1.length() || begin2 < version2.length(); ++begin1,++begin2) {
  13.             int length1 = give(version1, begin1), length2 = give(version2, begin2);
  14.             if (length1 < length2) {
  15.                 return -1;
  16.             }
  17.             if (length1 > length2) {
  18.                 return 1;
  19.             }
  20.             for (int i = 0; i < length1; ++i) {
  21.                 if (version1[begin1] < version2[begin2]) {
  22.                     return -1;
  23.                 }
  24.                 if (version1[begin1] > version2[begin2]) {
  25.                     return 1;
  26.                 }
  27.                 ++begin1;
  28.                 ++begin2;
  29.             }
  30.         }
  31.         return 0;
  32.     }
  33. };
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

17

主题

0

精华

232

积分

高级会员

Rank: 3Rank: 3

积分
232
发表于 12-28-2014 09:25 AM | 显示全部楼层
干扰码丧心病狂,想复制代码收着都不行,呵呵,这网站
回复 支持 1 反对 0

使用道具 举报

发表于 12-16-2014 01:36 PM | 显示全部楼层
Great post and elegant codes!!!
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 反对

使用道具 举报

47

主题

2

精华

379

积分

高级会员

Rank: 3Rank: 3

积分
379
发表于 12-16-2014 08:22 PM | 显示全部楼层
曹博做的比我的好得多。。。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表