CTF of Z2BNS
0%

整数反转

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目地址

题目名称：两数之和

难度：⭐

题目描述：

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

示例1：

1
2
输入：123
输出：321

示例2：

1
2
输入：-123
输出：-321

示例3：

1
2
输入：120
输出：21

注意：

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

🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

下面是自己提交通过的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int reverse(int x) {
        int i=0;//i是整数x的10进制位数
        long rev=0;//一定要初始化，long类型8字节反转后不会超出范围
        vector<int> values{};//存储10进制整数x的每一位
        do
        {
            values.push_back(x%10);//3 2 1
            x=x/10;//12 1 0
        }while(x!=0);
        i=values.size();//整数x的10进制位数
        //求反转后的数值
        for(int k=0;k<i;k++){
            rev+=values[k]*pow(10,i-k-1);
        }
        //反转后整数溢出
        if(abs(rev)>2147483648){
            rev=0;
        }
        return rev;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解：

方法：弹出和推入数字 & 溢出前进行检查
思路

我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。

算法

反转整数的方法可以与反转字符串进行类比。

我们想重复“弹出” xx 的最后一位数字，并将它“推入”到 rev 的后面。最后，rev将与x 相反。

要在没有辅助堆栈 / 数组的帮助下 “弹出” 和 “推入” 数字，我们可以使用数学方法。

1
2
3
4
5
6
7
//pop operation:
pop = x % 10;
x /= 10;

//push operation:
temp = rev * 10 + pop;
rev = temp;

但是，这种方法很危险，因为当$temp=rev·10+pop$ 时会导致溢出。

幸运的是，事先检查这个语句是否会导致溢出很容易。

为了便于解释，我们假设 rev 是正数。

  1. 如果$temp=rev·10+pop$导致溢出，那么一定有$rev\geqq\frac{INTMAX}{10}$。
  2. 如果$rev\geqq\frac{INTMAX}{10}$，那么$temp=rev·10+pop$一定会溢出。
  3. 如果$rev\geqq\frac{INTMAX}{10}$，那么只要pop>7，$temp=rev·10+pop$就会溢出。

当rev为负时可以应用类似的逻辑。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            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;
        }
        return rev;
    }
};

复杂度分析

  • 时间复杂度：$O(log(x))$，x中大约有$ \log_{10}(x)$位数字。
  • 空间复杂度：$O(1)$。
🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓知 识 点🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓🎓
知识点：

1、数据在计算机中的存储:

机器数：一个数在计算机中的表现形式叫做机器数，这个数有正负之分，在计算机中用一个数的最高位（符号位）表示它的正负，其中0表示正数，1表示负数。

真数：计算机中的机器数对应的真实的值就是真数，对最高位（符号位）后面的二进制转换成10进制，并根据最高位来确定这个数的正负。

原码：符号位加上真数的绝对值，第一位表示符号，其余位表示值。

反码：正数的反码是其本身；负数的反码是在原码的基础上，符号位不变，其余各位取反。

补码：正数的补码就是其本身；负数的补码是在其原码的基础上，符号位不变其余各位取反最后加1（即在反码的基础上加1）。

2、问题：原码是被人脑直接识别并用于计算的表达方式，为何还会有反码和补码呢？？？👀

  • 人脑很容易可以知道第一位是符号位，而对于计算机而言，辨别“符号位”基础电路设计会变得十分复杂，于是人们考虑将符号位也参与运算并且只保留加法，减去一个数等于加上它的负数。

  • 若用原码表示，让符号位也参与运算，能满足正数的加法，但无法满足负数的加法结果不正确。若用反码计算减法，会有[0000 0000]原、[1000 0000]原两个编码表示0。若用补码表示，可以用[0000 0000]原表示0，不但解决了0的两个编码问题，而且可以用[1000 0000]补表示-128，注意：因为实际上是使用以前-0的补码来表示，所以-128并没有原码和反码表示。

  • 使用补码不仅修复了0的符号以及存在两个编码的问题且还能多表示一个最低数，这就是为什么8位二进制使用源码或反码表示的范围为[-127,+127]，而使用补码表示范围为[-128,127]。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

反转之后的整数，我是在do where循环外面利用for循累加起来的，没有想到在do where循环里面可以直接在弹出x数字的同时推入到反转整数的后面，又学到了，再接再厉吧😛。

------------- THE END! THANKS! -------------