[数据结构与算法]力扣 8. 字符串转换整数 (atoi)

题目来源：https://leetcode.cn/problems/string-to-integer-atoi/

大致题意：
给一个字符串，将其转为整数

思路

首先考虑规则：

1. 如果字符串有前导空格后者后缀空格，需要去除
2. 如果字符串开头为 -，则对应整数为负数；如果开头为 +，则表示为整数，默认也为整数
3. 遍历字符串时，如果遇到非数字字符，直接返回当前的整数值
4. 如果当前是正数，但是对应整数超过了 2³¹- 1，则直接返回 2³¹- 1；如果当前是负数，但是对应整数小于 -2³¹，那么直接返回 -2³¹

接下来按照规则处理字符串，每个规则对应处理方法为：

1. 首先对字符串进行 trim，去除前导和后缀空格
2. 判断首字符是否为 - 或者 +，若是，则使用标记表示当前数的正负情况，同时更新遍历索引
3. 遍历字符串，初始时索引为 0，若有第二条的情况则为 1。若当前字符不是数字，那么直接停止遍历，否则更新整数值。更新方法为，初始时使用 ans 表示当前的整数，每遍历一位数字都更新为 ans * 10 - 当前位数字（这里用 - 是因为 ans 为负数，方便进行越界判断）
4. 使用标志位 limit 表示当前整数的边界值，这里统一使用负数。如果是正数，边界值为-2³¹ + 1，如果是负数则为 -2³¹，同时使用 标志位 mulLimit 辅助判断，其值为 limit / 10。具体判断条件为，每次取出当前数字位后，先判断当前 ans 是否小于 mulLimit，若小于则 ans * 10 一定小于 limt 值，也就是会越界；之后再判断 ans 是否小于limit + 当前位数字（这里等价于 ans - 当前位数字 与 limt 进行对比，只是 ans - 当前位数字 发生越界后会造成判断失误，所以使用了等式交换），若小于则说明越界

具体看代码：

public int myAtoi(String s) {
        // 取出首尾空格
        s = s.trim();
        // 标记当前整数是否为负数
        boolean isNeg = false;
        // 当前的边界值
        int limit = -Integer.MAX_VALUE;
        int ans = 0;
        int len = s.length();
        int idx = 0;
        // 判断首位是否是符号位
        if (len > 0 && !Character.isDigit(s.charAt(0))) {
            // 若是负数，更新标记位和边界值
            if (s.charAt(0) == '-') {
                isNeg = true;
                limit = Integer.MIN_VALUE;
                idx = 1;
            } else if (s.charAt(0) == '+') {
                idx = 1;
            }
        }
        // 辅助边界值
        int mulLimit = limit / 10;
        while (idx < len) {
            // 若当前位字符不是数字，跳出循环
            if (s.charAt(idx) < '0' || s.charAt(idx) > '9') {
                break;
            }
            // 获取当前位数字
            int digit = s.charAt(idx++) - '0';
            // 根据辅助位判断是否越界
            if (ans < mulLimit) {
                ans = limit;
                break;
            }
            ans *= 10;
            // 根据边界值判断是否越界
            if (ans < limit + digit) {
                ans = limit;
                break;
            }
            ans -= digit;
        }
        return isNeg ? ans : -ans;
    }