力扣(LeetCode)7. 整数反转(C++)

模拟

整数反转，需要一个中间变量 $ans$ ， 循环存入 $x$ 的最低位 $x\%10$， 然后 $x=x/10$ ，得到 $x$ 新的最低位 。如果进入新的循环，$ans\times 10$ ，让上一次的 $ans$ 十进制左移一位。重复上述操作，即可得到 $ans$ 。

朴素解法

因为这题有整形溢出问题，这里使用 $longlong$ 仅演示上述操作，在下一个解法分析边界。

class Solution {
public:
    int reverse(int x) {
        long long ans = 0;
        while(x){
            ans*=10;
            ans +=x%10;
            x/=10;
        }
        if(ans>INT_MAX||ans<INT_MIN) return 0;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度 $O(logn)$ ， $n$ 是 $x$ 的大小，时间复杂度 $O(lo{g}_{10}n)$。

空间复杂度 $O(1)$ 除若干变量使用的常量级空间，没有使用额外的线性空间。

整型解题

题目限制，必须使用 $int$ 存数 。 考虑正数溢出条件， 发生在 $ans\ast 10+x\%10>INT\_MAX$ 的情况下，
推导可得，$ans>\frac{INT\_MAX-x\%10}{10}$ 的情况下，整形溢出。

同理，负数溢出发生在 $ans<\frac{INT\_MIN-x\%10}{10}$ 的情况下。设置边界 ， 本题得解。

class Solution {
public:
    int reverse(int x) {
        int ans = 0;
        while(x){
            if(x>0 && ans > (INT_MAX - x%10)/10) return 0;
            if(x<0 && ans < (INT_MIN - x%10)/10) return 0;
            ans*=10;
            ans +=x%10;
            x/=10;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度 $O(logn)$ ， $n$ 是 $x$ 的大小，时间复杂度 $O(lo{g}_{10}n)$。

空间复杂度 $O(1)$ 除若干变量使用的常量级空间，没有使用额外的线性空间。

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC