Zako's Blog

題目網址：https://leetcode.cn/problems/path-sum-iii/ 題意：給一 BT 的 root 和一整數 targetSum,　返回路徑總和等於 targetSum 的 path 個數。 path 不需從 root 開始, 也不需在 leaf 結束, 但 path 方向須是向下的（只能從父節點到子節點）。 Solution 1： 想法：利用 DFS traverse() 負責 DFS 遍歷整個 BT countPath(root) 負責計算在 root 為 root 的 BT 中, 以 root 為開頭，且和為 targetSum 的 path 個數 class Solution {public: int pathSum(TreeNode* root, int targetSum) { int res = 0; traverse(root, targetSum, res); return res; }private: // 遍歷整個 BT voi ...

題目網址：https://leetcode.cn/problems/maximum-binary-tree/ 題意：給一不重複的的整數 array nums, 利用下面的演算法遞迴建構 Maximum BT： 創建一個 root, 其值為 nums 中最大值 用最大值左邊的 subarray 遞迴建構左子樹 用最大值右邊的 subarray 遞迴建構右子樹 返回 nums 建構的 Maximum BT。 Solution： 想法：利用 DFS class Solution {public: TreeNode* constructMaximumBinaryTree(vector<int>& nums) { return dfs(0, nums.size() - 1, nums); }private: TreeNode* dfs(const int left, const int right, const vector<int>& nums){ if ...

題目網址：https://leetcode.cn/problems/maximum-width-of-binary-tree/ 題意：給一 BT 的 root, 返回該 tree 的最大寬度。 每一層的寬度被定義為兩個端點之間的長度（該層最左和最右的非空節點, 兩端點之間的 null 也計入長度）。 答案可用 32-bit 有號整數表示。 Solution 1： 想法：利用 DFS 我們可以 assign idx 給每個 node, 然後計算出每層的寬度 root = 1 left = 2 * parent right = 2 * parent + 1 但是一旦遇到高度 > 64 的 skew tree, 32-bit 的有號整數便無法表達 ➔ 因此紀錄每層最左邊的非空節點的 idx, 把它當作該層所有節點 idx 的 offset, 因此新的 idx 為原先 idx 扣掉該層的 offset, 然後再用新的 idx 來對 child 進行遞迴 class Solution {public: int widthO ...

題目網址：https://leetcode.cn/problems/3sum-closest/ 題意：給一長度為 n 的整數 array nums 和一整數 target, 從 nums 選出三個整數, 使其 sum 最接近 target, 返回這三個數之 sum。 假設每個輸入恰只存在一個解。 Solution： 想法：利用 Two Pointers 首先, 將 nums 由小到大做排序, 用 res 來記錄當前最接近 target 之 sum 用 i 遍歷 [0 , n], 每一次 i 遍歷一元素 使用 Two pointer 尋找：left = i + 1, right = n - 1, 並用 sum 紀錄當前三數之和 若 sum 比 res 還更接近 target, 則 res = sum 否則, 代表 sum 比 res 離 target 更遠, 則可細分成兩種情形： sum < target：left + 1 sum ≥ target：right - 1 class Solution {public: int threeSumClo ...

題目網址：https://leetcode.cn/problems/subarray-product-less-than-k/ 題意：給一整數 array nums 和一整數 k, 返回所有 subarray 中所有乘積小於 k 的連續 subarray 個數。 Solution： 想法：利用 Two Pointers + Sliding Window 用 prod 紀錄 left ~ right 之連續數乘積 若 prod > k : 則 prod /= nums[left], 且 left 要不斷右移, 直到 prod < k 新增的連續 subarray 總共有 right - left + 1 個（以 right 為結尾的連續 subarray）e.g. nums = [10, 5, 2, 6], k = 100 left = 0 = right, 取 10 < 100 ➔ res = 1 left = 0, right = 1, 取 10 * 5 < 100 ➔ res = 1 + 2 = 3 因為除了原本的 [10] 之外新增了 [5], ...