1. 题目
1.1 英文
Determine whether an integer is a palindrome. Do this without extra space.
Some hints:
- Could negative integers be palindromes? (ie, -1)
- If you are thinking of converting the integer to string, note the restriction of using extra space.
- You could also try reversing an integer. However, if you have solved the problem “Reverse Integer”, you know that the reversed integer might overflow. How would you handle such case?
- There is a more generic way of solving this problem.
1.2 中文
检测一个整形是否是一个回文(从左往右看和从右往左看都相等的数),不要使用额外空间。
提示:
- 负数是否是回文?
- 如果你想将整形转化成字符串,注意不要使用额外空间的限制。
- 你可以尝试反转整形。然而,如果你解决了“反转整形”的问题,那你可能知道反转整形可能会导致溢出,你该如何控制这个情况。
- 解决这个问题有一个更通用的方法。
2. 解答
接下来我们就来用这个更通用的方法来解决,Go语言实现。
func isPalindrome(x int) bool {
// 小于0 或者 末尾是0而本身不是0 时,不符合情况
if x < 0 || ( x % 10 == 0 && x != 0 ){
return false
}
revertedNum := 0
// x大于revertedNum时说明还未过一半,继续循环
for x > revertedNum {
revertedNum = revertedNum * 10 + x % 10
x = x / 10
}
// 判断 x==revertedNum/10 的情况用在当长度为奇数时;比如1234321,最后得到的是123和1234
return x == revertedNum || x == revertedNum / 10
}
时间复杂度:O(log_{10}n)
空间复杂度:O(1)
0 条评论
来做第一个留言的人吧!