每日一题（7）：字符串转换整数

开始

又是一道中等难度题

做完后发现结果虽然不错

但是距离ACM出身的正规军还是有较大差距

所以还是侧重写写过程中学到的知识和自己的一些体会吧

本题场景其实非常适合用自动机来解决

思想是自动机的思想...但是奈何我忘了这个叫自动机（大学课本内容还给老师了...果然还是要多复习...

简单来说就是要有个状态转移表

无论形式是HashMap还是switch-case

大白话来说

就是顺序遍历字符的时候，能够在每个状态做该做的事（处理前导空格/处理符号位/处理内容体），重复这个过程，直至处理完成，转移到下一状态处理

这块都还比较简单

烦就烦在对结果的输出，是需要从个位数开始依次乘以权重并累加

大意就是，我要用1,2,3来输出123，我需要让123 == 1*1000 + 2*100 + 3*1才能得到123

而这个过程，是会溢出的！

负数可能会小于Integer.MIN_VALUE，正数可能会大于Integer.MAX_VALUE

看官方题解是用long类型做结果累加和，绕过了这个问题

但是我不想这样，万一下次题目就让你处理long呢，还有更大的类型允许你绕过吗？

所以我搞出了safeAdd，safeMinus，safeMulti来允许溢出，并只返回极值

也算是比较优雅地解决了这个问题吧

如果不这样设计，基本上代码会出现大堆的if-else来判断是否溢出，非常麻烦

比起防御式编程，我更倾向这种方式

下面看看代码实现

class Solution {
    public int myAtoi(String s) {
        char[] cs = s.toCharArray();

        int state = 0;
        boolean negative = false;
        char[] csr = new char[cs.length];
        boolean finish = false;

        for (int i = 0; i < cs.length; i++) {
            if (finish) {
                break;
            }
            char c = cs[i];
            switch (state) {
                case 0: // 处理前导空格
                    if (c == ' ') {
                        continue;
                    } else {
                        state++;
                        i--;
                    }
                    break;
                case 1: // 处理符号位
                    if (c == '-') {
                        negative = true;
                    } else if (c == '+') {
                        negative = false;
                    } else {
                        i--;
                    }
                    state++;
                    break;
                case 2: // 处理内容体
                    if (Character.isDigit(c)) {
                        csr[i] = c;
                    } else {
                        finish = true;
                        break;
                    }
                    break;
            }
        }

        int r = 0;
        int t = 1;
        for (int i = cs.length - 1; i > -1; i--) {
            char c = csr[i];
            if (c == '\0') {
                continue;
            }
            int n = safeMulti(c2i(c), t);
            if (negative) {
                r = safeMinus(r, n);
            } else {
                r = safeAdd(r, n);
            }
            if (r == Integer.MIN_VALUE || r == Integer.MAX_VALUE) {
                break;
            }
            t = safeMulti(t, 10);
        }

        return r;
    }

    private int c2i(char c) {
        return (int)c - (int)('0');
    }

    private int safeAdd(int i1, int i2) {
        if (i1 > Integer.MAX_VALUE - i2) {
            return Integer.MAX_VALUE;
        }
        return i1 + i2;
    }

    private int safeMinus(int i1, int i2) {
        if (i1 < Integer.MIN_VALUE + i2) {
            return Integer.MIN_VALUE;
        }
        return i1 - i2;
    }

    private int safeMulti(int i1, int i2) {
        if (i1 > Integer.MAX_VALUE / i2) {
            return Integer.MAX_VALUE;
        }
        return i1 * i2;
    }
}

以及这次的执行效率（还不错哈哈

下次继续~（小插曲：昨天没赶上24点前做完，所以...