简述网站制作的流程,网站在线设计,wordpress不同页面布局,山东省专业群建设网站作者#xff1a;翟天保Steven 版权声明#xff1a;著作权归作者所有#xff0c;商业转载请联系作者获得授权#xff0c;非商业转载请注明出处 题目描述#xff1a;
写一个函数 StrToInt#xff0c;实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。…作者翟天保Steven 版权声明著作权归作者所有商业转载请联系作者获得授权非商业转载请注明出处 题目描述
写一个函数 StrToInt实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。传入的字符串可能有以下部分组成:
1.若干空格
2.可选一个符号字符 或 -
3. 数字字母符号空格组成的字符串表达式
4. 若干空格
转换算法如下:1.去掉无用的前导空格2.第一个非空字符为或者-号时作为该整数的正负号如果没有符号默认为正数3.判断整数的有效部分3.1 确定符号位之后与之后面尽可能多的连续数字组合起来成为有效整数数字如果没有有效的整数部分那么直接返回03.2 将字符串前面的整数部分取出后面可能会存在存在多余的字符(字母符号空格等)这些字符可以被忽略它们对于函数不应该造成影响3.3 整数超过 32 位有符号整数范围 [−231, 231 − 1] 需要截断这个整数使其保持在这个范围内。具体来说小于 −231的整数应该被调整为 −231 大于 231 − 1 的整数应该被调整为 231 − 14.去掉无用的后导空格
数据范围:
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;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) {// 状态转移矩阵vectorvectorint 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;}
};
