☆打卡算法☆LeetCode 7、整数反转 算法解析
> 推荐阅读
>
> - CSDN主页
> - GitHub开源地址
>- Unity3D插件分享
> - 简书地址
> - 我的个人博客
> - QQ群:1040082875
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
## 一、题目
### 1、算法题目
“将给定的整数进行反转输出。”
题目链接:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-integer/
### 2、题目描述
将一个32位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过32位的有符号整数的范围 [-231,231 - 1] 就返回0.
假设环境不允许存储64位整数(有符号或无符号)。
比如:
> 输入:x = 123
> 输出:321
> 输入:x = -123
> 输出:-321
> 输入:x = 120
> 输出:21
## 二、解题
### 1、思路分析
这道题如果不考虑数据溢出的问题,是非常简单的,可以在一层循环中使用取模运算拿到末尾数字即可。
>比如123:
1)将123
% 10
得到 3
,之后将 123
/ 10
2)将12
% 10
得到 2
,之后将 12
/ 10
3)将1
% 10
得到 1
,再将 1
/ 10
有了取模和除法操作,对于像12300
这样的数字,也可以完美的解决掉了。
接下来要考虑数据溢出的问题,转化后的整数取值范围为[-231,231 - 1],不满足返回0。
溢出条件有两个,一个是大于整数最大值MAX_VALUE,另一个是小于整数最小值MIN_VALUE,设当前计算结果为digit,下一位为rev。
- 从digit * 10 + rev > MAX_VALUE这个溢出条件来看
当出现 digit > MAX_VALUE / 10 且 还有rev需要添加 时,则一定溢出
当出现 digit == MAX_VALUE / 10 且 rev > 7 时,则一定溢出,7是2^31 - 1的个位数
- 从digit * 10 + pop < MIN_VALUE这个溢出条件来看
当出现 digit < MIN_VALUE / 10 且 还有rev需要添加 时,则一定溢出
当出现 digit == MIN_VALUE / 10 且 rev < -8 时,则一定溢出,8是-2^31的个位数
### 2、代码实现
从左到右迭代字符串s,将每个字符添加到合适的行,使用当前行和当前方向这两个变量对合适的行进行比较。
只有当向上移动到最上面的行或向下移动到最下面的行时,当前方向发生改变。
```csharp
public class Solution
{
public int Reverse(int x)
{
int rev = 0;
while (x != 0)
{
if (rev < int.MinValue / 10 || rev > int.MaxValue / 10)
{
return 0;
}
int digit = x % 10;
x /= 10;
rev = rev * 10 + digit;
}
return rev;
}
}
```
执行结果:
### 3、时间复杂度
时间复杂度: O(log∣x∣)
翻转的次数即 x 十进制的位数。
空间复杂度: O(1)
有常数级个变量,所以空间复杂度为O(1)。
## 三、总结
小于2^31的10位数,首位只能是1或2,反转过来末位是1或2,小于7。
如果大于7,输入就溢出了。所以不用考虑末位的7和-8,只要保证其余9位满足条件就行。
- 点赞
- 收藏
- 关注作者
评论(0)