8. 字符串转换整数（atoi）

解题思路
Go
Rust

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格，检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。确定最终结果是负数还是正数。如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，”123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：本题中的空白字符只包括空格字符 ‘ ‘ 。除前导空格或数字后的其余字符串外，请勿忽略任何其他字符。

解题思路

这道题最好不要用语言内置的函数。但同时如果只是使用if-else去判断各种情况又会让代码变得很冗余。所以我们使用有限状态机的方式。即假设我们的程序在每一时刻存在一个状态s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。
本题可以建立如下图所示的状态机：

也可以用如下的表格来表示

	‘’	+/-	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

接下来编程部分就非常简单了：我们只需要把上面这个状态转换表抄进代码即可。另外自动机也需要记录当前已经输入的数字，只要在 s’ 为 in_number 时，更新我们输入的数字，即可最终得到输入的数字。

const myAtoi = function(str){
    class Automaton {
      constructor(){
        this.state = "start"
      this.ans = 0
      this.sign = 1
      this.map = new Map([
          ['start', ['start', 'signed', 'in_number', 'end']],
        ['signed', ['end', 'end', 'in_number', 'end']],
        ['in_number', ['end', 'end', 'in_number', 'end']],
        ['end', ['end', 'end', 'end', 'end']]
      ])
    }
    //进行状态的转换
    get(char){
        this.state = this.map.get(this.state)[this.getIndex(char)]
      //对字符串类型进行减法操作，可以将得到一个数值型（Number）的值
      if(this.state==="in_number"){
          this.ans = this.ans * 10 + (char-0) //括号里是将字符串变成数字的
        this.ans = this.sign === 1 ? Math.min(this.ans, Math.pow(2, 31) - 1) : Math.min(this.ans, -Math.pow(-2, 31));
      }else if(this.state === "signed"){
          this.sign = char==="+" ? 1 : -1
      }
    }
    //状态转换规则
    getIndex(){
        if(char === ' ') {
          return 0
      }else if( char=== "-" || char === "+"){
          return 1
      }else if(typeof Number(char) === "number" && !isNaN(char)){
          return 2
      }else{
          return 3
      }
    }
  }
  let automaton = new Automaton()
  for(let char of str){
      automaton.get(char)
  }
  return automaton.sign * automaton.ans
}

Go

type State int
type CharType int
const (
    STATE_START State = iota
    STATE_SIGN
    STATE_NUMBER
    STATE_END
)
const (
    CHAR_SPACE CharType = iota
    CHAR_NUMBER
    CHAR_SIGN
    CHAR_OTHER
)
func toCharType(ch byte) CharType {
    switch ch {
    case '0', '1', '2', '3', '4', '5', '6', '7', '8', '9':
        return CHAR_NUMBER
    case '+', '-':
        return CHAR_SIGN
    case ' ':
        return CHAR_SPACE
    default:
        return CHAR_OTHER
    }
}
func myAtoi(s string) int {
    transfer := map[State]map[CharType]State{
        STATE_START: map[CharType]State{
            CHAR_SPACE:STATE_START,
            CHAR_SIGN:STATE_SIGN,
            CHAR_NUMBER:STATE_NUMBER,
        },
        STATE_SIGN: map[CharType]State{
            CHAR_NUMBER:STATE_NUMBER,
        },
        STATE_NUMBER:map[CharType]State{
            CHAR_NUMBER:STATE_NUMBER,
        },
    }
    ans := 0
    sign := 1
    state := STATE_START
    for i := 0; i < len(s); i++ {
        typ := toCharType(s[i])
        if _, ok := transfer[state][typ]; !ok {
            return sign * ans
        } else {
            if transfer[state][typ] == STATE_SIGN && s[i] == '-' {
                sign = -1
            }
            if transfer[state][typ] == STATE_NUMBER {
                ans = ans * 10 + int(s[i] - '0')
                if sign == 1 && ans > math.MaxInt32 {
                    return math.MaxInt32
                }
                if sign == -1 && -ans < math.MinInt32 {
                    return math.MinInt32
                }
            }
            state = transfer[state][typ]
        }
    }
    return sign * ans
}

Rust

fn c2i(c: char) -> i32 {
    (c as u8 - '0' as u8) as i32
}

enum Status {
    Waiting,
    Positive(i32),
    Negative(i32),
    End(i32),
}

impl Solution {
    fn overflowing_mul10(a: i32) -> (i32, bool) {
        match a.overflowing_mul(10) {
            (_, true) => match a > 0 {
                true => (i32::max_value(), true),
                false => (i32::min_value(), true),
            },
            (ans, false) => (ans, false),
        }
    }

    fn overflowing_mul10_add(a: i32, b: i32) -> (i32, bool) {
        match Solution::overflowing_mul10(a) {
            (o, true) => (o, true),
            (a, false) => match a.overflowing_add(b) {
                (_, true) => (i32::max_value(), true),
                (ans, false) => (ans, false),
            },
        }
    }

    fn overflowing_mul10_sub(a: i32, b: i32) -> (i32, bool) {
        match Solution::overflowing_mul10(a) {
            (o, true) => (o, true),
            (a, false) => match a.overflowing_sub(b) {
                (_, true) => (i32::min_value(), true),
                (ans, false) => (ans, false),
            },
        }
    }

    pub fn my_atoi(s: String) -> i32 {
        let mut status = Status::Waiting;
        for ch in s.chars() {
            status = match status {
                Status::Waiting => match ch {
                    ' ' => continue,
                    '-' => Status::Negative(0),
                    '+' => Status::Positive(0),
                    '0'..='9' => Status::Positive(c2i(ch)),
                    _ => Status::End(0),
                },
                Status::Positive(a) => match ch {
                    '0'..='9' => match Solution::overflowing_mul10_add(a, c2i(ch)) {
                        (o, true) => Status::End(o),
                        (ans, false) => Status::Positive(ans),
                    },
                    _ => Status::End(a),
                },
                Status::Negative(a) => match ch {
                    '0'..='9' => match Solution::overflowing_mul10_sub(a, c2i(ch)) {
                        (o, true) => Status::End(o),
                        (ans, false) => Status::Negative(ans),
                    },
                    _ => Status::End(a),
                },
                Status::End(_) => break,
            };
        }
        match status {
            Status::Positive(ans) | Status::Negative(ans) | Status::End(ans) => ans,
            Status::Waiting => 0,
        }
    }
}

8. 字符串转换整数 （atoi）

解题思路

Go

Rust