网站设置地图,化妆品设计网站,成都网站外包公司,如何自己编写小程序废话不多说#xff0c;喊一句号子鼓励自己#xff1a;程序员永不失业#xff0c;程序员走向架构#xff01;本篇Blog的主题是【字符串转换】#xff0c;使用【字符串】这个基本的数据结构来实现#xff0c;这个高频题的站点是#xff1a;CodeTop#xff0c;筛选条件为喊一句号子鼓励自己程序员永不失业程序员走向架构本篇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 0j 0。两个指针分别遍历两个字符串将每个小数点.分隔开的修订号解析成数字并进行大小比较 * 如果 num1 num2返回 1 * 如果 num1 num2返回 -1 3、ij两个指针都后移一步进行下一轮的修订号解析比较。 4、如果遍历完两个字符串都没有返回相应结果说明两个字符串相等返回0。
时间复杂度分析 两个字符串各遍历一遍因此时间复杂度为 O(nm)O(n m)O(nm) 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(NM)双指针遍历两个字符串 空间复杂度 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 更小的值时同样也会导致溢出。
这些常量通常用于限制或检查 int 类型的变量以确保它们不会超出范围。这对于处理整数数据非常重要因为溢出可能导致不正确的计算结果或未定义的行为。
