【LeetCode】7、Reverse Integer（整数反转）

题目等级：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

题意：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

解题思路：

本题很简单，我们给出以下两种方法。

解法一：转为字符串

由于之前我们大都做过如何反转字符串的题目，因此我们可以将整数转为字符串，通过字符串的反转来实现整数的反转，整数转字符串String.valueOf(num)，字符串转整数Integer.parseInt(str)。

这样的做法也很简单，但是实际上没有必要，因为直接完成整数的反转也比较简单。

class Solution {

    public int reverse(int x) {

        String s=String.valueOf(x);

        if(x<0)

            s=s.substring(1);

        StringBuffer strBuf = new StringBuffer(s);

        String str=strBuf.reverse().toString();

        try{

            return x>0 ? Integer.parseInt(str) : -1*Integer.parseInt(str);

        }catch(NumberFormatException e){

            return 0;

        }

    }

}

解法二：弹出和压入数字

通过pop = x % 10，取出末尾数字，然后除以 10 去掉个位数，然后用一个变量保存倒置的数。这个想法也很容易理解，但是这里的重点是如何防止溢出。

需要知道的是:int的范围是【-2147483648,2147483647】，也就是最大能表示的数大概是20亿左右，因此在反转的过程中，我们需要进行判断，是否溢出，如果溢出则返回0。

具体过程参考如下代码：

class Solution {

    public int reverse(int x) {

        int res=0;

        while(x!=0){

            int temp=x%10;

            x=x/10;

            if (res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE / 10&&temp > 7)) return 0;

            if (res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE / 10&&temp< -8)) return 0;

            res=res*10+temp;

        }

        return res;

    }

}

实际上，这里的溢出判断略显复杂，可以用一种比较简单的方法：将反转后的数设置为long类型，然后在反转完成后，与int最大值和最小值进行比较，溢出则返回0。

public int reverse(int x) {

    long res = 0;

    while (x != 0) {

        int temp = x % 10;

        x /= 10;

        res = res * 10 + temp;

    }

    if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE )

        return 0;

    return (int)res;

}

时间复杂度：有多少位就循环多少次，所以是lg(n)，即以10为底，时间复杂度O（lgn）

空间复杂度：O(1)

总结：

本题比较简单，思路不难想到，但是重点在于能否考虑到溢出，并正确的对溢出情况进行处理。

从本题开始，由于感觉顺序刷题难度较大，转变一下刷题顺序，先刷easy难度的题。

巴特西

【LeetCode】7、Reverse Integer（整数反转）

题目等级：Easy

题目描述：

解题思路：

最新文章

热门文章