[LeetCode] 007. Reverse Integer
-
date_range Mar. 28, 2019 - Thursday info
Problem (Easy)
Given a 32-bit signed integer, reverse digits of an integer.
Example 1:
- Input: 123
- Output: 321
Example 2:
- Input: -123
- Output: -321
Example 3:
- 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.
Approach 1: Manipulate Strings
Idea
Manipulate the number as string, which is easy to reverse. Then cast integer type to the reversed string.
Solution
class Solution1:
def reverse(self, x: int) -> int:
l = str(x).split('-')
if len(l) > 1:
sign = '-'
else:
sign = ''
rev = l[-1][::-1]
while rev[0] == '0' and len(rev) > 1:
rev = rev[1:]
res = int(''.join([sign, rev]))
if ret > pow(2, 31)-1 or ret < -pow(2, 31):
return 0
return ret
Complexity
- Time: $O(\log(x))$
- Space: $O(1)$?
Approach 1 Update
Hint
int('00012') -> 12
Solution
class Solution1_update:
def reverse(self, x: int) -> int:
rev = str(abs(x))[::-1]
sign = '' if x > 0 else '-'
ret = int(''.join([sign, rev]))
if ret > pow(2, 31)-1 or ret < -pow(2, 31):
return 0
return ret
Approach 2
Idea
Numeric manipulation: reverse the number digit by digit from right. Basic procedure:
- Get the rightmost digit by
digit = x % 10
; - Save the right most digit to
ret += digit
; - Remove this rightmost digit from
x
byx //= 10
; - In the next loop, let the
x
’s digit to left by one bit byret *= 10
; - Loop until
x
reaches 0.
Solution
class Solution2:
def reverse(self, x: int) -> int:
n = x if x > 0 else -x
ret = 0
while n != 0:
ret *= 10
ret += n % 10
n //= 10
ret = ret if x > 0 else -ret
if ret > pow(2, 31)-1 or ret < -pow(2, 31):
return 0
return ret
Complexity
- Time: $O(\log(x))$
- Space: $O(1)$?
KF