7. Reverse Integer

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?

For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

Show Company Tags
Show Tags
Show Similar Problems

Solution 1 题解:
解题思想是: 用一个queue来存当前输入数字从个位开始到最高位的数字。依次取得这些数字的方法是,当前数字对10取余数,然后当前数字减去这个余数再除以10,依次循环处理。并且在这个循环过程中记录位数。在下一步还原时,依据当前位数算出要乘以多少个0,从queue中取出来的数就是从个位开始的数,相当于reverse了。
因为取得数字的过程中依据取余,所以符号可以得以保留,并且对于10,100也能保证reverse的正确性。 对于溢出并没有做特殊处理。

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

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

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

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

public class Solution {
    public int reverse(int x) {
        if (x == Integer.MIN_VALUE) {
            return 0;
        }
        int result = 0;
        int num = Math.abs(x);
        while (num != 0) {
            if (result > (Integer.MAX_VALUE - num % 10) / 10) {
                return 0;
            }
            // Not +=, rather "result ="
            result = result * 10 + num % 10;
            num = num / 10;
        }
        return x > 0 ? result : -result;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s