BAT面试算法进阶(7)- 反转整数

小编温馨提示,今天是我们坚持的第7天! 今天休息日,降低了些难度.让大家轻松的放假也能学习哦

一.题目

给定一个 32 位有符号整数，将整数中的数字进行反转。

• 例如:

输入: 123
输出: 321

输入: 120
输出: 21

输入: -123
输出: -321

• 注意
  

假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。根据这个假设，如果反转后的整数溢出，则返回 0。

二.解决方案

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

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

3.算法
反转整数可以和反转字符串一起类比实现.
在没有辅助的堆栈/数组的帮助下,'弹出'和'推入'数字,可以尝试有用数学的方式.

但是,当因为当 temp = rev*10+pop时,有可能会造成溢出.

4.解决溢出

• 假设rev,为正数

• 如果temp = rev*10+pop,导致溢出.那么一定rev >= INTMAX/10;

• 如果rev > INTMAX / 10;那么temp = rev*10+pop 一定会溢出

• 如果rev == INTMAX / 10,那么只要pop > 7 ,temp = rev*10+pop 就会溢出

三.代码实现
C++ Code

四.复杂度

• 时间复杂度:O(log(x))

• 空间复杂度:O(1)

小编OS:

如有疑问,留言即可.胖C会利用空余时间给大家做一个简单解答的.
持续更新关注公众号!