s********u 发帖数: 1109 | 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*c 发帖数: 9453 | 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********g 发帖数: 60 | 3 字符串不行。比如9.0和10.0
【在 q*c 的大作中提到】 : 这太容易了吧,就是找最大值啊,用通常的字符串比较函数就行。n 算法
|
U**K 发帖数: 58 | 4 拆成数组比如[2,1,3], 数组求和,和最大的最新 |
L**********1 发帖数: 797 | 5 1.将所有的版本号转为x.xxx的格式,即保留第一个小数点,其它全部取消
2.用Double.valueOf转换
3.比大小
用的是JAVA.
O(n) |
s*i 发帖数: 5025 | 6 2.12 将会小于2.2
[发表自未名空间手机版 - m.mitbbs.com]
【在 L**********1 的大作中提到】 : 1.将所有的版本号转为x.xxx的格式,即保留第一个小数点,其它全部取消 : 2.用Double.valueOf转换 : 3.比大小 : 用的是JAVA. : O(n)
|
y*******8 发帖数: 2377 | 7 3.1.12 和3.2.1?
【在 U**K 的大作中提到】 : 拆成数组比如[2,1,3], 数组求和,和最大的最新
|
s******8 发帖数: 4192 | 8 这个一直有争议的是3.1到底比3.02高还是低? |
t**********r 发帖数: 2153 | 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*w 发帖数: 729 | 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*c 发帖数: 9453 | 11 那就分段比字符串,比的时候长度相等就比大学,长度不等那么长的大。首字符为零去
掉。
【在 s********g 的大作中提到】 : 字符串不行。比如9.0和10.0
|
s********u 发帖数: 1109 | 12 这明显不对吧。比如3.4和3.2.23,后者长度更长,但前者更新。
似乎转换成数组是逃不掉的了
【在 q*c 的大作中提到】 : 那就分段比字符串,比的时候长度相等就比大学,长度不等那么长的大。首字符为零去 : 掉。
|
f*****n 发帖数: 224 | 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*****n 发帖数: 224 | 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*****n 发帖数: 224 | 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******y 发帖数: 29 | |
m*******m 发帖数: 80 | 17 1. 转换成数组应该是逃不了, 那些比较String的函数总是会把3.14当做比3.2更高版本
.
2. java的话用comparator写比较的逻辑 |
q*c 发帖数: 9453 | 18 是每段内比啊,从左到右,第一个不等的决定大小。
不能转换,因为接下来溢出等问题坑爹。
【在 s********u 的大作中提到】 : 这明显不对吧。比如3.4和3.2.23,后者长度更长,但前者更新。 : 似乎转换成数组是逃不掉的了
|