最新消息:

7. Reverse Integer整数反转 (Easy)

算法 ksharpdabu 76浏览 0评论

Given a 32-bit signed integer, reverse digits of an integer.(将一个32位的有符号的整数的进行反转,注意:反转后可能会溢出,如果溢出,则返回0)

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: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

自己的思路:
1.反转,则用取余取出整数的最后一位,然后加上上次得到的值result*10 , 新的a =a *10+ b ;
2.这里题目的关键点是怎么判断是否溢出。我的判断是 a *10+b  如果溢出,则 ((a *10+b)-a) != b 。
java代码:

 

leetcode官方解答:

Solution


Approach 1: Pop and Push Digits & Check before Overflow

Intuition

We can build up the reverse integer one digit at a time. While doing so, we can check beforehand whether or not appending another digit would cause overflow.

Algorithm

Reversing an integer can be done similarly to reversing a string.

We want to repeatedly “pop” the last digit off of xx and “push” it to the back of the rev. In the end, rev will be the reverse of the xx.

To “pop” and “push” digits without the help of some auxiliary stack/array, we can use math.

However, this approach is dangerous, because the statement temp = rev10+pop  can cause overflow.

Luckily, it is easy to check beforehand whether or this statement would cause an overflow.

To explain, lets assume that  rev  is positive.

Similar logic can be applied when  rev is negative.

这里的以java来说:

当X>0:

Integer.MAX_VALUE的值为 2147483647。

如果 temp = rev*10+pop 会溢出,则 rev >=( Integer.MAX_VALUE/10) 。因为pop是个位数,肯定是 0<=pop<=9。此时就需要分两种情况:

当 rev ==( Integer.MAX_VALUE/10) , 即rev == 214748364 ,此时如果 pop>7  ,temp=214748364*10+pop  就会溢出。

当 rev > ( Integer.MAX_VALUE/10) ,此时无论pop等于什么,temp都会溢出。

当X< 0:

Integer.MIN_VALUE的值为-2147483648。

如果 temp = rev*10+pop 会溢出,则 rev <=( Integer.MIN_VALUE/10) 。因为pop是个位数,肯定是 -9<=pop<=0。此时就需要分两种情况:

当 rev ==( Integer.MIN_VALUE/10) , 即rev == -214748364 ,此时如果 pop<-8  ,temp=-214748364*10+pop  就会溢出。

当 rev < ( Integer.MIN_VALUE/10) ,此时无论pop等于什么,temp都会溢出。

Java:

 

 

Complexity Analysis

  • Time Complexity: O(log(x)). There are roughly log10(x) digits in xx.
  • Space Complexity: O(1).
 
其他的解法:
1.有看到用long类型来解决的,这种算作弊了.
2.有的用字符串转Integer的异常来判断溢出,这种相当于用jdk自带的判断溢出的功能,感觉挺有创意的。
 
来源: https://leetcode.com/problems/reverse-integer/solution/

 

转载请注明:大步's Blog » 7. Reverse Integer整数反转 (Easy)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址