首页 > 代码库 > Reverse Integer leetcode java

Reverse Integer leetcode java

题目

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

click to show spoilers.

Have you thought about this?

Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!

If the integer‘s last digit is 0, what should the output be? ie, cases such as 10, 100.

Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?

Throw an exception? Good, but what if throwing an exception is not an option? You would then have to re-design the function (ie, add an extra parameter).

 

题解

 解题思想是: 用一个queue来存当前输入数字从个位开始到最高位的数字。依次取得这些数字的方法是,当前数字对10取余数,然后当前数字减去这个余数再除以10,依次循环处理。并且在这个循环过程中记录位数。在下一步还原时,依据当前位数算出要乘以多少个0,从queue中取出来的数就是从个位开始的数,相当于reverse了。

 

因为取得数字的过程中依据取余,所以符号可以得以保留,并且对于10,100也能保证reverse的正确性。 对于溢出并没有做特殊处理。

代码如下:

 1     public int reverse(int x) {
 2         Queue<Integer> q = new LinkedList<Integer>();
 3         int count = 0;
 4         while(x!=0){
 5          count++;
 6          int r=x%10;
 7          q.add(r);
 8          x=(x-r)/10;
 9          }
10         
11         int nx = 0;
12         for(int i=count;i>0;i--){
13             int temp = q.poll();
14             int j=i;
15             int carry=1;
16             while(j>1){
17             carry=carry*10;
18             j--;
19             }
20             nx = nx+temp*carry;
21         }
22         return nx;
23      }

 然后在网上搜索到Code ganker(http://blog.csdn.net/linhuanmars/article/details/20024837)的解法,

感觉就更加精炼,而且对边界条件(越界问题)考虑的非常巧妙,值得学习。

像他再博文中提到:“这种题的考察重点并不在于问题本身,越是简单的题目越要注意细节,一般来说整数的处理问题要注意的有两点,一点是符号,另一点是整数越界问题

注意Integer.MIN_VALUE的绝对值是比Integer.MAX_VALUE大1的,所以经常要单独处理。

代码如下:

 1 public int reverse(int x) {
 2     if(x==Integer.MIN_VALUE)
 3         return Integer.MIN_VALUE;
 4     int num = Math.abs(x);
 5     int res = 0;
 6     while(num!=0){
 7         if(res>(Integer.MAX_VALUE-num%10)/10)//非常巧妙的判断了越界问题
 8             return x>0?Integer.MAX_VALUE:Integer.MIN_VALUE;
 9         res = res*10+num%10;
10         num /= 10;
11     }
12     return x>0?res:-res;
13 }