LeetCode_#7_整数反转 Reverse Integer_C++题解
程序员文章站
2024-01-27 08:36:40
7. 整数反转 Reverse Integer 题目描述 Given a 32 bit signed integer, reverse digits of an integer. 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 Example 1: Example 2: E ......
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的绑定,进一步加快执行效率。参考:
-