提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode高频题8：字符串转换整数 (atoi)

LeetCode转换 字符串 整数 高频 atoi
2023-09-11 14:15:38 时间

LeetCode高频题8：字符串转换整数 (atoi)

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
在这里插入图片描述
基础知识：
【1】LeetCode高频题7：整数反转，除运算，取模运算的魅力

文章目录

题目

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、审题

示例 1：

输入：s = “42”
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步：“42”（当前没有读入字符，因为没有前导空格）
第 2 步：“42”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
第 3 步：“42”（读入 “42”）
解析得到整数 42 。
由于 “42” 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：

输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
第 2 步：" -42"（读入 ‘-’ 字符，所以结果应该是负数）
第 3 步：" -42"（读入 “42”）
解析得到整数 -42 。
由于 “-42” 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：

输入：s = “4193 with words”
输出：4193
解释：
第 1 步：“4193 with words”（当前没有读入字符，因为没有前导空格）
第 2 步：“4193 with words”（当前没有读入字符，因为这里不存在 ‘-’ 或者 ‘+’）
第 3 步：“4193 with words”（读入 “4193”；由于下一个字符不是一个数字，所以读入停止）
解析得到整数 4193 。
由于 “4193” 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成

这种题的核心思想：过滤非法字符，然后拿到合法数字字符串，再转化为数字

本题没啥算法原型，就是一些字符和边界条件的操控，让你训练条件函数的控制

（1）第一步，就是想办法过滤掉那些不需要的字符，得到了一个str是咱们习以为常见到的数字字符串，比如下图
+a，-b，或者a，b啥的
在这里插入图片描述
（2）然后得到（1）的str就是一个真的数字字符串，咱们再将其转化为int数字，越界卡住就行。
本文先看过滤条件

预处理：前面±符号不动，去除s中开头那些个0000，截取数字串，抹掉后面那些非数字字符

（1）str首位置的±保留不动，我们不能丢掉正负数的符号位
（2）从s=1开始，第一个不为0的字符锁定，最后然s指向它，干掉左边前面一堆0000啥的，保留真的数字
（3）e从最尾端开始数，一直往左找，找到最左边那个不是数字的位置。也即是想办法把非数字干掉，好转化
（4）当然s头尾的空格首先要用s.trim()干掉，这是必然的

比如下图中首字符是-，保留
但是接着7之前来了一堆0，让s越过这些0字符，直接去第一个非0字符7那指着
e倒回来看，找到最左边第一个非数字字符的位置_那
substring截取**[s,e)之间的字符串，完成头尾过滤！
在这里插入图片描述
但是要小心
substring截取[s,e)**之间的字符可能就是一个负号了
这还是非法的，咱们先返回负号，待会再来一次合法的过滤函数valid，处理这个状况
在这里插入图片描述
本次头尾过滤的代码，手撕一波，返回一个字符串

    //复习：
    //预处理：前面+-符号不动，去除s中开头那些个0000，截取数字串，抹掉后面那些非数字字符
    public static String removeHeadZeroTailNoNum(String s){
        //（4）当然s头尾的空格首先要用s.trim()干掉，这是必然的
        s = s.trim();
        if (s.compareTo("") == 0 || s.length() == 0) return "";
        int N = s.length();//长
        //（1）str首位置的+-保留不动，我们不能丢掉正负数的符号位
        boolean flag = s.charAt(0) == '+' || s.charAt(0) == '-' ? true : false;
        int start = flag ? 1 : 0;//0是符号位？
        //（2）从s=1开始，第一个不为0的字符锁定，最后然s指向它，干掉左边前面一堆0000啥的，保留真的数字
        for(; start < N; start++){
            //沿途找第一个非0字符，start指着它
            if (s.charAt(start) != '0' ) break;
        }

        int end = -1;
        //（3）e从最尾端开始数，一直往左找，找到最左边那个不是数字的位置。也即是想办法把非数字干掉，好转化
        for (int i = N - 1; i >= (flag ? 1 : 0); i--) {//倒回来，看看0位置是符号位，就不要找了
            if (s.charAt(i) < '0' || s.charAt(i) > '9') end = i;//非数字记忆i，最次到0位置，或1
        }
        
        //返回啥结果呢？负号位带上
        String ans = flag ? String.valueOf(s.charAt(0)) : "";//有符号位先拿上
        //再截取start和end之间的，end一直是-1，表示N之前都OK
        end = end == -1 ? N : end;//还-1，就末尾
        ans += s.substring(start, end);

        return ans;
    }

测试：

String s1 = removeHeadZeroTailNoNum("+0007321_hhljg");
        System.out.println(s1);

+7321

再测试：

s1 = removeHeadZeroTailNoNum("+_007321_hhljg");
        System.out.println(s1);

+

再测试

s1 = removeHeadZeroTailNoNum("_007321_hhljg");
        System.out.println(s1);

结果是一个空串“”

上面过滤完的字符串竟然还不合格？再核查是不是真的数字字符串

