剑指offer(C++)-JZ67：把字符串转换成整数atoi(算法-模拟)

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

题目描述：

写一个函数 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，根据题目条件设立矩阵如下：

1. 起始状态为0，分析第一行：如果碰到空格，那下一个状态还是0；如果碰到符号，则状态转为1；如果碰到数字，则状态转为2；如果碰到无效字符，状态转为3。
2. 假设状态转为1，分析第二行：如果碰到空格，即+空格，则无效，因此第二行第一列为3；如果又碰到符号，例如+-，也无效，所以第二行第二列为3；如果碰到数字，例如-3，则状态转为2；碰到无效字符状态转为3。
3. 假设状态转为2，分析第三行：如果碰到空格，例如+8空格或者8空格，后续均无效，因此第三行第一列为3；如果碰到符号，例如+8+或者8+，后续也是均无效，因此第三行第二列为3；如果碰到数字，例如+89或者89，则后续是有效的，因此第三行第三列为2；无效字符同理无效。
4. 当状态为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++;elsebreak;}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;}
};