题目

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

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

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

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

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

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

说明：

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

示例 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) 。

方案一

  1. var INT_MIN = -2147483648
  2. var INT_MAX = 2147483647
  3. var boundary = INT_MAX / 10
  5. func strToInt(str string) int {
  6.     // 去除前导空格
  7.     s := strings.TrimLeft(str, " ")
  8.     if len(s) == 0 {
  9.         return 0
  10.     }
  12.     // 第一个字符不是 + 或 -, 且不是 0-9
  13.     first := string(s[0])
  14.     if (first < "0" || first > "9") && (first != "+" && first != "-") {
  15.         return 0
  16.     }
  17.     symbol := "+"
  18.     if first == "+" || first == "-" {
  19.         symbol = first
  20.         s = s[1:]
  21.     }
  23.     // 开始拼接数字
  24.     num := 0
  25.     for i := range s {
  26.         ch := string(s[i])
  27.         a := getNum(ch)
  28.         if a == -1 { // 遇到了 非 0-9
  29.             break
  30.         }
  32.         if num > boundary || (num == boundary && ch > "7") {
  33.             if symbol == "+" {
  34.                 return INT_MAX
  35.             }
  37.             return INT_MIN
  38.         }
  40.         num *= 10
  41.         num += a
  42.     }
  44.     if symbol == "-" {
  45.         return -num
  46.     }
  47.     return num
  48. }
  50. func getNum(ch string) int {
  51.     switch ch {
  52.     case "0":
  53.         return 0
  54.     case "1":
  55.         return 1
  56.     case "2":
  57.         return 2
  58.     case "3":
  59.         return 3
  60.     case "4":
  61.         return 4
  62.     case "5":
  63.         return 5
  64.     case "6":
  65.         return 6
  66.     case "7":
  67.         return 7
  68.     case "8":
  69.         return 8
  70.     case "9":
  71.         return 9
  72.     }
  74.     return -1
  75. }
  • 注意第32行，越界条件的判断

    方案二（DFA）

    核心问题是，如何判断这个问题可以用状态机来解决？

建立下图表示的状态机
image.png

状态表


 “ “ +/- 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 
type Automaton struct {
    min      int64
    max      int64
    boundary int
    table    [][]string

    overflow bool
    // +/-
    symbol string
    state  string
    ans    int
}

func NewAutomaton() *Automaton {
    return &Automaton{
        min:      -2147483648,
        max:      2147483647,
        boundary: 214748364,
        state:    "start",
        symbol:   "+",
        table: [][]string{
            {"start", "signed", "in_number", "end"},
            {"end", "end", "in_number", "end"},
            {"end", "end", "in_number", "end"},
            {"end", "end", "end", "end"},
        },
    }
}

// Push 往自动机中添加一个字符
func (a *Automaton) Push(ch string) {
    a.setNextState(ch)

    switch a.state {
    case "start":
    case "signed":
        a.symbol = ch
    case "in_number":
        i := a.chToInt(ch)
        if a.willOverflow(i) {
            a.overflow = true
            // 结束
            a.state = "end"
        }
        a.ans = a.ans*10 + i
    case "end":
    }
}

func (a *Automaton) chToInt(ch string) int {
    return int([]byte(ch)[0] - "0"[0])
}

func (a *Automaton) willOverflow(i int) bool {
    return (a.ans == a.boundary && i > 7) || a.ans > a.boundary
}

func (a *Automaton) setNextState(ch string) {
    if a.state == "end" {
        return
    }

    var row int
    switch ch {
    case " ":
        row = 0
    case "+", "-":
        row = 1
    case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
        row = 2
    default:
        row = 3
    }

    a.state = a.table[a.getCol()][row]
}

func (a *Automaton) getCol() int {
    switch a.state {
    case "start":
        return 0
    case "signed":
        return 1
    case "in_number":
        return 2
    default:
        return 3
    }
}

func (a *Automaton) Ans() int {
    if a.overflow {
        if a.symbol == "+" {
            return int(a.max)
        }

        return int(a.min)
    }

    if a.symbol == "-" {
        return -a.ans
    }
    return a.ans
}

func myAtoi(s string) int {
    auto := NewAutomaton()
    for _, ch := range s {
        auto.Push(string(ch))
    }

    return auto.Ans()
}

状态模式

原文

https://leetcode-cn.com/problems/string-to-integer-atoi/
https://leetcode-cn.com/leetbook/read/illustrate-lcof/e2im3i/
https://leetcode-cn.com/problems/string-to-integer-atoi/solution/zi-fu-chuan-zhuan-huan-zheng-shu-atoi-by-leetcode-/