力扣 - 剑指 Offer 67. 把字符串转换成整数

题目

思路1

根据题意，要解决这题，首先要判断的条件有：
- 不包括首位空格
- 第一位必须为：+、-、数字三者其一，否则不合法
- 数字必须连续的，如果遇到非数字，结束判断
- 判断结果要在 \(-2^{31}\)~\((2^{31}-1)\) 之间，如果超过的话，就输出最大值 / 最小值
我们用sign记录符号、res记录每次遍历累加的值、threshold记录阈值（我们阈值取Integer.MAX_VALUE/10，即小了一位数，作用后面再说）、index记录开始的索引。接下来开始解析：
- 首先，我们使用Java的trim方法去除首位空格
- 然后判断第一位的字符是什么，为负号sign就为-1，默认是正号1。同时还要设置开始比遍历的索引index，如果为负号或者显示的正号，我们就设置为1（因为这两个符号都占了一个位置），否则就默认从0开始（这时候不用管是否为数字，这个判断留到下面再去判断）
- 接下来根据前面设置的index，从index开始遍历字符串，判断每一位字符：
  - 如果不为数字则跳出循环；
  - 如果res结果大于阈值（res还没加上当前值，因为如果res已经大于阈值了，不管当前值是多大也没有影响）则说明拼接后的值已经超过了Integer.MAX_VALUE，需要返回整数的最大值；
  - 如果res == threshold，且当前的值也大于7（为什么要大于7呢，因为大于7就说明大于正整数的最大值，前几位一样，那么就比较最后一位嘛），此时再根据符号，直接返回最大值即可。
  - （注意：因为最大正整数和最小负整数不仅仅是符号不一样的区别，将最小负整数去掉符号之后，还是比最大正整数的值还大1。所以这个是如何保证能正确判断呢？主要是在cs[i] > '7'这个地方：这个条件判断了如果res等于最大正整数，此时不是直接返回最大正整数，而是进行拼接，进行下一轮判断，当然，如果是负数的话，达到-2147483647也是进行拼接，如果是-2147483648，那么就会直接返回最大负整数，这也就是为什么c[i]要大于7而不是大于等于‘7了）
- 如果上一步都没超最大值，此时讲当前值拼接到res中即可：res = res*10 + (cs[i] - '0');
- 最后返回res*sign，由sign控制符号

代码

class Solution {

    public int strToInt(String str) {

        char[] cs = str.trim().toCharArray();

        // 非空格的字符长度为0，直接返回0

        if (cs.length == 0) {

            return 0;

        }

        // 符号标志，代表正负号，默认为正

        int sign = 1;

        // 存储结果

        int res = 0;

        // 默认第一位是符号，所以从第二位开始计算，即1

        int index = 1;

        // 阈值

        int threshold = Integer.MAX_VALUE / 10;

        // 判断第一位非空格的的字符

        if (cs[0] == '-') {

            // 负号

            sign = -1;

        } else if (cs[0] != '+') {

            // 如果不是正号的话，我们先默认：第一位是数字、为正数，下面再进行判断

            index = 0;

        }

        // 根据前面的index判断是从第0位还是第1位开始判断

        for (int i = index; i < cs.length; i++) {

            // 不是数字就直接结束

            if (cs[i] < '0' || cs[i] > '9') {

                break;

            }

            // 超出范围

            if (res > threshold || (res == threshold && cs[i] > '7')) {

                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;

            }

            // 进行拼接

            res = res*10 + (cs[i] - '0');

        }

        return sign * res;

    }

}

复杂度分析

时间复杂度：\(O(N)\)，线性遍历数组所需时间为\(O(N)\)
空间复杂度：\(O(N)\)，将字符串转换成字符数组所占用的空间

巴特西

力扣 - 剑指 Offer 67. 把字符串转换成整数

题目

思路1

代码

复杂度分析

最新文章

热门文章