leetcode day4

7.整数反转

1.利用数组反转： 思路：利用vector数组先存储每一位，然后再反转，溢出判断可以借助x+y>2³¹-1，而当只能用int时，采取移项变成y>2³¹-1-x即可。

class Solution { public: int reverse(int x) { int tmp,fan=0,fu=0; vector<int> jie; int i=0; if(x==-2147483648) return 0; //对于-2^31单独处理 if(x<0) //负数取正 { fu=1; x=abs(x); } do //截取所有数字 { jie.push_back(x%10); x=x/10; i++; }while(x!=0); for(i=0;i<jie.size();i++) //反转同时做溢出判断 { if(jie.size()==10&&jie[0]>2) return 0; if(pow(10,jie.size()-i-1)*jie[i]>2147483647-fan) return 0; fan+=pow(10,jie.size()-i-1)*jie[i]; } if(fu==1) //恢复符号 { fan=-fan; if(fan>0) return 0; } else if(fan<0) return 0; return fan; } };

2.伪栈推挤法： 思路：“弹出” x 的最后一位数字，并将它“推入”到 rev 的后面。最后，rev 将与 x 相反。

class Solution { public: int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0; if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0; rev = rev * 10 + pop; } return rev; } };

收获

1.vector相当于动态数组，应该用insert方法或者push_back方法插入 2.对于整数溢出的判断要多总结，同时巧用移项，防止溢出 3.对于这种转换的题，要想到队列，栈等结构

8.字符串转换整数

1.模拟法：

class Solution { public: int myAtoi(string s) { int to=0; int rev=0,pop; int i=0; int fu=0,flag=0,len=0; //flag表示第几次出现+-符号，len表示已有数的位数 for(i=0;i<s.size();i++) { if(flag>1) return 0; //出现两次符号，非法 if(s[i]==' '&&len==0) continue; //吸收开头的空格 else if(s[i]==' ') break; //非开头空格同非法字符直接break if(s[i]=='-'&&len==0) {len++;flag++;fu=1;continue;} //第一次数字前出现符号 else if(s[i]=='-') break; //后续符号当作非法字符 if(s[i]=='+'&&len==0) {len++;flag++;fu=0;continue;} else if(s[i]=='+') break; if('0'>s[i]||s[i]>'9') break; //处理数字 else {pop=s[i]-48;len++;} if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return INT_MAX; //溢出判断 if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && -pop < -8)) return INT_MIN; if(fu==0) rev=rev*10+pop; else rev=rev*10-pop; } return rev; } };

2.有限状态机法（官方）

收获

1.有限状态机方法很适用于对于不同状态的一个串来进行操作 2.模拟法其实经过修修补补基本和有限状态机差不多，只不过需要很强的逻辑思维不然很容易混乱