LeetCode-7.整数反转 取模反转法与字符串法-阿里云开发者社区

开发者社区> 开发与运维> 正文

LeetCode-7.整数反转 取模反转法与字符串法

简介: 给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。 示例 1: 输入: 123 输出: 321 示例 2: 输入: -123 输出: -321 示例 3: 输入: 120 输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−2\^31, 2\^31 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-integer 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注

看到题目,会觉得很简单,相信大家肯定都遇到过这种题,但是本题唯一的难点在于溢出的判断。

我想了两种办法,一种是常规的取模反转,另一种是字符串法。

方法一(取模反转法):
如果使用这个方法,我们要知道题目所给的数值范围:2^31-1=2147483647,-2^31=-2147483648

接下来我们只要找到溢出条件:取模到极限值的最后一位时的判断,详见下方代码注释。

#include <iostream>
using namespace std;

/**
 * LeetCode
 * 7. 整数反转 - 取模反转法
 * https://space.bilibili.com/54183978
 */

class Solution {
public:
    int reverse(int x) {
       int ans = 0;
       while(x != 0){
           int tem = x % 10;
           // ans大于214748364 或者 ans=214748364且最后一位大于7
           if( ans > INT_MAX / 10 || (ans == INT_MAX / 10 && tem > 7)) return 0;
           // ans小于214748364 或者 ans=214748364且最后一位小于-8
           if( ans < INT_MIN / 10 || (ans == INT_MIN / 10 && tem < -8)) return 0;
           ans = ans*10 + tem;
           x = x / 10;
       }
        return ans;
    }
};

int main(){
    Solution solution;
    cout << solution.reverse(-123);
}

测评结果:
1032 / 1032 个通过测试用例
状态:通过
执行用时: 4 ms
内存消耗: 5.8 MB

方法二(字符串法):
这个方法会比较低效,其核心思想是对整数取模,每位取出来的数字转成字符,拼接到新的字符串上实现反转。然后利用C++的异常捕捉机制来判断是否运算溢出。

这里要知道C++中的int和string互转的方法:
int转string:to_string
string转int:stoi

/**
 * LeetCode
 * 7. 整数反转 - 字符串方法(效率很低)
 * https://space.bilibili.com/54183978
 */

class Solution {
public:
    int reverse(int x) {
        string ans = "";
        int flag = 0;
        if(x < 0){
            flag = 1;
            ans = "-";
        }
        while(x!=0){
            if(flag){
                // to_string:int转string
                ans = ans + to_string(-(x%10));
            } else{
                ans = ans + to_string(x%10);
            }
            x /= 10;
        }
        try{
            // string转int
            return stoi(ans);
        } catch (std::invalid_argument) {
            return 0;
        } catch (std::out_of_range&) {
            return 0;
        }
    }
};

int main(){
    Solution solution;
    cout << solution.reverse(-123);
}

测评结果:
20200918220923946.png

(其实结果不是很准,第一次跑貌似用时和消耗都只击败了百分之几的用户,仅供参考!)

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章