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

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

明确目标题后，附上题目链接，后期可以依据解题思路反复快速练习，题目按照题干的基本数据结构分类，且每个分类的第一篇必定是对基础数据结构的介绍。

字符串转为整数【MID】

字符串和栈结合的一道题

题干

题目如下
在这里插入图片描述
一些用例的示例：

解题思路

原题解地址，在这里依据题意罗列几个要点：

根据示例 1，需要去掉前导空格；
根据示例 2，需要判断第 1 个字符为 + 和 - 的情况，因此，可以设计一个变量 sign，初始化的时候为 1，如果遇到 - ，将 sign 修正为 -1；
判断是否是数字，可以使用字符的 ASCII 码数值进行比较，即 0 <= c <= '9'；
根据示例 3 ，在遇到第 1 个不是数字的字符的情况下，转换停止，退出循环；
根据示例 5，如果转换以后的数字超过了 int 类型的范围，需要截取。这里不能将结果 res 变量设计为 long 类型，注意：由于输入的字符串转换以后也有可能超过 long 类型，因此需要在循环内部就判断是否越界，只要越界就退出循环，这样也可以减少不必要的计算；由于涉及下标访问，因此全程需要考虑数组下标是否越界的情况。

代码实现

给出代码实现基本档案

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

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param n int整型 the n* @return int整型*/public int myAtoi(String s) {// 1 初始化下标，并删除下标前的空格int index = 0;while (index < s.length() && s.charAt(index) == ' ') {index++;}// 极端情况下，字符串全为空格，此时返回0if (index == s.length()) {return 0;}// 2 判断第一个非空格字符的符号，获取整数的符号,无论正负，均继续向前探索int sign = 1;if (s.charAt(index) == '-') {sign = -1;index++;} else if (s.charAt(index) == '+') {index++;}// 3 循环判断，进行数字读取int result = 0;while (index < s.length()) {// 3-1 如果为非数字，则终止if (s.charAt(index) < '0' || s.charAt(index) > '9') {break;}// 3-2 如果为数字则需要判断增加数字后是否会溢出int curNum = s.charAt(index) - '0';// 如果当前值*10后大于上届，或当前值*10等于上届但本级数字大于上届的取模，则证明本层遍历完还是大于上届if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < curNum)) {return sign > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;}// 3-3 如果未越界则正常存值,每次新读入值后上一个结果就要扩大10倍result = result * 10 + curNum;index++;}return sign * result;}}

复杂度分析

时间复杂度 O(N)，一次遍历 s；
空间复杂度 O(1)，借助的常量阶的空间

比较版本号【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';
}

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

定义两个指针 i和j，初始化i = 0，j = 0。
两个指针分别遍历两个字符串，将每个小数点'.'分隔开的修订号解析成数字，并进行大小比较：
* 如果 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;}
}

复杂度分析

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

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

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

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