剑指 Offer 67. 把字符串转换成整数
题目说明
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。
当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。
该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。
注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0。
假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
解题思路
从头到尾对字符串进行一个遍历操作。
-
对一开始的空格进行一个滤去处理
-
对第一个非空格字符进行符号判定，用sign记录。
-
对后续的数字进行遍历，直到第一个非数字出现
- 通过res = res * 10 + str.charAt(index) - ’0‘来记录结果
- res要与最大值进行比较判断，如果超限直接根据sign来返回Integer.MAX_VALUE或者Integer.MIN_VALUE。此处用到技巧，用(Integer.MAX_VALUE / 10)来和res进行比较，防止超限，之前前面进行比较，如果相等则比较最后一位和’7‘
-
返回sign * res
剑指 Offer 20. 表示数值的字符串
题目说明
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。
数值（按顺序）可以分成以下几个部分：
若干空格
一个 小数 或者 整数
（可选）一个 'e' 或 'E' ，后面跟着一个 整数
若干空格
小数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
至少一位数字，后面跟着一个点 '.'
至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
一个点 '.' ，后面跟着至少一位数字
整数（按顺序）可以分成以下几个部分：
（可选）一个符号字符（'+' 或 '-'）
至少一位数字
部分数值列举如下：
["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]
部分非数值列举如下：
["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]
解题思路
有限状态自动机
有限状态自动机（Finite State Machine，简称FSM），是一种用来表示和设计顺序逻辑电路、计算机程序，以及其他类型的行为的数学模型。有限状态自动机在理论计算机科学、语言研究、电脑科学、语言识别等领域都得到了广泛地应用。
一个有限状态自动机由以下组成：
- 状态：这些是有限状态机的核心部分，代表系统的不同条件或配置。
- 转移：这是从一个状态移动到另一个状态的规则或条件。这些转移可以基于输入或事件。
- 起始状态：有限状态机开始工作时的状态。
- 终止状态：这些状态表示有限状态机的结束或接受状态。当达到这些状态时，系统将停止运行。
有两类主要的有限状态自动机：
- 确定性有限状态自动机（Deterministic Finite Automaton，简称DFA）：在这种类型的自动机中，对于给定的输入，每个状态只能转移到一个状态。
- 非确定性有限状态自动机（Nondeterministic Finite Automaton，简称NFA）：在这种类型的自动机中，对于给定的输入，每个状态可能会转移到多个状态。
在本题中，我们可以应用这种思路来解决。如果用简单的遍历下去的话，会出现很多种分支已经情况，会导致代码逻辑非常复杂且出现冗余的情况。有限自动状态机可以有效的解决这个问题。
在本题中，字符可以有六种情况（非左下图五种我们用’?‘表示，直接返回false即可），而这六种情况我们可以构成8种状态。如果要构成一个数字的话，我们是可以很明确的判定下一位可以是什么以及不可以是什么，基于此思想，我们产生了八种状态，而这八种状态以及他们的转换关系也就构成了有限状态自动机
我们根据以下的状态机定义来说明情况
Map[] maps = {
new HashMap<>() {
// 0:起始blank -> blank, sign, dot前的dight, dot
{put('b', 0); put('s', 1); put('d', 2); put('.', 8);}},
new HashMap<>() { // 1:e之前的sign -> dot前的dight, dot前为空（此处作此区分，如果前面为空的话后面不能为空）
{put('d', 2); put('.', 8);}},
new HashMap<>() { // 2: dot之前的dight -> 继续dot前的dight, dot前不为空, Ee, blank
{put('d', 2); put('.', 3); put('e', 4); put('b', 7);}},
new HashMap<>() { // 3: dot之后的dight -> 继续dot后的dight, Ee，blank
{put('d', 3); put('e', 4);put('b', 7);}},
new HashMap<>() { // 4: Ee -> sign, dot后的dight(Ee后面不能再有dot了)
{put('s', 5); put('d', 6);}},
new HashMap<>() { // 5: e之后的sign -> e之后的dight
{put('d', 6);}},
new HashMap<>() { // 6: e之后的dight -> 继续e之后的dight（不能再有dot了）, blank
{put('d', 6); put('b', 7);}},
new HashMap<>() { // 7: 尾部blank -> 继续尾部blank
{put('b', 7);}},
new HashMap<>() { // 8: dot前为空的情况 -> 只能且必须去dot后dight（后面必须有dight）
{put('d', 3);}}
};
把所有合法的转移情况都标记出来，那么如果下一步的转移是不合法的，则说明出问题了，该字符串不能构成数字
最后我们还需要判定合法结束状态，即有些状态是可以合法结束的，有些则不可以
在以上的情况中，只有状态2、状态3、状态6和状态7是合法的，即字符串可以构成数字