题解一:模拟
解题思路:模拟考虑各种特殊情况:
1、负号“-”与正号“+”只能出现在第一个i=0的位置;
2、不能出现除0~9与+、-之外的任何字符;
3、不能出现前置零;
4、最后结果判断是否越界(INT_MIN<=res<=INT_MAX);
特判所有的特殊情况后,如示例将字符串转换成整数:
复杂度分析:
时间复杂度:O(n),遍历字符串
空间复杂度:O(1)
实现如下:
class Solution { public: int StrToInt(string str) { int flag = 0;//标记数字正负 long long res = 0; for (int i = 0; i < str.size(); ++i) { if (str[i] == '-' || str[i] == '+') {//判断第一个 if (i != 0) return 0; flag = str[i] == '-' ? 1 : 0; } else if (str[i] >= '0'&&str[i]<='9') {//将字符串转变成int类型 if (str[i] == '0') { if (res == 0)return 0;//前置零的情况特判; else res = res * 10 + 0; } else { res = res * 10 + str[i] - '0'; } } else { return 0; } } //负数 if(flag){ //负数 res=-res; if(res<INT_MIN)return 0;//小于int最小值 return res; } //正数 if(res>INT_MAX)return 0;//大于int最大值 return res; } };
题解二:递归
解题思路:同题解一;
注意事项:注意递归的结束条件;
复杂度分析:
时间复杂度:O(n),遍历整个字符串
空间复杂度:O(n),递归最大深度;
实现如下:
class Solution { public: long long res=0,flag=0; void f(string &str,int i){ if(i<str.size()){ if (str[i] == '-' || str[i] == '+') {//判断第一个 if (i != 0) {res=0; return ;} flag = str[i] == '-' ? 1 : 0; }else if(str[i] >= '0'&&str[i]<='9'){ if (str[i] == '0') { if (res == 0){res=0; return ;}//前置零的情况特判; else { res = res * 10 + 0; } } else { res = res * 10 + str[i] - '0';//将当前值计算到最终结果上 } }else{ res=0; return ; } f(str,i+1);//递归下一层 } } int StrToInt(string str) { f(str,0); //处理最后的结果 if(flag){ //负数 res=-res; if(res<INT_MIN)return 0;//小于int最小值 return res; } //正数 if(res>INT_MAX)return 0;//大于int最大值 return res; } };