语义化版本比较--实现

本文最后更新于：2021年4月21日 上午

概览：语义化版本比较的实现。

语义化版本比较

传入两个形如v1.2.3的字符串，比较两个语义化版本的大小。如果version1小于version2，返回-1；如果version1大于version2，返回1。如果二者相等，返回0。

注意，如果传入的字符串形如x，则其等价于x.0.0。 如果传入的字符串形如x.y，则其等价于x.y.0。

源于 蓝信移动 2面 2021/04/17

面试反思

  • 在读懂题目之前，不要乱说话！
  • 我甚至直接说去比较字符串的大小，尴尬😅。

处理字符串

先要确保两个字符串是否匹配，即是否符合语义化版本的要求。

  • 使用C++11的正则表达式库来确保其匹配。
  • 使用regex_match函数，正则：(v|V)[0-9\.]*[0-9]。
1
2
3
4
5
6
7
regex e("(v|V)([0-9\.])*[0-9]");

bool match1 = regex_match(str1,e);//要求完全匹配
bool match2 = regex_match(str2,e);//要求完全匹配

cout << (match1 ? "str1 matched" : "str1 Not matched") << endl;
cout << (match2 ? "str2 matched" : "str2 Not matched") < endl;

提取字符串中的数字

依旧使用正则表达式来进行提取。

  • 使用sregex_iterator 构造迭代器，其内部会自动调用regex_search函数，从而得到所有的匹配结果。
  • 正则：[0-9]+
1
2
regex re("[0-9]+");
sregex_iterator it(str1.begin(), str1.end(), re);

比较 - 思路1 直接比较

直接就去比较两个数组的元素，当两个数组元素不相等的时候，对于超出的部分，要和0做比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int compareVersion(vector<int> &nums1, vector<int> &nums2) {
	int len1 = nums1.size();
	int len2 = nums2.size();

	int i = 0, j = 0;
	for (; i < len1 && j < len2; i++, j++) {
		if (nums1[i] < nums2[j]) {
			return -1;
		}
		else if (nums1[i] > nums2[j]) {
			return 1;
		}
	}

	//循环结束，i < len1 或者 j < len2
	if (len1 == len2) {
		return 0;
	}

	bool flag = false;
	while (i < len1) {
		if (nums1[i] != 0) {
			return 1;
		}
		else {
			i++;
			flag = true;
		}
	}
	if (flag && i == len1) {
		return 0;
	}

	while (j < len2) {
		if (nums2[j] != 0) {
			return -1;
		}
		else {
			j++;
			flag = true;
		}
	}
	if (flag && j == len2) {
		return 0;
	}
}

比较 - 思路2 填充后比较

两个数组的长度可能是不相等的，可以将较短的数组填充0，达到相等的长度，然后再去比较，这样代码写起来比较简单些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int compareVersion1(vector<int> &nums1, vector<int> &nums2) {
	int len1 = nums1.size();
	int len2 = nums2.size();

	int maxlen = max(len1, len2);
    
    while (len1 < maxlen) {
        nums1.push_back(0);
        len1++;
    }
    while (len2 < maxlen) {
        nums2.push_back(0);
        len2++;
    }

	for (int k = 0; k < maxlen; k++) {
		if (nums1[k] > nums2[k]) {
			return 1;
		}
		else if (nums1[k] < nums2[k]) {
			return -1;
		}
	}
	return 0;
}

完整代码

折叠/查看代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <regex>
#include <iterator>
#include <sstream>

using namespace std;

int compareVersion(vector<int> &nums1, vector<int> &nums2) {
    int len1 = nums1.size();
    int len2 = nums2.size();

    int i = 0, j = 0;
    for (; i < len1 && j < len2; i++, j++) {
        if (nums1[i] < nums2[j]) {
            return -1;
        }
        else if (nums1[i] > nums2[j]) {
            return 1;
        }
    }

    //循环结束，i < len1 或者 j < len2
    if (len1 == len2) {
        return 0;
    }

    bool flag = false;
    while (i < len1) {
        if (nums1[i] != 0) {
            return 1;
        }
        else {
            i++;
            flag = true;
        }
    }
    if (flag && i == len1) {
        return 0;
    }

    while (j < len2) {
        if (nums2[j] != 0) {
            return -1;
        }
        else {
            j++;
            flag = true;
        }
    }
    if (flag && j == len2) {
        return 0;
    }
}

int compareVersion1(vector<int> &nums1, vector<int> &nums2) {
    int len1 = nums1.size();
    int len2 = nums2.size();

    int maxlen = max(len1, len2);

    while (len1 < maxlen) {
        nums1.push_back(0);
        len1++;
    }
    while (len2 < maxlen) {
        nums2.push_back(0);
        len2++;
    }

    for (int k = 0; k < maxlen; k++) {
        if (nums1[k] > nums2[k]) {
            return 1;
        }
        else if (nums1[k] < nums2[k]) {
            return -1;
        }
    }
    return 0;
}

int main()
{
    stringstream ss;
    vector<int> nums1, nums2;
    int tmp;

    while (1) {
        cout << "please cin 2 str:" << endl;;
        string str1,str2;
        cin >> str1>>str2;
        regex e("(v|V)([0-9\.])*([0-9])");
        //smatch m;

        bool match1 = regex_match(str1,e);//要求完全匹配
        bool match2 = regex_match(str2,e);//要求完全匹配

        cout << (match1 ? "str1 matched" : "str1 Not matched") << endl;
        cout << (match2 ? "str2 matched" : "str2 Not matched") << endl;

        //匹配之后，将匹配到的数据保存到数组中

        ss.clear();
        nums1.clear();
        nums2.clear();

        if (match1) {
            regex re("[0-9]+");
            sregex_iterator it(str1.begin(), str1.end(), re), end_it;
            for (; it != end_it; it++) {
                ss << it->str();
                ss >> tmp;
                ss.clear();
                nums1.push_back(tmp);
            }
        }

        ss.clear();

        if (match2) {
            regex re("[0-9]+");
            sregex_iterator it(str2.begin(), str2.end(), re), end_it;
            for (; it != end_it; it++) {
                ss << it->str();
                ss >> tmp;
                ss.clear();
                nums2.push_back(tmp);
            }
        }

        int result = compareVersion1(nums1,nums2);

        cout << "result: " << result << endl;

    }
}

运行实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
please cin 2 str:
v1.2
v1
str1 matched
str2 matched
result: 1
please cin 2 str:
v1.2.3
v1.2.0
str1 matched
str2 matched
result: 1
please cin 2 str:
v1
V2.6
str1 matched
str2 matched
result: -1
please cin 2 str:
v1
v1.0.0.0
str1 matched
str2 matched
result: 0
C/C++
C/C++

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！