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