190. Reverse Bits

解題程式碼

var reverseBits = function (n) {
  let result = 0;
  for (let i = 0; i < 32; ++i) {
    result = (result << 1) + (n & 1);
    n >>= 1;
  }

  return result >>> 0;
};

解題思路、演算法

題目要求要把二進制的 input n 做翻轉後，再轉成十進制作成 output

首先要先知道(左、右)位移位運算子、無符號右位移運算子:

• Left shift (<<)
• Right shift (>>)
• Unsigned right shift (>>>)

const a = 5; // 00000000000000000000000000000101
const b = 2; // 00000000000000000000000000000010

console.log(a << b); // 00000000000000000000000000010100
// Expected output: 20
//-----------------------------------------------------------
const a = 5; //  00000000000000000000000000000101
const b = 2; //  00000000000000000000000000000010
const c = -5; //  11111111111111111111111111111011

console.log(a >> b); //  00000000000000000000000000000001
// Expected output: 1

console.log(c >> b); //  11111111111111111111111111111110
// Expected output: -2
//-----------------------------------------------------------
const a = 5; //  00000000000000000000000000000101
const b = 2; //  00000000000000000000000000000010
const c = -5; //  11111111111111111111111111111011

console.log(a >>> b); //  00000000000000000000000000000001
// Expected output: 1

console.log(c >>> b); //  00111111111111111111111111111110，差異在整個數字右移後，前面補上 b 個 0
// Expected output: 1073741822

然後是 Bitwise AND (&) :

知道這些之後，來理解下解法的程式碼:

result = (result << 1) + (n & 1); 可以拆成兩個階段看:

1. result += (n & 1); 取出最右邊的 bit，ex: 00101 取得最右邊 1
2. result <<= 1; 往左移一個 bit

result = (result << 1) + (n & 1); 就是 0 + 1 = 01

n >>= 1; 則是捨棄掉已取得的最右邊 bit，ex: 00101 變成 00010

下次迴圈時: result = (result << 1) + (n & 1); 就是 10 + 0，n >>= 1; 則是捨棄掉已取得的最右邊 bit，ex: 00010 變成 00001

再下次迴圈時: result = (result << 1) + (n & 1); 就是 100 + 1，n >>= 1; 則是捨棄掉已取得的最右邊 bit，ex: 00000 變成 00000

以此類推，迴圈跑完，將 result 用 >>> 轉成 unsigned

解法的時間、空間複雜度

時間複雜度: O(1)
空間複雜度: O(1)

參考資料

https://youtu.be/UcoN6UjAI64?si=ePHwN2_weElexBTX

補充

將數字做翻轉:

function reverse_a_number(n) {
  let reversedNum = 0;
  while (n !== 0) {
    reversedNum = reversedNum * 10 + (n % 10);
    n = Math.floor(n / 10);
  }
  return reversedNum;
}

13. Roman to Integer

解題程式碼

const roman = new Map([
  ['M', 1000],
  ['CM', 900],
  ['D', 500],
  ['CD', 400],
  ['C', 100],
  ['XC', 90],
  ['L', 50],
  ['XL', 40],
  ['X', 10],
  ['IX', 9],
  ['V', 5],
  ['IV', 4],
  ['I', 1],
]);

var romanToInt = function (s) {
  let counter = 0;
  let result = 0;

  while (counter < s.length) {
    if (roman.get(s.slice(counter, counter + 2))) {
      result += roman.get(s.slice(counter, counter + 2));
      counter += 2;
    } else {
      result += roman.get(s.slice(counter, counter + 1));
      counter++;
    }
  }
  return result;
};

解題思路、演算法

用 hashMap 去儲存各種 roman 字串的對應值再做比對。

解法的時間、空間複雜度

時間複雜度: O(1)
空間複雜度: O(n)

參考資料

528. Random Pick with Weight

解題程式碼

/**
 * @param {number[]} w
 */
var Solution = function (w) {
  this.weights = [];
  this.sum = 0;

  for (let i = 0; i < w.length; i++) {
    this.sum += w[i];
    this.weights.push(this.sum);
  }
};

/**
 * @return {number}
 */
Solution.prototype.pickIndex = function () {
  const index = Math.floor(Math.random() * this.sum);
  let start = 0;
  let end = this.weights.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (index < this.weights[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return start;
};

/**
 * Your Solution object will be instantiated and called as such:
 * var obj = new Solution(w)
 * var param_1 = obj.pickIndex()
 */

解題思路、演算法

這題首先可以算出整個 w 陣列的所有值的總和，以及建立一個新陣列 weights，記錄當前遍歷過權重的總和。例如 w = [2, 1, 5, 4] 時，sum = 12，weight = [2, 3, 8, 12]。

接著我們從 sum 裡面隨機抽一個數字，例如抽到 7，透過二分搜尋法查找後，它會在 weights 陣列的 3 & 8 之間，8 的 index 在 weight 內是 2，所以得出索引 2。

若 w 抽取的索引和機率轉化成比例長度，會變成以下的樣子:

w 抽取的 index:                 0    1        2            3
w 指定 index 被抽取的機率:    |     |  |              |           |
當前權重的累加總和:                 2  3              8           12
                            |  |  |  |  |  |  |  |  |  |  |  |  |
                            0  1  2  3  4  5  6  7  8  9  10 11 12

解法的時間、空間複雜度

時間複雜度: init: O(n)，pickIndex: O(log n)
空間複雜度: O(n)

參考資料