977. Squares of a Sorted Array
題目網址：https://leetcode.cn/problems/squares-of-a-sorted-array/
題意：給一 sorted array nums, 求每個數字平方所組成的 sorted array。
Solution：
想法：利用 two pointers
class Solution {public: vector<int> sortedSquares(vector<int>& nums) { const int n = nums.size(); int left = 0, right = n - 1; vector<int> res(n, 0); for (int i = n - 1; i >= 0; --i) { // res 從後面往前填(先填大的) if (abs(nums[left]) > abs(nums[right])) { res ...
100. Same Tree
題目網址：https://leetcode.cn/problems/same-tree/
題意：給兩 BT, 求兩者是否相等。
Solution 1：
想法：利用 DFS
class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { // 至少其中一個為 null, 兩個都為 null 時, return true; 其他情況皆為 false if (!(p && q)) { return p == q; } // 兩個皆不為 null return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right); & ...
572. Subtree of Another Tree
題目網址：https://leetcode.cn/problems/subtree-of-another-tree/
題意：給兩棵 BT root 和 subRoot, 求 subRoot 是否為 root 之 subtree。
Solution：
想法：利用 DFS, 先判斷是否為 Same Tree（可參考 100. Same Tree）若不是的話, 則遞迴判斷 subRoot 是否為 root 之左子樹 or root 之右子樹
class Solution {public: bool isSubtree(TreeNode* root, TreeNode* subRoot) { if (!subRoot) { // subRoot == null, 則一定為 root 之 subtree return true; } if (!root) { // root == null && subRoot != null r ...
347. Top K Frequent Elements
題目網址：https://leetcode.cn/problems/top-k-frequent-elements/
題意：給一 array nums 和一整數 k, 返回出現頻率前 k 高的元素。可以按任何順序返回答案。
進階：請設計 $O(n \cdot log(n))$ time 的演算法, 其中 n 為 nums.size()。
Solution：
想法：利用 Heap
計算每種元素的出現次數
直接將元素 push 到 min heap pq 中
若 pq.size() > k, 代表現在 pq 中有 k + 1 個元素, 故把最小的元素給 pop 掉, 讓 pq 元素個數始終保持在 k 個
此時, pq 中的元素為前 k 大的元素, 將其取出即可
class Solution {public: using pii = pair<int, int>; vector<int> topKFrequent(vector<int>& nums, int k) { unordere ...
1. Two Sum
題目網址：https://leetcode.cn/problems/two-sum/
題意：給一 array nums 和一整數 target, 求 nums 中兩數和剛好為 target 之 index, 假設每一種 target 只會對應到一組解。
注意：同一個元素不可重複使用, 可按照任意順序返回。
Solution：
想法：利用 hash table, 由於題目保證一定有解, 因此對 nums[i] 而言, 先去 hash table 中找 target - nums[i] 是否存在
若存在, 則直接返回
否則, 將 nums[i] 還有其 index 加入到 hash table 中
class Solution {public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> umap; // {value, index} for (int ...