leetcode 165
才一周没刷leetcode,手就生了,这个题目不难,但是完全AC还是挺费劲的。
题目描述:
Compare two version numbers version1 and version2.
If version1 > version2 return 1, if version1 < 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 < 12.21
题目不难,就是比较字符串。但是有几点需要注意。
1.各大博客上po出的代码现在都无法AC,原因在于测试case修正了。比如一些算法直接将自连个子版本号分割后对齐转化为int型,现在有个case直接导致这里发生溢出。
2.可能有多个子版本号,这里要考虑全面。
代码如下:
class Solution {
public:
int compareVersion(string version1, string version2) { string v1_front, v1_back, v2_front, v2_back; vector<string> v1;
vector<string> v2; splitString(version1, v1);
splitString(version2, v2); vector<unsigned long long> v1_long;
vector<unsigned long long> v2_long; for (auto i = v1.begin(); i != v1.end(); i ++) {
if (i->size() != )
v1_long.push_back(stoull(*i));
else
v1_long.push_back(); } for (auto i = v2.begin(); i != v2.end(); i ++) {
if (i->size() != )
v2_long.push_back(stoull(*i));
else
v2_long.push_back(); } while (v1_long.size() < v2_long.size()) {
v1_long.push_back();
} while (v1_long.size() > v2_long.size()) {
v2_long.push_back();
} for (int i = ; i < v1_long.size(); i ++) {
if (v1_long[i] != v2_long[i]) {
return v1_long[i] > v2_long[i] ? : -;
}
}
return ; } void abandonFrontZeros(string & s)
{
int pos = ;
while (s[pos] == '' && pos < s.size()) {
++pos;
}
s = s.substr(pos, s.size() - pos);
} void splitString(string & s, vector<string> & v)
{
vector<int> dot_pos;
for (int i = ; i < s.size(); i ++) {
if (s[i] == '.') {
dot_pos.push_back(i);
}
} int b = ;
for (int i = ; i < dot_pos.size(); i ++) {
v.push_back(s.substr(b, dot_pos[i] - b));
b = dot_pos[i] + ;
} v.push_back(s.substr(b, s.size() - b)); for (auto i = v.begin(); i != v.end(); i ++) {
abandonFrontZeros(*i);
}
} };
感慨一些:C++11的一些新特性还是很方便的。string类的自带接口如substr()很方便。还有stoi(), stoull(), stod()等模板函数也很方便。
最新文章
- iOS10 UI教程视图和子视图的可见性
- 【Android】利用服务Service创建标题栏通知
- HDU 5675 ztr loves math
- Flume研究心得
- VMProtect修复导入表的插件
- C语言生产随机数的方法
- FileMode枚举
- 使用AOP记录应用调用链开销
- prometheus如何使用blackbox-exporter来获取k8s的网络性能
- Scrum立会报告+燃尽图(十二月九日总第四十次):视频剪辑与用户反馈
- mybatis pagehelper多数据源配置的坑
- 系统架构--分布式计算系统spark学习(三)
- ubuntu下安装memcached和PHP的memcache扩展
- Asp.net 基于Cookie简易的权限判断
- AutoEncoder and DenoiseAutoEncoder
- 学习笔记 第十三章 使用CSS3新布局
- JavaScript面向对象实现
- 分布式数据库DDM Sidecar模式负载均衡
- JavaScript面试题链接汇总
- hadoop集群zookeeper迁移