191. Number of 1 Bits

解題程式碼

var hammingWeight = function (n) {
  let count = 0;
  while (n) {
    n = n & (n - 1);
    count++;
  }

  return count;
};

解題思路、演算法

這題當然可以把 input 值轉成 2 進位，然後再跑迴圈去計算 1 出現幾次，只是這樣時間複雜度為 O(32) = O(1)，32 代表每個位元都跑檢查過

要更好的效能的話，可以使用前人想到的特別技巧

Bitwise AND (&) 可以計算兩個數字其二進位數的每個位元是否都為一然後輸出

const a = 5;        // 00000000000000000000000000000101
const b = 3;        // 00000000000000000000000000000011

console.log(a & b); // 00000000000000000000000000000001

而如果是 n & (n - 1) 的話，可以消除 n 的最後一個 1，例如 00000000000000000000000000000101 & 00000000000000000000000000000100 結果就是 00000000000000000000000000000100

而再次進行 n & (n - 1)，變成 00000000000000000000000000000100 & 00000000000000000000000000000011，結果就全部變成 0，脫離迴圈，迴圈內執行兩次，也剛好等於 00000000000000000000000000000101 1 的個數

解法的時間、空間複雜度

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

參考資料

Number of 1 Bits - Leetcode 191 - Python

136. Single Number

解題程式碼

var singleNumber = function (nums) {
  let num = 0;
  for (let i = 0; i < nums.length; i++) {
    num ^= nums[i];
  }

  return num;
};

解題思路、演算法

這題題目給了兩個限制: 時間複雜度要是 O(n) 然後空間複雜度要是 O(1)，所以就變成很多做法都不行XD

最後參考別人的作法，用 Bitwise XOR (^)，利用兩個相同數字轉成二進位後，兩個數相同位元相加會變成 0 的特性，讓兩個數字都變成 0，最後留下來的就會是 input 陣列中出現一次的數字

和 CodeWar 這題一樣是同一題 https://www.codewars.com/kata/54da5a58ea159efa38000836/solutions/javascript

解法的時間、空間複雜度

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

參考資料

268. Missing Number

解題程式碼

解法 1

var missingNumber = function (nums) {
  let numsSum = 0;
  let n = nums.length;
  let numsLengthSum = (n * (n + 1)) / 2;
  for (let i = 0; i < n; i++) {
    numsSum += nums[i];
  }
  return numsLengthSum - numsSum;
};

解法 2

var missingNumber = function (nums) {
  let temp = 0;
  for (let i = 0; i < nums.length; i++) {
    temp ^= nums[i];
    temp ^= i;
  }
  return (temp ^= nums.length);
};

解法 3

var missingNumber = function (nums) {
  const set = new Set(nums);

  for (let i = 0; i <= nums.length; i++) {
    if (!set.has(i)) return i;
  }
};

解題思路、演算法

這題可以有很多的解法，但題目有一個 Follow up 要求，解法的時間複雜度要 O(n)、空間複雜度要 O(1)，要達成這個要求我們可以把 1~nums.length 的數字全部加起來，然後也把整個 nums 的元素全部加起來，兩個相減，得到的就是題目要求的 missing number。

這題也可用類似於 Leetcode 136. Single Number 的概念去解，同樣的數字做 XOR 會不見，所以設定一個 temp 值，遞迴陣列每個元素時和當前遍歷的元素及 i 值做 XOR，最後剩下的數字就會是 missing number，這個解法基本上執行效率都勝出 90% 的其他解法。

解法 3 是在討論區看到的解法，用 set 做蠻乾淨的，不過空間複雜度就不符合 Follow up 要求。

解法的時間、空間複雜度

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

參考資料