数字位操作
7. Reverse Integer
Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.
Assume the environment does not allow you to store 64-bit integers (signed or unsigned).
Example 1:
Input: x = 123
Output: 321
Example 2:
Input: x = -123
Output: -321
Example 3:
Input: x = 120
Output: 21
Constraints:
-2^31 <= x <= 2^31 - 1
思路
x = -1230
第一次循环：pop = 0, x = -123, reversed = 0
第二次循环：pop = 3, x = -12, reversed = 3
第三次循环：pop = 2, x = -1, reversed = 32
第四次循环：pop = -1, x = 0, reversed = -321
Complexity Analysis
- Time Complexity: O(log(x)). There are roughly log10(x) digits in x.
- Space Complexity: O(1).
C++解法
#include <string> // 引入string库
#include <limits> // 引入limits库以处理溢出
class Solution {
public:
int reverse(int x) {
long long reversed = 0; // 使用long long以避免溢出
while (x != 0) {
// 取出最后一位
int pop = x % 10;
x /= 10; // 删除最后一位
// 加入到反转结果中
reversed = reversed * 10 + pop;
// 检查是否可能发生溢出
if (reversed > std::numeric_limits<int>::max() || reversed < std::numeric_limits<int>::min()) {
return 0; // 溢出时返回0
}
}
return static_cast<int>(reversed); // 转换为int并返回
}
};
class Solution {
public:
int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7))
return 0;
if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8))
return 0;
rev = rev * 10 + pop;
}
return rev;
}
};
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;
}
}
To explain, lets assume that rev is positive.
- If
temp=rev⋅10+popcauses overflow, then it must be thatrev≥INTMAX/10 - If
rev>INTMAX/10, then temp=rev⋅10+pop is guaranteed to overflow. - If
rev==INTMAX/10, thentemp=rev⋅10+popwill overflow if and only if pop>7
I think both two conditions are unneccessary
|| (rev == INT_MAX / 10 && pop > 7)
|| (rev == INT_MAX / 10 && pop > 7)
because when rev == INTMAX/10, pop then will be 0, 1, or 2 because the input is int.
Python3解法
class Solution:
def reverse(self, x: int) -> int:
sign = [1, -1][x < 0]
rev, x = 0, abs(x)
while x:
x, mod = divmod(x, 10)
rev = rev * 10 + mod
if rev > 2**31 - 1:
return 0
return sign * rev
9. Palindrome Number
Given an integer x, return true if x is a palindrome__, and false otherwise.
Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Example 2:
Input: x = -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: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Constraints:
-2^31 <= x <= 2^31 - 1
Follow up: Could you solve it without converting the integer to a string?
思路
方法一：判断是否为负数，如果是负数则返回false，如果不是负数就把参数反转一下比较
Beware of overflow when you reverse the integer.
方法二：转为字符串，然后调用反转函数比较
C++解法
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
return reverse(x) == x;
}
int reverse(int x) {
int rev = 0;
while (x != 0) {
int pop = x % 10;
x /= 10;
if (rev > INT_MAX / 10 || (rev == INT_MAX / 10 && pop > 7))
return 0;
if (rev < INT_MIN / 10 || (rev == INT_MIN / 10 && pop < -8))
return 0;
rev = rev * 10 + pop;
}
return rev;
}
};
测试用例为1234567899时，使用下面代码会报错terminate called after throwing an instance of 'std::out_of_range'
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
string s = to_string(x);
reverse(s.begin(), s.end());
return stoi(s) == x;
}
};
直接使用stoi函数会导致溢出，因为stoi函数会把字符串转换为整数，而字符串的长度是有限的，所以会导致溢出。
#include <string>
#include <algorithm>
class Solution {
public:
bool isPalindrome(int x) {
if (x < 0) return false; // 负数不是回文
string s = to_string(x); // 转换为字符串
string reversed_s = s; // 复制字符串
reverse(reversed_s.begin(), reversed_s.end()); // 反转字符串
return s == reversed_s; // 直接比较反转前后的字符串
}
};