博客

这个题目没有考察算法知识，模拟的是日常开发中对原始数据的处理，

面试遇到这类问题，应先仔细阅读题目文字说明和示例，有疑惑的地方需要和面试官确认，在编码的时候需要耐心和细心调试

几个要点：

• 去掉先导空格
• 判断第一个字符为+或者-的情况，因此，需要设计一个遍历sign，初始化时为1，如果遇到 -（负号），将sign的值修改为-1
• 判断是否是数字，可以使用字符的ASCII码数值进行比较，即c >= ‘0’ && c <= ‘9’
• 在遇到第一个字符不是数字字符的情况下，转换停止，退出循环
• 如果转换以后的数字超过了int类型的范围，需要截取。这里不能将记录结果的变量res设置为long型，注意：由于输入的字符串转换以后也可能超过long类型，因此需要在循环内部就判断是否越界，只要越界就退出循环，这样也可以减少不必要的计算
• 下标访问，因此，全程需要考虑数组下标是否越界的情况
  • 由于题目中说【环境只能保存32位整数】，因此，这里在每一轮循环之前先要检查乘以10以后是否溢出

class Solution {
    public int myAtoi(String s) {

        int len = s.length();

        char[] charArray = s.toCharArray();

        //1. 去除前导空格
        int index = 0;
        while (index < len && charArray[index] == ' ') {
            index++;
        }

        //针对极端情况 "            "
        if (index == len) {
            return 0;
        }

        //如果出现符号字符，仅第一个有效，并记录正负
        //sign=1表示默认为正数
        int sign = 1;
        char firstChar = charArray[index];
        if (firstChar == '+') {
            index++;
        } else if (firstChar == '-') {
            index++;
            sign = -1;
        }

        //将后续出现的数字字符进行转换
        //不能使用long类型，题目说的？
        int res = 0;
        while (index < len) {
            char currChar = charArray[index];

            //先判断不合法的情况
            if (currChar < '0' || currChar > '9') {
                break;
            }

            //题目中说：环境只能存储32位大小的有符号正数，因此，需要提前判断：乘以10以后是否越界
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            //合法的情况下，才考虑转换，每一步都把符号位乘进去
            res = res * 10 + sign * (currChar - '0');
            index++;
        }

        return res;
    }
}

算法的时间复杂度：O(N)，这里N为字符串的长度