整数反转

题目地址

题目名称:两数之和

难度:

题目描述:

给出一个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数字的同时推入到反转整数的后面,又学到了,再接再厉吧😛。

Donate
  • Copyright: Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020 John Doe
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信