LeetCode_#7_整数反转 Reverse Integer_C++题解

7. 整数反转 reverse integer

题目描述

given a 32-bit signed integer, reverse digits of an integer.

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

example 1:

input: 123
output: 321

example 2:

input: -123
output: -321

example 3:

input: 120
output: 21

note:
assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. for the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

注意：假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为[\(-2^{31}\),\(2^{31}-1\)]。请根据这个假设，如果反转后整数溢出那么就返回 0。

官方题解_检测溢出

class solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0){
            int pop = 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;
            x = x / 10;
        }
        return rev;
    }
};

• 时间复杂度：\(o(\log(x))\)，x中大约有 \(\log_{10}(x)\) 位数字。
• 空间复杂度：\(o(1)\)。

参考样例题解_long存储+加速

static const auto speedup = []{
    ios::sync_with_stdio(false);
    cin.tie(null);
    return 0;
}();
class solution {
public:
    int reverse(int x) {
        long long rev = 0;
        while (x != 0){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return (rev > int_max || rev < int_min) ? 0 : rev;
    }
};

• 直接用更大范围的long来存储，得到结果后再判断是否超过int的范围（感觉不太符合题意但确实可以通过）
• 在执行用时最短的范例中看到了如上speedup函数，提交测试以后发现此函数确实可以大幅减少执行用时。
  • ios::sync_with_stdio(false); iostream默认是与stdio关联在一起的，以使两者同步，因此消耗了iostream不少性能，设置为false后，不再同步了，iostream的性能提高了很多倍。但关闭后cin不能和scanf，sscanf, getchar, fgets之类同时用了，否则就可能会导致输出和预期的不一样。

  • cin.tie(null);在默认的情况下cin绑定的是cout，每次执行 << 操作符的时候都要调用flush，这样会增加io负担。可以通过tie(0)（0表示null）来解除cin与cout的绑定，进一步加快执行效率。

    参考：