LeetCode腾讯精选练习50 Day2

LeetCode腾讯精选练习50 Day2

7.整数反转

思路：把整数看成一个多项式加法，例如123 = 1 * 100 + 2 * 10 + 3 * 1，我们要做的是将整数反转过来，所以可以想到每次取数字的最低位来进行组合，我们利用迭代思想，取到的数字加在之前取得数字后面组成一个新的数字。从多项式的角度来看是 3 * 10 * 10 * 10 + 2 * 10 * 10 + 1。

值溢出问题：整数的取值范围是

[-2^{31},2^{31}-1]

2的K次方除10的余数始终为2，4，8，所以可以得到下溢和上溢的值。

class Solution {public int reverse(int x) {int ans = 0;while(x != 0){int pop = x % 10;if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7)) // 判断是否上界溢出 2^31-1/10的尾数为7return 0;if (ans < Integer.MIN_VALUE / 10 ||(ans == Integer.MIN_VALUE /10 && pop < -8)) // 判断是否下界溢出  -2^31/10的位数为-8return 0;ans = ans * 10 + pop;   //新切下来的数字加在后面x /= 10;       //去掉切下来的数字}return ans;     //返回反转后的数字}
}

时间复杂度O(n),空间复杂度O(1)

8.字符串转换整数

思路：字符串包含空格，字母，数字，符号等。我们首先要想到的是先去除字符串中的空格。（判断字符串此时是否遍历完成）这样剩下的字符串第一个字符一定是非空格。我们需要的是字符是数字，我们判断第一个数字是否为数字或者表示±的符号。如果为符号，记录该符号。如果为字母，继续遍历直到找到数字或代表正负的符号。整数的取值范围上一题已经说明，我们提前判断是否数值会溢出，至于为何需要提前判断，请看代码详细注释。找到数字后通过迭代方式更新数字。

class Solution {public int myAtoi(String s) {int i = 0;int limit;char[] charArray = s.toCharArray(); //转换为char数组，便于寻找位置while (i < s.length() && charArray[i] == ' '){  //去除前面多余的空格i++;}if (i == s.length())  //判断是否已经遍历完成return 0;int sign = 1;  //判断是否有正负号并记录char firstChar = charArray[i];if (firstChar == '+') {i++;} else if (firstChar == '-') {i++;sign = -1;}int res = 0;while (i < s.length()){      //继续遍历字符串数组，如果是非数字则跳出，判断是否回发生溢出现象char currChar = charArray[i];if (currChar > '9' || currChar < '0')break;//注意到遍历的这个char一定数字，所以需要提前判断是否会发生越界if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10))return Integer.MAX_VALUE;if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) //负数情况return Integer.MIN_VALUE;res = res * 10 + sign * (currChar - '0');//数据合法组成数字i++;//继续遍历下一个字符}return res;}
}

时间复杂度为O(n)，空间复杂度为O(1)。

9.回文数

思路：首先需要明确的是数字一定为非回文数，数字能被10整除的也不是回文数，因为数字第一个数不可能为0，接下来只需要反转数字，判断反转数字与给出数字是否一致即可。

class Solution {public boolean isPalindrome(int x) {if (x < 0 || (x % 10 == 0 && x != 0))  //负数一定不是回文数，如果该数能被10整除说明该数一定不是回文数(第一个数字一定为非零)return false;int revertedNumber = 0;while (x > revertedNumber) {          //反转数字revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}return x == revertedNumber || x == revertedNumber / 10; //判断反转后数字和之前数字是否一致}
}

时间复杂度O(n)，空间复杂度O(1)。