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

题目

剑指 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)\),将字符串转换成字符数组所占用的空间
上一篇:1-1/2+1/3+……精度损失


下一篇:1876 长度为三且各字符不同的子字符串