整数反转
题目描述：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
其实这个题目已经足够简单了，在解题的时候，只需要注意下溢出问题即可。
Way 1
非常容易想到的一种方法就是把给定的整数转换为字符串，然后通过字符串的反转来得到整数的反转，看代码
class Solution: def reverse(self, x: int) -> int: if x < 0: myint = - int(str(-x)[::-1]) if myint < -2147483648: return 0 return - int(str(-x)[::-1]) else: myint = int(str(x)[::-1]) if myint > 2147483647: return 0 return int(str(x)[::-1])
这种解法是比较容易想到的，当然最终的成绩虽然是通过，但是却还有比较大的提升空间。
下面我们再来通过数学的方法来优化下
Way 2
对于一个整数，我们可以通过取它与10的模来获得最后一位数字，然后再把该数字乘以10，同时重置该整数为他自己的整除数值，以此类推，直至这个整数整除为0为止。
当然还需要注意整数的符号和溢出问题
class Solution: def reverse(self, x: int) -> int: reverse = 0 if x >= 0: while x != 0: tail = x % 10 x //= 10 reverse = reverse * 10 + tail if reverse > 2**31 -1: return 0 else: return reverse else: x = abs(x) while x != 0: tail = x % 10 x //= 10 reverse = reverse * 10 + tail if - reverse < - 2**31: return 0 else: return - reverse
Java 实现
class Solution { public int reverse(int x) { int rev = 0; while (x != 0) { int pop = x % 10; x /= 10; if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0; if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0; rev = rev * 10 + pop; } return rev; } }
回文数
题目描述：
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
进阶:
你能不将整数转为字符串来解决这个问题吗？
题目里也说了，最好不用字符串的方式来解决，那么我们来看看思路吧。
Way 1
我们可以继续使用上面整数反转的方式来解决
class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False elif x == 0: return True elif x % 10 == 0: return False else: y = x reverse = 0 while (x != 0): tail = x % 10 x //= 10 reverse = reverse * 10 + tail if y == reverse: return True else: return False
不过这种解法效果并不是很好
下面我们可以再进一步，来看看回文数的特点。
Way 2
回文数，必定会是一个前后对称的数字，比如：123321，3223 等等，所以如果我们能够拿出前半部分与后半部分，对比这两部分是否一致也是可以的
class Solution: def isPalindrome(self, x: int) -> bool: if x < 0: return False length = 0 help = 1 tmp = x while tmp != 0: length += 1 tmp //= 10 for i in range(1, length): help *= 10 while (x != 0): head = x // help tail = x % 10 if head != tail: return False x = x % help // 10 help //= 100 return True
该方法看似只循环了一般的数据，但是实际上结果却并没有提升太多
看来这种回文数问题，在没有限制的前提下，还是使用字符串的方法来解决最好。
class Solution: def isPalindrome(self, x: int) -> bool: mystr = str(x) return mystr == mystr[::-1]
简洁又方便
Java 实现
class Solution { public boolean isPalindrome(int x) { if (x < 0) { return false; } int help = 1; int tmp = x; while (tmp >= 10) { help *= 10; tmp /= 10; } while (x != 0) { if (x % 10 != x / help) { return false; } x = x % help / 10; help /= 100; } return true; } }
今天的两道算法题都属于比较简单的，哈哈哈，从简单的开始，给自己增加信心呀！！
