题目描述：
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
1.若干空格
2.（可选）一个符号字符（'+' 或 '-'）
3. 数字，字母，符号，空格组成的字符串表达式
4. 若干空格
转换算法如下:
1.去掉无用的前导空格
2.第一个非空字符为+或者-号时，作为该整数的正负号，如果没有符号，默认为正数
3.判断整数的有效部分：
3.1 确定符号位之后，与之后面尽可能多的连续数字组合起来成为有效整数数字，如果没有有效的整数部分，那么直接返回0
3.2 将字符串前面的整数部分取出，后面可能会存在存在多余的字符(字母，符号，空格等)，这些字符可以被忽略，它们对于函数不应该造成影响
3.3 整数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231的整数应该被调整为 −231 ，大于 231 − 1 的整数应该被调整为 231 − 1
4.去掉无用的后导空格
数据范围:
1.0 <=字符串长度<= 100
2.字符串由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成
示例：
输入：
"4396 clearlove"
返回值：
4396
说明：
6后面的字符不属于有效的整数部分，去除，但是返回前面提取的有效部分
解题思路：
本题考察算法场景模拟。两种解题思路。
1）遍历法
首先过滤前置空格；再判断正负号；之后判断连续数字，过程中注意正负极限判断；每找到一个新数字，就把之前的数字*10再累加上去，遍历完即可得到答案。复杂度O(n)。
2）状态机
基于状态转移矩阵对字符串遍历过程的状态进行分析。
状态分为4种，空格、符号、数字和无效，对应0123，根据题目条件设立矩阵如下：
- 起始状态为0，分析第一行：如果碰到空格，那下一个状态还是0；如果碰到符号，则状态转为1；如果碰到数字，则状态转为2；如果碰到无效字符，状态转为3。
- 假设状态转为1，分析第二行：如果碰到空格，即+空格，则无效，因此第二行第一列为3；如果又碰到符号，例如+-，也无效，所以第二行第二列为3；如果碰到数字，例如-3，则状态转为2；碰到无效字符状态转为3。
- 假设状态转为2，分析第三行：如果碰到空格，例如+8空格或者8空格，后续均无效，因此第三行第一列为3；如果碰到符号，例如+8+或者8+，后续也是均无效，因此第三行第二列为3；如果碰到数字，例如+89或者89，则后续是有效的，因此第三行第三列为2；无效字符同理无效。
- 当状态为2时，对数字进行累加和越界判断；当状态为3时，break退出即可。
总的来说，状态机就是基于题目要求，将可能发生的情形和状态的转变，以矩阵形式表示，进而解题。复杂度O(n)。
测试代码：
1）遍历法
#include <climits> class Solution { public: // 字符串转为整数 int StrToInt(string s) { int sign = 1; int idx = 0; int size = int(s.size()); // 前空格过滤，过滤完如果没有后续则退出 while(idx < size){ if(s[idx] == ' ') idx++; else break; } if(idx == size) return 0; // 判断符号，如果没有后续则退出 if(s[idx] == '+') idx++; else if(s[idx] == '-'){ idx++; sign = -1; } if(idx == size) return 0; // 继续遍历寻找目标数字 int result = 0; while(idx < size){ // 遇到非数字退出 if(s[idx] < '0' || s[idx] > '9') break; // 判断极限 if(result > INT_MAX / 10 || (result == INT_MAX / 10 && (s[idx] - '0') >= (INT_MAX % 10))) return INT_MAX; if(result < INT_MIN / 10 || (result == INT_MIN / 10 && (s[idx] - '0') >= -(INT_MIN % 10))) return INT_MIN; // 字符转为数字 result = result * 10 + sign * (s[idx] - '0'); idx++; } return result; } };
2）状态机
class Solution { public: // 字符串转为整数 int StrToInt(string s) { // 状态转移矩阵 vector<vector<int>> states = { {0,1,2,3}, {3,3,2,3}, {3,3,2,3}, }; // 定义 long result = 0; long top = INT_MAX; long bottom = INT_MIN; int sign = 1; int size = int(s.length()); // 状态从0开始 int state = 0; for(int i = 0; i < size; ++i){ // 空格 if(s[i] == ' '){ state = states[state][0]; } // 正负号 else if(s[i] == '-' || s[i] == '+'){ state = states[state][1]; if(state == 1){ sign = (s[i] == '-') ? -1 : 1; } } // 数字 else if(s[i] >= '0' && s[i] <= '9'){ state = states[state][2]; } // 非法字符 else{ state = states[state][3]; } // 状态为2时，表明在连续数字状态，进行数字累加 if(state == 2){ // 数字相加 result = result * 10 + s[i] - '0'; // 越界处理 result = (sign == 1) ? min(result, top) : min(result, -bottom); } // 状态为3时，说明后续无效，退出即可 else if(state == 3) break; } return (int)sign * result; } };
