【数据结构-字符串 四】【字符串识别】字符串转为整数、比较版本号

废话不多说，喊一句号子鼓励自己：程序员永不失业，程序员走向架构！本篇Blog的主题是【字符串转换】，使用【字符串】这个基本的数据结构来实现，这个高频题的站点是：CodeTop，筛选条件为：目标公司+最近一年+出现频率排序，由高到低的去牛客TOP101去找，只有两个地方都出现过才做这道题（CodeTop本身汇聚了LeetCode的来源），确保刷的题都是高频要面试考的题。

# 比较版本号【MID】
还是字符串识别的一道题，比较版本号

题干

题目如下

解题思路

原题解地址，比较两个版本号大小，版本号由修订号组成，中间使用’.'分隔，越靠近字符串前边，修订号的优先级越大。当v1 > v2时返回 1，当v1 < v2时返回 -1，相等时返回 0

如样例所示，v1= 1.02.3, v2 = 1.02.2，前两个修订号都相等，v1的第三个修订号大于v2的第三个修订号，因此v1 > v2，返回1。下面来讲解双指针的做法。

我们使用两个指针i和j分别指向两个字符串的开头，然后向后遍历，当遇到小数点’.‘时停下来，并将每个小数点’.'分隔开的修订号解析成数字进行比较，越靠近前边，修订号的优先级越大。根据修订号大小关系，返回相应的数值

// 将一段连续的字符串转换成数字 
while(i < v1.size() && v1[i] != '.') {
   num1 = num1 * 10 + v1[i++] - '0';
}
1
2
3
4

这样做可以直接去前导0，同时将字符串转换成数字也便于比较大小。具体过程如下：

1. 定义两个指针 i和j，初始化i = 0，j = 0。
2. 两个指针分别遍历两个字符串，将每个小数点'.'分隔开的修订号解析成数字，并进行大小比较：
   * 如果 num1 > num2，返回 1；
   * 如果 num1 < num2，返回 -1；
   3、i++，j++，两个指针都后移一步，进行下一轮的修订号解析比较。
   4、如果遍历完两个字符串都没有返回相应结果，说明两个字符串相等，返回0。

时间复杂度分析： 两个字符串各遍历一遍，因此时间复杂度为 O(n+m)O(n + m)O(n+m) ，n和m分别是两个字符串的长度。

代码实现

给出代码实现基本档案

基本数据结构：字符串
辅助数据结构：无
算法：迭代
技巧：双指针

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 比较版本号
     * @param version1 string字符串
     * @param version2 string字符串
     * @return int整型
     */
    public int compare (String version1, String version2) {
        // 1 定义两个指针，分别漫游两个字符串
        int i = 0;
        int j = 0;

        // 2 双重漫游，遇到.的时候比较
        while (i < version1.length() || j < version2.length()) {
            // 2-1 没有遇到.号前获取修订号值
            int num1 = 0;
            int num2 = 0;
            while (i < version1.length() && version1.charAt(i) != '.') {
                num1 = num1 * 10 + version1.charAt(i) - '0';
                i++;
            }
            while (j < version2.length() && version2.charAt(j) != '.') {
                num2 = num2 * 10 + version2.charAt(j) - '0';
                j++;
            }

            // 2-2 获取到完整的一格修订号后比较
            if (num1 > num2) {
                return 1;
            } else if (num1 < num2) {
                return -1;
            }

            // 2-3 相等修订号情况下，继续向前
            i++;
            j++;
        }

        // 3 漫游完全部修订分区后，还是没有返回，证明两个版本号相同
        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

复杂度分析

时间复杂度 O(N+M)，双指针，遍历两个字符串；
空间复杂度 O(1)，借助的常量阶的空间

拓展知识：Integer.MAX_VALUE 和Integer.MIN_VALUE

Integer.MAX_VALUE 和 Integer.MIN_VALUE 是 Java 中的两个常量，它们分别代表了 int 数据类型的最大值和最小值。这两个常量定义在 Java 的 Integer 类中，是 int 数据类型的包装类。

1. Integer.MAX_VALUE：这个常量表示了 int 数据类型的最大可能值，即 2^31 - 1，也就是 2,147,483,647。当你试图存储一个比 Integer.MAX_VALUE 大的值时，会导致溢出。

2. Integer.MIN_VALUE：这个常量表示了 int 数据类型的最小可能值，即 -2^31，也就是 -2,147,483,648。当你试图存储一个比 Integer.MIN_VALUE 更小的值时，同样也会导致溢出。

这些常量通常用于限制或检查 int 类型的变量，以确保它们不会超出范围。这对于处理整数数据非常重要，因为溢出可能导致不正确的计算结果或未定义的行为。