[LeetCode][C++] 只用 int 來實作 #7 Reverse Integer

- 5月 22, 2021

我知道很多人都用 string 或 long 來做這題，雖然很簡單卻沒辦法學到這題的關鍵。

LeetCode 官方解答用了一個很 tricky 的方式偵測 overflow/underflow 恐怕也不是很通用的解。

題目的關鍵

把數字反轉根本不是重點，如果我真的要反轉數字我這樣寫就好了:


class Solution {
 public:
  int reverse(int x) {
    int output = 0;
    while (x != 0) {
      const int digit = x % 10;
      output *= 10;
      output += digit;
      x /= 10;
    }
    return output;
  }
};

結束?

但題目希望你單純用 int 來解，而且如果結果超出 int 範圍又要 return 0，這代表我們只能用 int 來偵測甚麼時候數字會超出 int 範圍。

先了解一下 C++ Overflow/Underflow 會發生什麼事?

這就跟用什麼語言來寫非常有關係了，所以我查了一下看到這個 StackOverflow 解答才知道原來 C++ 在執行像是 a + b 如果超出範圍的話 (overflow) 什麼狀況都有可能發生 (undefined behavior)，意味這程式已經沒救了，比 crash 還糟糕因為 a + b 有可能是任何數字。

C++ compiler 其實還有內建的 overflow 檢查像是 __builtin_add_overflow 來偵測什麼時候 overflow，不過我們為了學到點什麼當然不能拿來作弊。

那我們到底要怎麼偵測 a + b 會不會爆掉? 我們只要會數學的移項就好了。

移項

我們今天想偵測 a + b 是不是大於 int 最大值 (overflow)，或偵測 a + b 是不是小於 int 最小值 (underflow)，我們想知道會不會爆掉就這樣寫:


return (a + b) > INT_MAX; // overflow
return (a + b) < INT_MIN; // underflow

很可惜 C++ 在做左邊的 a + b 時早就爆了，這時我們就可以很聰明的把其中一項移到右邊去:


return a > (INT_MAX - b); // overflow
return a < (INT_MIN - b); // underflow

這樣左邊就不可能爆掉，可是你會發現右邊在 b 是正數的時候會讓第二行爆掉，b 是負數的又會讓第一行爆掉，所以我們要先判斷一下 b 是正的還是負的:


if (b > 0) return a > (INT_MAX - b); // overflow
if (b < 0) return a < (INT_MIN - b); // underflow

這樣右邊括號裡就不可能爆掉，同時我們又有能力去判斷如果真的做了 a + b 會不會造成爆掉。

減法、乘法、除法也是玩類似的移項遊戲，詳細的就請參考這個 StackOverflow 解答 (小心他乘法沒考慮到負數的狀況，所以其實有一點 flawed)。

萬用解法

如果我們做一個 safeAdd() 和 safeMultiply() 來嘗試做加法和乘法，失敗就回傳 false，成功回傳 true，我們就可以拿來做任何題目，也不怕被面試時不知道該如何說:


#include <climits>

class Solution {
 public:
  int reverse(int x) {
    int output = 0;
    while (x != 0) {
      const int digit = x % 10;
      if (!safeMultiply(output, 10, output /*out*/)) return 0;
      if (!safeAdd(output, digit, output /*out*/)) return 0;
      x /= 10;
    }
    return output;
  }

  bool safeMultiply(const int a, const int x, int &out) {
    // Does a * x > INT_MAX ?
    if (a > INT_MAX / x) return false;
    // Does a * x < INT_MIN ?
    if (a < INT_MIN / x) return false;
    out = a * x;
    return true;
  }

  bool safeAdd(const int a, const int x, int &out) {
    // Does a + x > INT_MAX ?
    if (x > 0 && a > INT_MAX - x) return false;
    // Does a + x < INT_MIN ?
    if (x < 0 && a < INT_MIN - x) return false;
    out = a + x;
    return true;
  }
};

基本上就是這篇文章一開始的 code 把加法和乘法的地方換掉而已。

只針對這題的解法

其實唯一有機會爆掉的運算就只有 a * 10 + b 這個動作，我們可以只做一個 safe function 來檢查會不會爆掉嗎?

掌握了移項的原理之後，我們只要做幾件事就可以寫任何 safe function 了:

把會爆掉的運算移項到另外一邊
把還是有機會爆掉的東西加上 if 確保沒有運算會爆掉
如果式子很複雜，一步一步檢查會不會有東西爆掉 (像是底下的 step 1 & step 2)


#include <climits>

class Solution {
 public:
  int reverse(int x) {
    int output = 0;
    while (x != 0) {
      const int digit = x % 10;
      if (!safeMultiplyAndAdd(output, digit, output /*out*/)) return 0;
      x /= 10;
    }
    return output;
  }

  bool safeMultiplyAndAdd(const int a, const int x, int &out) {
    if (x > 0) {
      // Does a * 10 + x > INT_MAX ?
      // (Step 1) Does a * 10 > INT_MAX ?
      if (a > INT_MAX / 10) return false;
      // (Step 2) Does a * 10 + x > INT_MAX ?
      if (a * 10 > INT_MAX - x) return false;
    } else {
      // Does a * 10 + x < INT_MIN ?
      // (Step 1) Does a * 10 < INT_MIN ?
      if (a < INT_MIN / 10) return false;
      // (Step 2) Does a * 10 + x < INT_MIN ?
      if (a * 10 < INT_MIN - x) return false;
    }

    out = a * 10 + x;
    return true;
  }
};

千萬別這樣寫

LeetCode C++ 解答長這樣:


class Solution {
public:
    int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
};

Why 7 and -8? 難道是因為很 87 嗎?

看了底下留言才知道原來是指 INT_MAX 的最後一位 2147483647 和 INT_MIN 的 -2147483648。

喔拜託別這樣寫，誰記得起來，而且如果今天把 int 改成 short 或 long 這個數字又要再換一次。

稍微好一點的寫法我有找到把 7 和 -8 用 INT_MAX % 10 和 INT_MIN % 10 來得到，不過我還是很討厭這種判斷方式，因為很難維護，不跟你說題目在做什麼光看 code 還以為在做很複雜的運算。

結果

喔拜託這個文章一點圖片都沒有，所以我只好在最後面放個 submission result:

有沒有發現記憶體用量打敗非常多其他的 code? 因為他們大概都偷用 string 或 long 來解這題。

搜尋此網誌

Clean Code Craving