LeetCode7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

1
2
Input: 123
Output: 321

Example 2:

1
2
Input: -123
Output: -321

Example 3:

1
2
Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.


stack + overflow

1

Complexity Analysis

  • Time Complexity: O(log⁡(x)). There are roughly log⁡10(x) digits in x .
  • Space Complexity: O(1)

my code in cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int reverse(int x) {
int ret = 0;
while (x)
{
//pop
int pop = x % 10;
x /= 10;

//positive overflow
if (ret > INT_MAX/10 || ret == INT_MAX/10 && pop > 7)//1.
return 0;

//negative overflow
if (ret < INT_MIN/10 || ret == INT_MIN/10 && pop > 8)
return 0;

//push
ret = ret * 10 + pop;
}
return ret;
}

细节

  1. ret > INT_MAX/10 不能写成ret*10>INT_MAX。否则报错。
1
signed integer overflow: 964632435 * 10 cannot be represented in type 'int'
  1. 注意INT_MAX(2147483647)和INT_MIN(-2147483647 - 1)的值。

总结

  1. 翻转整数用到stack的思想,back就是取模,pop就是求商,push就是ret*10+pop
  2. 另外还要注意overflow的问题,判断正数溢出和负数溢出的问题。(记一下2147483647,情人节吃屎吧36个人拿着ak47.)
Thanks for Support.