54. Spiral Matrix
題目網址：https://leetcode.cn/problems/spiral-matrix/
題意：給一 m x n 的 matrix, 按照 順時針螺旋 順序, 返回 matrix 中所有元素。
Solution：
想法： 將 matrix 由外而內分成好幾層, 每層都有四個方向要走, 依序是
由左至右
由上至下
由右至左
由下至上
class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { vector<int> res; int left = 0, right = matrix[0].size(); int top = 0, bottom = matrix.size(); int direction = 0; while (left < right && top < bottom) &# ...
73. Set Matrix Zeroes
題目網址：https://leetcode.cn/problems/set-matrix-zeroes/
題意：給一 m x n 的 matrix, 若其中一元素為0, 將其所在列和行的所有元素都設為0。
注意：請使用 in-place 演算法
進階：
用 O(mn) space 的直覺作法似乎是個壞主意
設計 O(m + n) space 的演算法，但這仍然不是最好的解決方案
設計 O(1) space 的演算法
Solution 1：
想法：分別用 rows, cols 來記錄哪些 row, col 上的元素要設為 0
class Solution {public: void setZeroes(vector<vector<int>>& matrix) { const int m = matrix.size(), n = matrix[0].size(); vector<int> rows(m, 0), cols(n, 0); for (int i = 0; ...
50. Pow(x, n)
題目網址：https://leetcode.cn/problems/powx-n/
題意：給一 double x 和一整數 n, 返回 x 的 n 次方。
Solution：
想法：利用 Divide and Conquer, 比如 $2^{10}$ 可拆成 $2^5 * 2^5$, 而 $2^5$ 又可拆成 $2(2^2 * 2^2)$, 依此類推。透過這樣的方法可以避免重複計算, 而不用一直乘 x
class Solution {public: double myPow(double x, int n) { // 注意 res 要宣告成 double (容易粗心) double res = quickPow(x, abs(n)); // 計算 x^n, 其中 n 取正 return (n >= 0) ? res : (1 / res); // 若 n < 0, 則取倒數 1 / (x^n) }private: double quickPow(double x, int n) ...
43. Multiply Strings
題目網址：https://leetcode.cn/problems/multiply-strings/
題意：給兩個以 string 表示的非負整數 num1 和 num2, 返回 num1 和 num2 的乘積 (以 string 表示)。
注意：不得使用任何內建的 BigInteger library 或是 直接將 input string 轉換為整數。
Solution：
想法：利用大數乘法, 用整數 array digits 來儲存乘積
e.g. num1 = "123", num2 = "45"
令每個數最左邊的數 idx = 0, 每往右一位 idx + 1, digits 最左邊的 idx 也為 0
num1 中 2 的 idx = 1
num2 中 4 的 idx = 0
若 num1.size() = m, num2.size() = n, 則 digits.size() = m + n
若 num1 和 num2 都取最小值, 則 num1 為 $10^{m-1}$, num2 為 $10^{n-1}$ ➔ nu ...
2013. Detect Squares
題目網址：https://leetcode.cn/problems/detect-squares/
題意：給一在 X-Y 平面上的點所構成的 data stream。設計一個滿足下述要求的算法：
新增一個在 data stream 中的新點到某個資料結構中。可以新增重覆的點, 並且會被視作不同的點
給一查詢點, 從資料結構中選出三個點, 使這三點、查詢點構成一個面積為正的 axis-aligned square, 統計滿足該要求的方法數。
axis-aligned square 是一個正方形, 除了四條邊的長度相同外, 還滿足每條邊皆與 X軸 or Y軸 平行或垂直。
實現 DetectSquares class：
DetectSquares()：初始化 DetectSquares instance
void add(int[] point)：向資料結構新增一個新的點 point = [x, y]
int count(int[] point)：按上述方式統計與點 point = [x, y] 共同構成 axis-aligned square 的方法數
Solution ...