【题目】
Compare two version numbersversion1andversion1.
Ifversion1>version2return 1, ifversion1<version2return -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
【分析】
类似于split的方法把字符串解析, 然后再比较。
(1)将两个字符串version1和version2进行分割,因为可能会出现这样的测试用例"1.0.1",有多个点。
(2)容器vector存储按照"."分割之后的数字。
(3)然后依次进行比较。
【代码】
/**------------------------------------
* 日期:2015-02-02
* 作者:SJF0115
* 题目: 165.Compare Version Numbers
* 网址:https://oj.leetcode.com/problems/compare-version-numbers/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int compareVersion(string version1, string version2) {
int size1 = version1.size();
int size2 = version2.size();
vector<int> v1;
vector<int> v2;
// 解析version1
int sum = 0;
for(int i = 0;i < size1;++i){
if(version1[i] == '.'){
v1.push_back(sum);
sum = 0;
}//if
else{
sum = sum * 10 + version1[i] - '0';
}//else
}//for
v1.push_back(sum);
// 解析version2
sum = 0;
for(int i = 0;i < size2;++i){
if(version2[i] == '.'){
v2.push_back(sum);
sum = 0;
}//if
else{
sum = sum * 10 + version2[i] - '0';
}//else
}//for
v2.push_back(sum);
// 比较
int count1 = v1.size();
int count2 = v2.size();
int num1,num2;
for(int i = 0,j = 0;i < count1 || j < count2;++i,++j){
num1 = i < count1 ? v1[i] : 0;
num2 = j < count2 ? v2[j] : 0;
if(num1 > num2){
return 1;
}//if
else if(num1 < num2){
return -1;
}//else
}//for
return 0;
}
};
int main(){
Solution s;
string str1("1.1");
//string str1("13.27.24");
string str2("1.1");
int result = s.compareVersion(str1,str2);
// 输出
cout<<result<<endl;
return 0;
}
【思路二】
思路二是对思路一的优化,思路一中,必须把version1,version2都解析完全才能比较。
例如:version1 = "13.27.23" version2 = "13.28.25"
思路一中23和25都会遍历到,这其实对结果没有什么影响了,因为前面的27和28已经决定了哪个版本的大小了,因此我们可以不必要解析后面的字符串。
基于这样的思路我们边解析边比较,一旦有结果便停止解析。
【代码二】
/**------------------------------------
* 日期:2015-02-02
* 作者:SJF0115
* 题目: 165.Compare Version Numbers
* 网址:https://oj.leetcode.com/problems/compare-version-numbers/
* 结果:AC
* 来源:LeetCode
* 博客:
---------------------------------------**/
class Solution {
public:
int compareVersion(string version1, string version2) {
int size1 = version1.size();
int size2 = version2.size();
// 解析version
int sum1,sum2,i,j;
for(i = 0,j = 0;i < size1 || j < size2;++i,++j){
// version1
sum1 = 0;
while(i < size1 && version1[i] != '.'){
sum1 = sum1 * 10 + version1[i] - '0';
++i;
}//while
// version2
sum2 = 0;
while(j < size2 && version2[j] != '.'){
sum2 = sum2 * 10 + version2[j] - '0';
++j;
}//while
// compare
if(sum1 > sum2){
return 1;
}//if
else if(sum1 < sum2){
return -1;
}//else
}//for
return 0;
}
};
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 后端.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
Leetcode101.zip
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
刷leetcode总结.md
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
My Solutions to Leetcode problems. All solutions support C
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
LeetCode888. 公平的糖果棒交换888. 公平的糖果棒交换解题思路:哈希表法第一次遍历 A\B 计算二者的糖果差值 diff,同时以 B糖果值建立哈希