LeetCode

LeetCode: Trees (3) Originally published in Chinese on 2019-08-24; this English edition preserves the original scope and technical context. Title 4. Recursive solution 617 Merge Binary Trees Merge two binary trees. Determine whether each node exists and merge them all into one tree. class Solution { public: TreeNode *mergeTrees(TreeNode *t1, TreeNode *t2) { if (!t1 && !t2) return nullptr; else if (!t1) return t2; else if (!t2) return t1; t1->val += t2->val; t1->left = mergeTrees(t1->left, t2->left); t1->right = mergeTrees(t1->right, t2->right); return t1; } }; 226 Invert Binary Tree Flip a binary tree. ...

LeetCode: Sorting Originally published in Chinese on 2019-08-17; this English edition preserves the original scope and technical context. Title 56 merge intervals Sort according to the start of the interval, and determine whether the start of the next interval is greater than the end of the previous interval. If it is greater, add the previous interval to the result array, otherwise continue to expand the current interval. class Solution { public: vector<vector<int>> merge(vector<vector<int>> &intervals) { vector<vector<int>> res; int n = intervals.size(); if (n == 0) return res; sort(intervals.begin(), intervals.end(), [](vector<int> const &v1, vector<int> const &v2) { return v1[0] < v2[0]; }); int start = intervals[0][0], end = intervals[0][1]; for (int i = 1; i < n; ++i) { if (intervals[i][0] > end) { res.push_back(vector<int>{start, end}); start = intervals[i][0]; } end = max(end, intervals[i][1]); } res.push_back(vector<int>{start, end}); return res; } }; 179 maximum number First convert the numbers into strings, and then customize a sorting rule similar to lexicographic order s1 + s2 > s2 + s1 for sorting. ...

LeetCode: Heaps Originally published in Chinese on 2019-08-05; this English edition preserves the original scope and technical context. Title Kth largest element in 215 array The simplest heap application. class Solution { public: int findKthLargest(vector<int> &nums, int k) { priority_queue<int, vector<int>, greater<>> heap; for (auto &m:nums) { if (heap.size() < k || m > heap.top()) heap.push(m); if (heap.size() > k) heap.pop(); } return heap.top(); } }; 347 Top K high-frequency elements First traverse once to count the number of occurrences of each element in the array, then use a large root heap to save the first k high-frequency elements, and finally pop these elements out in sequence and store them in the result array. The time complexity is O(n) and the space complexity is O(n). ...

LeetCode: Two Pointers Originally published in Chinese on 2019-07-31; this English edition preserves the original scope and technical context. Title 26 Remove duplicates from sorted array Use two pointers len and i to represent the subscripts of items without duplicates and the subscripts of the traversed array respectively. Copy the items without duplicates to nums[len] and then use ++len. class Solution { public: int removeDuplicates(vector<int>& nums) { int count = 0, len = 1, n = nums.size(); if (n == 0) return 0; for (int i = 1; i < n; ++i) { if (nums[i] == nums[i - 1]) continue; nums[len] = nums[i]; ++len; } return len; } }; 80 Remove duplicates from sorted array II Use two pointers len and i to represent the subscripts of items that are not repeated at most 2 times and the subscripts of the traversed array respectively. Copy the items with the number of repetitions less than or equal to 1 to nums[len] and then use ++len. ...

LeetCode: Depth-First Search Originally published in Chinese on 2019-07-27; this English edition preserves the original scope and technical context. Title 78 subsets Typical backtracking to find all possible situations. class Solution { vector<vector<int>> res; public: vector<vector<int>> subsets(vector<int> &nums) { res = vector<vector<int>>(1, vector<int>()); vector<int> curr; DFS(nums, 0, curr); return res; } void DFS(vector<int> &nums, int idx, vector<int> &curr) { for (int i = idx; i < nums.size(); ++i) { curr.push_back(nums[i]); res.push_back(curr); DFS(nums, i + 1, curr); curr.pop_back(); } } }; 733 Image Rendering Start DFS or BFS from the given image[sr][sc], and modify the values of all adjacent points with the same value to newColor. Pay attention to determine whether the given image[sr][sc] is equal to newColor. Otherwise, if the visited array of extra space is not used to record the visited points, an infinite loop stack overflow will occur. ...