比如
（1）s首位置竟然不是±，而且也不是数字，显然不合法的【就是上面举例的特殊情况，只剩一个负号了】，比如空串
（2）s如果只有一个±，也不是数字，不合法
（3）s首尾确实也是±，但是后续还要非数字字符串【其实上面已经过滤了，不会再出现这个情况】
在这里插入图片描述

    //在上面首尾清楚的情况下，再次过滤
    public static boolean isValidReview(String s){
        //（1）s首位置竟然不是+-，而且也不是数字，显然不合法的【就是上面举例的特殊情况，只剩一个负号了】，比如空串
        if (s.charAt(0) != '+' || s.charAt(0) != '-' ||
                s.charAt(0) < '0' || s.charAt(0) > '9') return false;
        //（2）s如果只有一个+-，也不是数字，不合法
        if ((s.charAt(0) != '+' || s.charAt(0) != '-') && s.length() == 1) return false;
        //（3）s首尾确实也是+-，但是后续还要非数字字符串【其实上面已经过滤了，不会再出现这个情况】
        //（1）（2）过了一定首字符是+-，或者正数
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(0) < '0' || s.charAt(0) > '9') return false;
        }

        //都没事
        return true;
    }

测试：

        boolean val = isValidReview("+");
        System.out.println(val);
        val = isValidReview("_111");
        System.out.println(val);
        val = isValidReview("-1_11");
        System.out.println(val);

false
false
false

过滤好了的str就是真的带正负号的数字字符了，转int数字，越界返回边界值

咱们的想法，是将正数转负数【当负数处理】，0和负数不管
然后操作这个字符串

正数当负数啥意思？，就是比如遇到’1’
用的时候用’0’-'1’就是-1的意思

见到正数，把它转负数，因为负数范围大，表示不会越界的

就像下面的正数最大值，可以加符号转正数，能int表示
但是int的负数最大值，加符号，变正数失效了，会溢出的！
懂？
在这里插入图片描述
为啥要转负数？看这个文章
【1】LeetCode高频题7：整数反转，除运算，取模运算的魅力
只有你看懂那的负数是防止越界的判断条件，你才能看懂今天的思想

最终的转化流程：数字字符串转int

（1）见到正数，将其转负数，标记自己是否是正数isPositive，同时令ans=0；
（2）从i从左往右，每个位置的数字a，拿出来，每次让ans×10+a=ans
（3）中途判断，只要ans越界，根据isPositive来看，如果是负数，则返回系统最小值，如果是正数，返回系统最大值
（4）注意，万一你传入的是系统最大值+1的那个2147483678这个字符串，由于（1）加了符号-2147483678，中途它不会越界的
但是实际上它是正数，一定会越界，也就是ans=-2147483678且最开始isPositive=true，则仍然认为ans是越界的，返回系统最大值——这里要小心的

手撕代码：

    //过滤好了的str就是真的带正负号的数字字符了，转int数字，越界返回边界值
    public static int strToNumReview(String s){
        if (s.compareTo("") == 0 || s.length() == 0) return 0;
        s = removeHeadZeroTailNoNum(s);//过滤
        if (s.compareTo("") == 0 || s.length() == 0) return 0;
        if (isNotValidReview(s)) return 0;

        //（1）见到正数，将其转负数，标记自己是否是正数isPositive，同时令ans=0；
        boolean isPostive = s.charAt(0) != '-' ? true : false;
        int ans = 0;
        int a = 0;//中间取数字a
        //准备负数越界的条件
        int m = Integer.MIN_VALUE / 10;
        int o = Integer.MIN_VALUE % 10;
        //（2）从i从左往右，每个位置的数字a，拿出来，每次让ans×10+a=ans
        for (int i = (s.charAt(0) == '-' || s.charAt(0) == '+') ? 1 : 0; i < s.length(); i++) {
            //去字符，转负数数字——这里就是转负数的意思
            a = '0' - s.charAt(i);
            //判越界//（3）中途判断，只要ans越界，根据isPositive来看，
            //        // 如果是负数，则返回系统最小值，如果是正数，返回系统最大值
            if (ans < m || (ans == m && a % 10 < o))
                return isPostive ? Integer.MAX_VALUE:Integer.MIN_VALUE;//得看s是正数负数，边界卡住了
            //然后就可以正常转数字了
            ans = ans * 10 + a;//转数字，不断从高位拿a放数字高位
        }

        //（4）注意，万一你传入的是系统最大值+1的那个2147483678这个字符串，
        // 由于（1）加了符号-2147483678，中途它不会越界的
        //但是实际上它是正数，一定会越界，也就是ans=-2147483678且最开始isPositive=true，
        // 则仍然认为ans是越界的，返回系统最大值——这里要小心的
        if (isPostive && ans == Integer.MIN_VALUE) return Integer.MAX_VALUE;

        return isPostive ? -ans : ans;//正数就要添加负号，负数直接返回
    }

测试：

        System.out.println(solution.myAtoi2("42"));
        System.out.println(strToNumReview("42"));
        System.out.println(strToNumReview("_42"));
        System.out.println(strToNumReview("-42"));
        System.out.println(strToNumReview("-42_"));
        System.out.println(strToNumReview("-000042_"));

42
42
0
-42
-42
-42

最重要的就是卡清楚边界条件，然后利用正数转负数，将字符一个一个抠出来，加到ans中
中途越界返回边界
最后检查是否s正数的情况下，最后ans又等于系统最小，这样的话，s正数仍然是越界的
用LeetCode测试

在这里插入图片描述
牛逼吧！！！

总结

提示：重要经验：

1）过滤不符合条件的那些字符，然后以常见的数字字符串转数字
2）最重要的就是卡清楚边界条件，然后利用正数转负数，将字符一个一个抠出来，加到ans中，中途越界返回边界，最后检查是否s正数的情况下，最后ans又等于系统最小，这样的话，s正数仍然是越界的
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。

相关文章