设为首页 加入收藏

TOP

LeetCode_#7_整数反转 Reverse Integer_C++题解
2019-03-13 16:08:10 】 浏览:12
Tags: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)\)

image

参考样例题解_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的绑定,进一步加快执行效率。

      参考:cin.tie与sync_with_stdio加速输入输出


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇关于类的几点说明 下一篇Linux CentOS 7 下的C++ 学习笔记..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }