Leecode - 7. 整數反轉(JavaScript版)

題目描述

給你一個 32 位的有符号整數 x ，傳回将 x 中的數字部分反轉後的結果。

如果反轉後整數超過 32 位的有符号整數的範圍 [−231, 231 − 1] ，就傳回 0。

假設環境不允許存儲 64 位整數（有符号或無符号）。

示例：

輸入：x = 123
輸出：321

輸入：x = -123
輸出：-321

輸入：x = 120
輸出：21

輸入：x = 0
輸出：0

輸入：x = 1534236469
輸出：0
           

提示：

• -231 <= x <= 231 - 1
• 負數負号不反轉
• 反轉後第一位不為0

解答

一開始就想到了轉換為字元串暴力求解

我沒有一顆算法的心

，作為一個算法小白總是習慣性的暴力求解，主要是複雜的實在是一開始想不出來。還好暴力求解也做出來了(第一次交的還挂了。。)，先看看我暴力求解的代碼(真的啰嗦-_-~)

暴力求解

知識點：

• toString()

  ：可把一個 Number 對象轉換為一個字元串，并傳回結果。傳回的字元長度為1。
  • 文法：

    NumberObject.toString(radix)

• charAt()

  ：可傳回指定位置的字元
  • 文法：

    stringObject.charAt(index)

• substring()

  ：用于提取字元串中介于兩個指定下标之間的字元
  • 文法：

    stringObject.substring(start,stop)

    ，第二個參數

    stop

    可選
  • 說明：

    substring()

    方法傳回的子串包括

    start

    處的字元，但不包括

    stop

    處的字元。

• split()

  ：用于把一個字元串分割成字元串數組
  • 文法：

    stringObject.split(separator,howmany)

    ，第二個參數可選
  • 說明：
    • 傳回的數組中的字串不包括 separator 自身
    • 如果把空字元串 ("") 用作 separator，那麼

      stringObject

      中的每個字元之間都會被分割

• reverse()

  ：用于颠倒數組中元素的順序
  • 文法：

    arrayObject.reverse()

  • 說明：該方法會改變原來的數組，而不會建立新的數組。

• join()

  ：用于把數組中的所有元素放入一個字元串
  • 文法：

    arrayObject.join(separator)

    ，參數可選
  • 說明：元素是通過指定的分隔符進行分隔的

var reverse = function(x) {
    // 将x轉換為字元串
    var str = x.toString();
    // 判斷str在長度不為1的情況下最後一位是否為0
    // 為0的話，反轉後第一位會是0
    if (str.charAt(str.length-1) == '0' && str.length > 1) {
        // 為0的話就舍棄
        str = str.substring(0, str.length - 1);
    }
    // 去除負數的負号
    str = x < 0 ? ("-" + str.substring(1).split("").reverse().join("")) : str.split("").reverse().join("");
    // 對反轉後的數進行溢出判斷
    if(str > Math.pow(2, 31) - 1 || str < Math.pow(-2, 31)) return 0;
    return str;
}
           

其中遇到的問題：

上面提到過我第一次送出的時候挂了，是因為我是對

沒有反轉後的x進行溢出判斷

，而是判斷了反轉前的，但是反轉後的數會有溢出的可能

非暴力求解法

這個是Leecode上一位大佬寫的，跟我的比起來進階了不知道多少倍，真的巧妙。他的辦法是，通過取餘，位非運算符(~)來一個一個數取反

• ~

  運算符（位非）用于對一個二進制操作數逐位進行取反操作
  • 第 1 步：把運算數轉換為 32 位的二進制整數。
  • 第 2 步：逐位進行取反操作。
  • 第 3 步：把二進制反碼轉換為十進制浮點數。
  • 總的來說就是對數字進行取負運算，再減 1
  • 那麼

    ~~

    ，就是進行兩次取反

    • # 對 -12.2 進行位非運算，則傳回值為 -12
      ~12 = -12-1 = -11.2
      # 那麼
      ~~12 = -(-13)-1 = -12
      # 結論
      ~~可以去掉小數
                 

    • 跟

      Math.floor()

      不同的是，它隻是單純的去掉小數部分，不論正負都不會改變整數部分。

      -12.2

      按照

      Math.floor()

      的做法就會等于

      -13

var reverse = function(x) {
    let res = 0;
    while(x){
        res = res * 10 + x % 10;
        if(res > Math.pow(2, 31) - 1 || res < Math.pow(-2, 31)) return 0;
        x = ~~(x / 10);
    }
    return res;
};
           

代碼說明

：

• 每一次都利用取餘來獲得整數的最後一位，任何整數不管能不能除盡10，最後得到的餘數都是整數本身的最後一位
• 将反轉後的數存在res中，在通過

  res * 10

  ,然後res存的數位數提升，在通過

  ~~(x / 10)

  除10去掉小數，去掉x的最後一位。例如
  • 開始x=123，res = 0
  • 第一次x=123，res = 0 * 10+123 % 10 = 3，x=~~(123 / 10) = 12
  • 第二次x=12，res = 3 * 10+12 % 10 = 30 + 2 = 32，x=~~(12 / 10) = 1
  • 第三次x=1，res = 32 * 10+1 % 10 = 320 + 1 = 321，x=~~(1 / 10) = 0