LeetCode 0009 - Palindrome Number
# Hints
- 思维
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121
Output: true
Example 2:
Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Example 3:
Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Coud you solve it without converting the integer to a string?
# 题意
给定一个正整数 ,判断将其视为字符串时是否为回文串。
# 题解
显然我们可以先把 转换为字符串然后判断 是否为回文串,但是我们并不需要这么麻烦就可以解决问题。
我们可以将 按数位反转得到 ,就像LeetCode 0007那样,然后判断 是否成立即可。但是解法还能更加高效。
我们考虑将 按数位反转的过程,假设 的长度为偶数,那么当反转进行到一半时,应当恰好有 ,其中 为反转过程的当前中间值。下面的表格详细解释了这个过程:
step | x | y |
---|---|---|
0 | 123321 | 0 |
1 | 12332 | 1 |
2 | 1233 | 12 |
3 | 123 | 123 |
而当 的长度为奇数时,以 为例,那么当反转进行到一半时 ,只需判断 是否成立即可。
由于存在十倍的差距,我们根本不需要考虑 的长度,直接判断两个条件是否有任意一个成立即可。到此我们已经得到了最简便的方法。具体的代码实现也非常精简。
细节问题:
- 负数和个位为 的正数一定不满足条件,且都需要特判掉,否则会给自己徒增麻烦。
# AC代码
class Solution {
public:
bool isPalindrome(int x) {
// 特判
if (x < 0) {
return false;
}
if (x % 10 == 0 && x != 0) {
return false;
}
// 主循环
int y = 0;
while (x > y) {
y *= 10;
y += (x % 10);
x /= 10;
}
// 返回
return (x == y || x == y / 10);
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01