大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
“将给定的整数进行反转输出。”
题目链接: 来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/reverse-integer/
将一个32位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过32位的有符号整数的范围 [-231,231 - 1] 就返回0.
假设环境不允许存储64位整数(有符号或无符号)。
比如:
输入:x = 123 输出:321
输入:x = -123 输出:-321
输入:x = 120 输出:21
这道题如果不考虑数据溢出的问题,是非常简单的,可以在一层循环中使用取模运算拿到末尾数字即可。
比如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。
从左到右迭代字符串s,将每个字符添加到合适的行,使用当前行和当前方向这两个变量对合适的行进行比较。
只有当向上移动到最上面的行或向下移动到最下面的行时,当前方向发生改变。
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;
}
}
执行结果:
时间复杂度: O(log∣x∣)
翻转的次数即 x 十进制的位数。
空间复杂度: O(1)
有常数级个变量,所以空间复杂度为O(1)。
小于2^31的10位数,首位只能是1或2,反转过来末位是1或2,小于7。
如果大于7,输入就溢出了。所以不用考虑末位的7和-8,只要保证其余9位满足条件就行。