112. Path Sum
題目網址：https://leetcode.cn/problems/path-sum/
題意：給一 BT 和一整數 targetSum, 返回是否存在 root-to-leaf 之路徑總和為 targetSum 的 path。
Solution 1：
想法：利用 DFS
class Solution {public: bool hasPathSum(TreeNode* root, int targetSum) { if (!root) { return false; } if (root->val == targetSum && !root->left && !root->right) { return true; } return hasPathSum(root->left, targetSum - root->val) || ...
567. Permutation in String
題目網址：https://leetcode.cn/problems/permutation-in-string/
題意：給兩 string s1 和 s2, 若 s2 包含 s1 的排列, 則返回 true。否則, 返回 false。
s1 的排列之一是 s2 的 substring。
注意：substring 為連續的, subsequence 為非連續的
Solution：
想法：利用 Sliding Window, 類似 76. Minimum Window Substring
先不斷地增加 right 來擴大窗口
縮小窗口的時機是窗口大小 ≥ s1.size() 時
當 valid == need.size() 時, 代表窗口中的 substring 為合法的排列
注意：這題是「固定長度」的窗口, 因為窗口每次向前滑動時只會移出一個字元, 故可以把內層的 while 改成 if, 其效果是一樣的
class Solution {public: bool checkInclusion(string s1, string s2) { ...
66. Plus One
題目網址：https://leetcode.cn/problems/plus-one/
題意：給一整數 array digits 用來表示一非負整數。返回該非負整數 + 1 後所表示的 digits。
非負整數的最高為儲存在 digits 的首位, 其中 digits[i] 只儲存單個數字。
除了 0 之外, 其他整數都不會以 0 作為開頭。
Solution 1：
想法：遍歷 digits, 並紀錄進位 carry。若最後 carry 為 1, 則在 digits 最前面補上 1
class Solution {public: vector<int> plusOne(vector<int>& digits) { int carry = 1; // 因為最後一位要加 1, 所以把 carry 設成 1 for (int i = digits.size() - 1; i >= 0; --i) { digits[i] = carry + digits[i]; ...
238. Product of Array Except Self
題目網址：https://leetcode.cn/problems/product-of-array-except-self/
題意：給一 array nums, 返回一 array answer, 其中 answer[i] 為 nums 中除了 nums[i] 以外其餘元素的乘積, 乘積保證在 32-bit 整數的範圍內（不用考慮 overflow）。
注意：請不要使用除法, 並在 $O(n)$ time 內解決此問題
進階：請設計 $O(1)$ space 的演算法, 其中 output array 不算額外空間
Solution 1：
想法：利用 prefix 和 postfix, 以 index = i 為分界, prefix[i] 記錄區間 [0, i - 1] 之乘積, postfix[i] 記錄區間 [i + 1, n - 1] 之乘積, 最後 nums[i] = prefix[i] * postfix[i] 即為題目所求
prefix：prefix[i] 紀錄 num[0] ~ nums[i - 1] 的乘積（由前往後填）
postfix：postfix[n - ...
303. Range Sum Query - Immutable
題目網址：https://leetcode.cn/problems/range-sum-query-immutable/
題意：給一 array, 多次輸入不同的 left 和 right, 求 array 中從 idx = left 到 idx = right 之和。
Solution 1：
想法: 每一次 query 都去計算
class NumArray {private: vector<int> nums_;public: NumArray(vector<int>& nums) { nums_ = move(nums); // 複製 nums } int sumRange(int left, int right) { int sum = 0; for (int i = left; i <= right; ++i) { sum += nums_[i]; } re ...