50. Pow(x, n)

解題程式碼

var myPow = function (x, n) {
  if (x === 0) return 0;
  if (n === 0) return 1;

  let pow = Math.abs(n);
  let result = pow % 2 === 0 ? myPow(x * x, pow / 2) : myPow(x * x, (pow - 1) / 2) * x;

  return n > 0 ? result : 1 / result;
};

解題思路、演算法

正常的一個乘法(2 * 2 * 2 * 2...)、除法去處理這題，遇到 n 很大(n = 2147483647)時會超出時間限制，所以需要轉換效率更高的方式去解題。

換個處理方式，2^10 = 2^5 * 2^5，2^11 = 2^5 * 2^5 * 2，就可以不用乘那麼多次，然後還要知道 2^-2 = (1/2^2)。

解法的時間、空間複雜度

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

參考資料

Pow(x, n) - X to the power of N - Leetcode 50 - Python

7. Reverse Integer

解題程式碼

var reverse = function (x) {
  let out = 0;
  let absX = Math.abs(x);

  while (absX > 0) {
    out = out * 10 + (absX % 10);
    absX = Math.floor(absX / 10);
  }

  if (out > 2147483647) return 0;

  return x > 0 ? out : -out;
};

解題思路、演算法

將要反轉的 input 數字每次除 10，得出的餘數就可以加到要輸出的結果中，下次迴圈時再將之前結果乘 10，並加入該次 input 數字除 10 的餘數。

處理邊界值的部分，可以先將 x 轉為正數，然後只需比較是否最終反轉的數比 2^31 - 1(2147483647) 還大，是就返回 0。

解法的時間、空間複雜度

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

參考資料

226. Invert Binary Tree

解題程式碼

var invertTree = function (root) {
  if (!root) return root;

  const tempNode = root.left;
  root.left = root.right;
  root.right = tempNode;

  invertTree(root.left);
  invertTree(root.right);
  return root;
};

解題思路、演算法

這題要做的是二元樹反轉，所以將當前根節點的左右子節點做交換，然後透過遞迴的方式，往該根節點的左右子節點繼續交換。

解法的時間、空間複雜度

因為每個節點都有遍歷到，所以時間複雜度 O(n)

參考資料