8. 字符串转换整数 (atoi)/面试题67. 把字符串转换成整数(一般)

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−2^31, 2^31 − 1]。如果数值超过这个范围，请返回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。

示例 1:

输入: "42"
输出: 42

示例 2:

输入: " -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

示例 3:

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

示例 4:

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。因此无法执行有效的转换。

示例 5:

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof

思路1：

  1. 先去前边空格
  2. 判断去掉空格后的前面是否有正负号
  3. 判断是否为数字，转换

简单思路，一步一步走就行，但是要注意小细节，容易出错

思路2：

有限状态机
‘ ‘ +/- number other
start start signed in_number end
signed end end in_number end
in_number end end in_number end
end end end end end

回看记录200705

用思路1写了一遍出来，后面看的时候需要将有限状态机写一下，是个好入门的例子

回看记录200712

将状态机实现了一下，不过代码都是抄的，能理解，但后面自己再来一次

代码1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int myAtoi(String str) {
        //1.去除前面空格
        int i=0,flag=1;//1代表正数，0代表负数
        long res =0;//int表示有问题
        char[] cstr = str.trim().toCharArray();
        if(cstr.length==0)
            return 0;
        // while(cstr[i]==' ')
        //     i++;
        //2. 处理正负号
        if(cstr[i]=='-'){
            flag=-1;
            i++;
        }else if(cstr[i]=='+'){
            flag=1;
            i++;
        }
        //3. 转整数，注意越界
        for(;i<cstr.length&&Character.isDigit(cstr[i]);i++){
            res = res*10+(cstr[i]-'0');
            //判断越界
            if(res>=Integer.MAX_VALUE && flag ==1)               
                return Integer.MAX_VALUE;                     
            if(res>Integer.MAX_VALUE && flag ==-1)
                return Integer.MIN_VALUE;                    
        }
        return flag*(int)res;
    }
}

代码2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Automata{
    private int state=0;
    int sign =1;//符号
    long res = 0;
    //状态表
    private int[][] table=new int[][]{{0,1,2,3},{3,3,2,3},{3,3,2,3},{3,3,3,3}};

    //状态转移
    public int get_state(char c){
        if(c==' '){//空格的话，状态还是start
            return 0;
        }else if(c=='-' || c=='+'){
            return 1;
        }else if(Character.isDigit(c)){
            return 2;
        }
        return 3;//end
    }
    //根据状态转移，解析
    public void parse(char c) {
        state = table[state][get_state(c)];//取到下一个状态值
        //状态2时是数字，需要解析
        if(state ==2){
            res = res*10+(c-'0');
            //注意一下溢出条件
            res = sign==1?Math.min(res,Integer.MAX_VALUE):Math.min(res,-(long)Integer.MIN_VALUE);
        }
        //注意符号
        if(state==1 && c=='-')
            sign=-1;
    }
}
class Solution {
    public int myAtoi(String str) {
        Automata au  = new Automata();
        char[] cstr = str.toCharArray();
        for(char c: cstr){
            au.parse(c);
        }
        return au.sign*(int)au.res;
    }
}