算法题：Find the latest version - 未名空间MITBBS历史存档

算法题：Find the latest version# JobHunting - 待字闺中

s*u2013-10-04 07:10

1 楼

http://www.careercup.com/question?id=5673258271637504
Find the latest version of released software. For e.g1. 2 and 2.2.. latest
is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
as string in above format.
一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
int/double/
下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
每一位都要做一次快排，也就是O(knlogn)
另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一
位只要O(n)，总共O(kn)。但坏处是，比如其中一位是很大的数，那么开的空间就要很
大，其实time cost也不再是O(n),而是O(max)。
我想了一下，既然只是要求最大版本。那就从第一位开始，每一位遍历。找到最大值之
后，将所有该位不存在，或者该位小于最大值的那个vector删除，或者用bool数组标记
下false。从左到右走一遍，最后只剩下一个vector。
不知道是不是最优解法。
还有一个问题就是怎么把比如3.12.4.7转换为vector {3,12,4,7}
我想的办法是将所有'.'改成‘ ’，然后用while(stringstream >> num)
估计有更好的办法？基础不扎实，所以一会用用sscanf,一会用用stringstream，都用
不好。

q*c2013-10-04 07:10

2 楼

这太容易了吧，就是找最大值啊，用通常的字符串比较函数就行。n 算法

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

s*g2013-10-04 07:10

3 楼

字符串不行。比如9.0和10.0

【在 q*c 的大作中提到】

: 这太容易了吧，就是找最大值啊，用通常的字符串比较函数就行。n 算法

U*K2013-10-04 07:10

4 楼

拆成数组比如[2，1，3], 数组求和，和最大的最新

L*12013-10-04 07:10

5 楼

1.将所有的版本号转为x.xxx的格式，即保留第一个小数点，其它全部取消
2.用Double.valueOf转换
3.比大小
用的是JAVA.
O(n)

s*i2013-10-04 07:10

6 楼

2.12 将会小于2.2

[发表自未名空间手机版 - m.mitbbs.com]

【在 L**********1 的大作中提到】

: 1.将所有的版本号转为x.xxx的格式，即保留第一个小数点，其它全部取消
: 2.用Double.valueOf转换
: 3.比大小
: 用的是JAVA.
: O(n)

y*82013-10-04 07:10

7 楼

3.1.12 和3.2.1？

【在 U**K 的大作中提到】

: 拆成数组比如[2，1，3], 数组求和，和最大的最新

s*82013-10-04 07:10

8 楼

这个一直有争议的是3.1到底比3.02高还是低？

t*r2013-10-04 07:10

9 楼

java 用 comparable.

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

s*w2013-10-04 07:10

10 楼

正好昨天也在用　istringstream parse 字符串，共享一下
string line;
while(getline(cin,line)) {
istringstream iss(line);
vector vi;
int tmp;
do {
iss >> tmp;
iss.ignore(256,'.');
if(iss.good())
vi.push_back(tmp);
} while(iss.good());
}

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

q*c2013-10-04 07:10

11 楼

那就分段比字符串，比的时候长度相等就比大学，长度不等那么长的大。首字符为零去
掉。

【在 s********g 的大作中提到】

: 字符串不行。比如9.0和10.0

s*u2013-10-04 07:10

12 楼

这明显不对吧。比如3.4和3.2.23，后者长度更长，但前者更新。
似乎转换成数组是逃不掉的了

【在 q*c 的大作中提到】

: 那就分段比字符串，比的时候长度相等就比大学，长度不等那么长的大。首字符为零去
: 掉。

f*n2013-10-04 07:10

13 楼

1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

f*n2013-10-04 07:10

14 楼

1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

f*n2013-10-04 07:10

15 楼

1. 换成数组
2. qsort(),然后自己编一个函数比较大小

【在 s********u 的大作中提到】

: http://www.careercup.com/question?id=5673258271637504
: Find the latest version of released software. For e.g1. 2 and 2.2.. latest
: is 2.2. eg2: 3.1 and 3.1.3... latest version is 3.1.3... version is passed
: as string in above format.
: 一道面经，感觉还是蛮有意思的。正好复习了下怎么用stringstream把string转换成
: int/double/
: 下面的回复，一种解法是把3.1.3转换成一个数组{3,1,3}，然后对所有数组补0，再依
: 次从右往左对每一位排序（有点像radix sort）但是这样感觉还是比较繁琐，相当于对
: 每一位都要做一次快排，也就是O(knlogn)
: 另一位说用radixsort，就是从右往左，每次做一个bucket sort。这样的好处是，每一

c*y2013-10-04 07:10

16 楼

javascript好像可以直接比较？

m*m2013-10-04 07:10

17 楼

1. 转换成数组应该是逃不了, 那些比较String的函数总是会把3.14当做比3.2更高版本
.
2. java的话用comparator写比较的逻辑

q*c2013-10-04 07:10

18 楼

是每段内比啊，从左到右，第一个不等的决定大小。
不能转换，因为接下来溢出等问题坑爹。

【在 s********u 的大作中提到】

: 这明显不对吧。比如3.4和3.2.23，后者长度更长，但前者更新。
: 似乎转换成数组是逃不掉的了