思路
思路一
状态机,时间复杂度 $O(n)$,空间复杂度 $O(1)$。
思路二
递归下降的语法解析,时间复杂度 $O(n)$,空间复杂度 $O(n)$。
CPP
// 状态机
class Solution {
public:
int type(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
int strToInt(string str) {
int transition[][4] = {
/*space +- num others*/
/* 0 1 2 3 */
/* empty: 0 */ { 0, 1, 2, -1 },
/* sign : 1 */ { -1, -1, 2, -1 },
/* inner: 2 */ { -1, -1, 2, -1 }
};
int x = 0, sign = 1, s = 0;
for (auto c: str) {
s = transition[s][type(c)];
if (s == -1) break;
if (s == 1 && c == '-') sign = -1;
else if (s == 2) {
x = x * 10 + c - '0';
if (x < 0) return sign > 0 ? INT_MAX : INT_MIN;
}
}
return x * sign;
}
};
JAVA
// 状态机
class Solution {
public int strToInt(String str) {
int x = 0, sign = 1;
for (int i = 0, s = 0; i < str.length(); i++) {
char c = str.charAt(i);
s = transition[s][type(c)];
if (s == -1) break;
if (s == 1 && c == '-') sign = -1;
else if (s == 2) {
x = x * 10 + c - '0';
if (x < 0) return sign > 0
? Integer.MAX_VALUE
: Integer.MIN_VALUE;
}
}
return x * sign;
}
int type(char c) {
if (c == ' ') return 0;
if (c == '+' || c == '-') return 1;
if (c >= '0' && c <= '9') return 2;
return 3;
}
int[][] transition = new int[][] {
/*space +- num others*/
/* 0 1 2 3 */
/* empty: 0 */ { 0, 1, 2, -1 },
/* sign : 1 */ { -1, -1, 2, -1 },
/* inner: 2 */ { -1, -1, 2, -1 }
};
}
PYTHON3
# 状态机
class Input:
Space = 0
Sign = 1
Num = 2
Others = 3
def type(c):
if c == ' ':
return Input.Space
if c in '+-':
return Input.Sign
if '0' <= c <= '9':
return Input.Num
return Input.Others
# 0 1 2 -1
# " -1234efg"
class State:
Empty = 0
Sign = 1
Inner = 2
Invalid = -1
Transition = {
# Space Sign Num Others
State.Empty: [State.Empty, State.Sign, State.Inner, State.Invalid],
State.Sign: [State.Invalid, State.Invalid, State.Inner, State.Invalid],
State.Inner: [State.Invalid, State.Invalid, State.Inner, State.Invalid]
}
class Limit:
MIN = -(1 << 31)
MAX = (1 << 31) - 1
class Sign:
Positive = 1
Negative = -1
class Solution(object):
def strToInt(self, str):
x, sign, s = 0, Sign.Positive, State.Empty
for c in str:
s = Transition[s][Input.type(c)]
if s == State.Invalid:
break
if s == State.Sign and c == '-':
sign = -1
elif s == State.Inner:
x = x * 10 + ord(c) - ord('0')
if sign == Sign.Positive and x > Limit.MAX:
return Limit.MAX
if sign == Sign.Negative and -x < Limit.MIN:
return Limit.MIN
return x * sign
# 递归下降的语法解析
"""
integer: digits
| sign digits
| spaces integer
digits: digit
| digit digits
spaces: space
| space spaces
space ' '
sign: +-
digit: 0-9
"""
class Solution(object):
def strToInt(self, str):
self.str = str
self.len = len(str)
self.idx = 0
self.sgn = 1
self.val = 0
self.min = -(1 << 31)
self.max = (1 << 31) - 1
self.integer()
return self.val * self.sgn
def integer(self):
self.spaces()
if self.sign() and self.previous() == '-':
self.sgn = -1
self.digits()
def digits(self):
if self.digit():
self.val = self.val * 10 + ord(self.previous()) - ord('0')
if self.sgn == 1 and self.val >= self.max:
self.val = self.max
return
if self.sgn == -1 and -self.val <= self.min:
self.val = -self.min
return
self.digits()
def spaces(self):
if self.space():
self.spaces()
def space(self):
return self.valid(lambda c: c == ' ')
def digit(self):
return self.valid(lambda c: c in '0123456789')
def sign(self):
return self.valid(lambda c: c in '+-')
def previous(self):
return self.str[self.idx - 1]
def peek(self):
if self.idx < self.len:
return self.str[self.idx]
return 'x'
def valid(self, checker):
if checker(self.peek()):
self.idx += 1
return True
return False
状态机可视化代码
// https://stately.ai/viz
import { createMachine } from 'xstate';
const parseIntegerMachine = createMachine({
id: 'Parse Integer',
initial: 'empty',
states: {
empty: {
on: {
'space': 'empty',
'+-': 'sign',
'num': 'inner',
'not space or num or +-': 'end'
},
type: 'final'
},
sign: {
on: {
'num': 'inner',
'not num': 'end'
}
},
inner: {
on: {
'num and small abs': 'inner',
'not num or abs too large': 'end'
}
},
end: {
type: 'final'
}
}
});