image

很簡單，就是輸入整數(shù)，輸出它的倒置。

第一反應(yīng)就是， 取余得到個位數(shù)，然后除以 10 去掉個位數(shù)，然后用一個變量保存倒置的數(shù)。

public int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        int pop = x % 10;
        x /= 10;
        rev = rev * 10 + pop;
    }
    return rev;
}

然后似乎不是那么理想。

為什么呢？倒置過來不應(yīng)該是 9646324351 嗎。其實題目里講了，int 的范圍是 也就是 [-2147483648,2147483647] 。明顯 9646324351 超出了范圍，造成了溢出。所以我們需要在輸出前，判斷是否溢出。

問題的關(guān)鍵就是下邊的一句了。

rev = rev * 10 + pop;

為了區(qū)分兩個 rev ，更好的說明，我們引入 temp 。

temp = rev * 10 + pop;
rev = temp;

我們對 temp = rev * 10 + pop; 進行討論。intMAX = 2147483647, intMin = - 2147483648。

對于大于 intMax 的討論，此時 x 一定是正數(shù)，pop 也是正數(shù)。

• 如果 rev > intMax / 10 ，那么沒的說，此時肯定溢出了。
• 如果 rev == intMax / 10 = 2147483647 / 10 = 214748364，此時 rev * 10 就是 2147483640 如果 pop 大于 7 ，那么就一定溢出了。但是！如果假設(shè) pop 等于 8，那么意味著原數(shù) x 是 8463847412 了，輸入的是 int ，而此時是溢出的狀態(tài)，所以不可能輸入，所以意味著 pop 不可能大于 7 ，也就意味著 rev == intMax / 10 時不會造成溢出。
• 如果 rev < intMax / 10，意味著 rev 最大是 214748363 ， rev * 10 就是 2147483630 , 此時再加上 pop ，一定不會溢出。

對于小于 intMin 的討論同理。

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

時間復(fù)雜度：循環(huán)多少次呢？數(shù)字有多少位，就循環(huán)多少次，也就是 次，所以時間復(fù)雜度是 O (log (x))。

空間復(fù)雜度：O (1)。

當(dāng)然我們可以不用思考那么多，用一種偷懶的方式 AC ，我們直接把 rev 定義成 long ，然后輸出前判斷 rev 是不是在范圍內(nèi)，不在的話直接輸出 0 。

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

總結(jié)

比較簡單的一道題，主要是在考判斷是不是溢出。