題目

https://leetcode-cn.com/problems/reverse-integer/

公眾號 《java編程手記》記錄JAVA學(xué)習(xí)日常，分享學(xué)習(xí)路上點點滴滴，從入門到放棄，歡迎關(guān)注

描述

給你一個 32 位的有符號整數(shù) x ，返回將 x 中的數(shù)字部分反轉(zhuǎn)后的結(jié)果。

如果反轉(zhuǎn)后整數(shù)超過 32 位的有符號整數(shù)的范圍 [?231, 231 ? 1] ，就返回 0

假設(shè)環(huán)境不允許存儲 64 位整數(shù)（有符號或無符號）

示例 1：

輸入：x = 123
輸出：321
示例 2：

輸入：x = -123
輸出：-321
示例 3：

輸入：x = 120
輸出：21
示例 4：

輸入：x = 0
輸出：0

Solution

解法

解題思路

反轉(zhuǎn)整數(shù)的思路有哪些？

• 把整數(shù)變成字符串，再反轉(zhuǎn)字符串，再轉(zhuǎn)換整形，判斷邊界問題
• 通過棧數(shù)據(jù)結(jié)構(gòu)，先從整數(shù)的尾部依次入棧，再出棧組合成新的數(shù)字

第一種整數(shù)變字符串，然后反轉(zhuǎn)這種就不做介紹了，我們主要以棧結(jié)構(gòu)這種思路來解題，這里我們不需要使用棧的數(shù)據(jù)結(jié)構(gòu)，將整數(shù)的尾部依次取出，然后拼接到新的數(shù)字即可，如下圖所示，通過取模拿到最后一位的結(jié)果數(shù)據(jù)，再依次拼接到最終的結(jié)果上即可，每次的結(jié)果就等于 res = res*10 + x%10,當(dāng)最后x的值為0 ，則整體運算結(jié)束，最后判斷是否超越邊界即可

image-20210411212913523

CODE

class Solution {
    public int reverse(int x) {
        long result = 0;
        long absX = Math.abs (x);
        while (absX != 0) {
            long pop = absX % 10; //取到3
            absX = absX / 10;    //去掉3
            result = result * 10 + pop;  //返回值
        }
        //1 << 31 是 -2147483648 ， (1 << 31) - 1 是 2147483647
        if (result <= 1 << 31 || result > (1 << 31) - 1) {
            return 0;
        }
        if (x > 0) {
            return (int) num;
        }
        if (x < 0) {
            return (int) -num;
        }
        return 0;
    }
}

復(fù)雜度

• 時間復(fù)雜度：O(log(x))，x 中大約有 log 10(x) 位數(shù)字
• 空間復(fù)雜度：O(1)

結(jié)果

• 執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶

• 內(nèi)存消耗：35.6 MB, 在所有 Java 提交中擊敗了55.86%的用戶

簡潔版本

解題思路

跟上面的思路差不多，唯一區(qū)別在于判斷越界的地方，當(dāng)新生成的結(jié)果last != res/10時，則說明整數(shù)溢出

CODE

class Solution {
    public int reverse(int x) {
        int res = 0;
        int last = 0;
        while(x!=0) {
            //每次取末尾數(shù)字
            int tmp = x%10;
            last = res;
            res = res*10 + tmp;
            //判斷整數(shù)溢出
            if(last != res/10)
            {
                return 0;
            }
            x /= 10;
        }
        return res;
    }
}

復(fù)雜度

• 時間復(fù)雜度：O(log(x))，x 中大約有 log 10(x) 位數(shù)字
• 空間復(fù)雜度：O(1)

結(jié)果

• 執(zhí)行用時：1 ms, 在所有 Java 提交中擊敗了100.00%的用戶

• 內(nèi)存消耗：35.3 MB, 在所有 Java 提交中擊敗了91.96%的用戶