0%

[0007] 整数反转

发表于 更新于 分类于 ， 本文字数： 2.8k 阅读时长 ≈ 3 分钟
...

[0007] 整数反转

题目描述

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

示例 1:

输入: 123
输出: 321

 示例 2:

输入: -123
输出: -321

示例 3:

输入: 120
输出: 21

注意:

假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231,  231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

Related Topics
  • 数学

    • 题目解析

    • 本题是一道模拟题，关键是对结果超出int32的情况的判断。

    不确定性

    • 明确末尾为0的情况处理

    方法一：长整形法

    分析

    • 直接利用取模法模拟即可

    思路

    • 先利用取模法计算出结果，存储在长整型 int64中。
    • 再去判断结果是否在int32范围内。

    注意

    • int32 的最大值和最小值分别是 2^31-1(2147483647), -2^31(-2147483648)
    • 考虑负数

    知识点

    • 取模
    • 模拟
    • int32范围
    • 2，16进制表示法

    复杂度

    • 时间复杂度O(1)
    • 空间复杂度O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    typedef long long lld;
    const int IntMax= 0x7fffffff, IntMin = 0x80000000; // c++ 常量 INT32_MAX，INT32_MIN 也表示
    // 0x7fffffff == 2^31-1, 0x80000000 = -2^31, 不明白可以探索二进制资料学习一下。

    class Solution {
        lld getReverseLld(int x) 
        {
            lld res = 0; // 使用长整型防止溢出
            for(;x!=0;x/=10) res = res*10 + x%10;
            return res;
        }

    public:
        int reverse(int x) {
            lld res = getReverseLld(x);
            if (res < IntMin || res > IntMax) return 0;
            return int(res);
        }
    };

    /*
    0
    -123
    1111111111
    123456778
    2147483647
    -2147483648
    2147447412
    -2147447412
    -2147447413
    */

    方法二：数组法

    分析

    • 在上一题基础上加大难度，给出的初始值是int64，那么上方法一就不可以使用了，没有比int64更大的有符号整数了。
    • 为了解决上述变形题型，我们用另一种方法解决本文的题目
    • 题目的难点是在处理边界值，即结果超出int32范围的情况，如果能判出结果超出了范围，那么题目就解决了
    • 初始值是int64的解法请读者自己思考

    思路

    • 首先我们可以知道结果（绝对值）的长度
    • 如果长度小于len(2147483647) = 10，那么肯定不超出范围
    • 再来讨论长度=10的情况
    • 拿结果绝对值与2147483647从高到低逐位比较

    注意

    • 题目输入不可能是8463847412，-8463847412(不在int32范围内)
    • 故也不可能出现翻转后变成2147483648
    • 所以只要拿2147483647与翻转后的数组比较大小即可
    • 出现前导0的情况，这里不影响结果
    • 输入为负数的情况

    知识点

    • 数组
    • 模拟
    • 字符串比较大小

    复杂度

    • 时间复杂度O(1)
    • 空间复杂度O(1)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    //
    class Solution {
        vector<int> MaxArr;
        void initMaxArr()
        {
            for(int i=INT32_MAX;i>0;i/=10) MaxArr.insert(MaxArr.begin(),i%10);
            /*
            for (int i : MaxArr)
            {
                cout<<i<<" ";
            }
            cout<<endl;
            */
        }

        vector<int> getAbsReverseArr(int x)
        {
            vector<int> rArr;
            int sign=1;
            if(x<0)sign=-1;
            // 这里不能用直接取绝对值 x=INT32_MIN 时，-x 会越界
            for (; x!=0 ; x/=10) rArr.push_back(x%10*sign);
            return rArr;
        }

        int arr2Int(vector<int> arr, bool isNeg)
        {
            int res=0;
            for (int n : arr)res = res*10+n;
            return isNeg?-res:res;
        }

        bool isOutOfRange(vector<int> arr)
        {
            if(arr.size()<MaxArr.size())return false;
            int i=0;
            for (i = 0; i < MaxArr.size() && MaxArr[i]==arr[i]; ++i); // 比出第一个不相等的数
            if (i>=MaxArr.size())return false; // 都相等了，没有溢出

            return MaxArr[i]<arr[i]; // 目标数大就是溢出了
        }
    public:
        Solution()
        {
            initMaxArr();
        }

        int reverse(int x) {
            auto rArr = getAbsReverseArr(x);
            if (isOutOfRange(rArr))return 0;
            return arr2Int(rArr, x<0);
        }
    };

    /*
    0
    1111111111
    1000000000
    12303000
    -123
    123456778
    2147483647
    -2147483648
    2147447412
    -2147447412
    -2147447413
    2147447413
    */

    相关题目

    相关文章