今天我们继续力扣之旅,还是从简单的题目下手,整数反转与回文数
整数反转
题目描述:
给出一个 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; } }
今天的两道算法题都属于比较简单的,哈哈哈,从简单的开始,给自己增加信心呀!!