ReverseInteger [source code]

public class ReverseInteger {
static
/******************************************************************************/
public class Solution {
    public int reverse(int x) {
        if (x == 0 || x == Integer.MIN_VALUE) return 0;
        if (x < 0) return -reverse(-x);
        int[] maxDigits = new int[10];
        int max = Integer.MAX_VALUE, i;
        for (i = 0; i < 10; i++, max /= 10) {
            maxDigits[i] = max % 10;
        }
        int[] digits = new int[10];
        for (i = 0; i < 10 && x > 0; i++, x /= 10) {
            digits[i] = x % 10;
        }
        if (i == 10) {
            for (int j = 0; j < 10; j++) {
                if (maxDigits[9 - j] < digits[j]) return 0;
                if (maxDigits[9 - j] > digits[j]) break;
            }
        }
        int sum = 0;
        for (int j = 0; j < i; j++) {
            if (digits[j] == 0 && sum == 0) continue;
            sum = sum * 10 + digits[j];
        }
        return sum;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        ReverseInteger.Solution tester = new ReverseInteger.Solution();
        int[] inputs = {
            123, 321,
            -123, -321,
            -2147483648, 0,
            1534236469, 0,
            -2147483412, -2143847412,
            2147483412, 2143847412,
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int x = inputs[2 * i];
            int expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            int output = tester.reverse(x);
            System.out.println(Printer.wrapColor(x + "", "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, (output == expected ? "green" : "red")));
        }
    }
}

首先考虑一下, 负数是不会溢出的, 从-MIN开始考虑, 可以发现负数reverse之后肯定是没有问题的;

这题好像可以用string来做? 就是感觉有点cheat;
真正面试的时候你就算用这个做, 估计都可能被面试官要求给出一个其他的纯粹用array的做法;

java> Integer.MIN_VALUE  
java.lang.Integer res0 = -2147483648

感觉这个值还是要记一下;

这个题整体的核心思路其实还是比较简单的, 就是要处理好几个坑, 比如trailing zeroes, 还有溢出的情况. 这些也是一个值得锻炼的基本功; 最后的速度是40ms (69%), 比较中庸, 这个有点奇怪;

最后一段组合的地方换成了用StringBuilder来做, 速度反而慢了5ms;
那估计这个算法的速度也是就这样了, 没办法了;

这个是discussion最优解:

public int reverse(int x)  
{  
    int result = 0;  

    while (x != 0)  
    {  
        int tail = x % 10;  
        int newResult = result * 10 + tail;  
        if ((newResult - tail) / 10 != result)  
        { return 0; }  
        result = newResult;  
        x = x / 10;  
    }  

    return result;  
}

这个想法其实是挺聪明的; 首先他这个还是跟很多人的这类reverse int的问题一样的思路, 不像我这样用array, 而是直接就一个buffer, x吐出来一个digit, result就加进去一个; 这个是reverse最常见的一个思路了其实现在, 我这个全都disassemble的思路其实才是比较奇葩的;
他这个思路还有一个好处就是根本不用判断trailing0, 因为在你将这些0作为leading0加给result的时候, 自动就被处理了;

至于overflow的处理, 他这里的这个想法也挺好的. 所谓加或者乘或者lshift的过程中产生overflow, 就是左边的一些bit被出界然后就消失了, 这个可以说是 dictionary definition. 他这里就是利用这个definition来直接判断overflow: 先给你增大, 然后再缩小回来, 如果没有变化, 说明就没有disappeared bits, 也就没有overflow;

这个跟我的思路还是有差别的, 我的思路就是很直白的, 直接根据int的range来进行一个大小比较, 在range以内的就不会overflow. 相比之下, 他的这个做法其实更加general, 而且处理起来实际上要考虑的东西反而比我这个要考虑的东西要少: 我这个看range的方法, 正负, 上界和下界全都要枚举考虑;

这个是一个类似的思路:

public int reverse(int x) {  
    long rev= 0;  
    while( x != 0){  
        rev= rev*10 + x % 10;  
        x= x/10;  
        if( rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE)  
            return 0;  
    }  
    return (int) rev;  
}

每产生一个新的大值(每次rev被增加), 我们就检查是否超界. 注意要让这个方法奏效, rev必须用long, 只有这样, 你拿一个超界的rev跟int的最值进行比较才有意义;

注意他们这帮人的做法全都是, 如果是负数还是直接按着做的; 好像如果正负区分对待速度能稍微快一点;

不过我试验了一下:

java> -123 / 10  
java.lang.Integer res0 = -12  
java> -123 % 10  
java.lang.Integer res1 = -3

感觉好像JAVA这些类C的语言都是这样, 并不是真的就是考虑了负号, 看这里的这个计算过程, 好像其实也是直接把负号先单独拎出来, 然后计算正数(绝对值)部分的除法或者mod, 然后重新把负号给attach上去一样; 所以背后的原理其实是一样的;

当然我写这个代码的时候还不知道这么回事, 本能上就感觉还是正负分开讨论最后做起来会方便一些, 这么思考其实也是没有问题的;

翻了几个submission的最优解, 其实好像最后的速度都差不多在40ms左右. 感觉还是题目太老了, 所以以前的很多当时submit的时候快而已;

Problem Description

Reverse digits of an integer.

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

click to show spoilers.

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

Difficulty:Easy
Total Accepted:261.1K
Total Submissions:1.1M
Contributor: LeetCode
Companies
bloomberg apple
Related Topics
math
Similar Questions
String to Integer (atoi)

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.