Posts

LeetCode 树（3） 题目 4. 递归求解 617 合并二叉树 合并两个二叉树。 判断各个节点是否存在，全部合并到一棵树上即可。 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 翻转二叉树 翻转一个二叉树。 先将左右子树分别翻转，再交换两者的位置。 class Solution { public: TreeNode *invertTree(TreeNode *root) { if (!root) return nullptr; TreeNode *left = invertTree(root->left), *right = invertTree(root->right); root->right = left; root->left = right; return root; } }; 104 二叉树的最大深度 找出一个二叉树的最大深度。...

LeetCode 排序 题目 56 合并区间 按照间隔的起始进行排序，判断下一个间隔的起始是否大于前一个间隔的末尾，如果大于的话就把之前的间隔加入结果数组，否则继续扩展当前的间隔。 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....

LeetCode 堆 题目 215 数组中的第 K 个最大元素 最简单的堆的应用。 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 前 K 个高频元素 先遍历一次统计出数组中各个元素出现的次数，再用一个大根堆将前 k 个高频元素保存下来，最后再将这些元素依次 pop 出来存入结果数组。时间复杂度是 O(n)，空间复杂度是 O(n)。 class Solution { public: vector<int> topKFrequent(vector<int> &nums, int k) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> freq; unordered_map<int, int> count; vector<int> res(k, 0); for (auto &m:nums) ++count[m]; for (auto &c:count) { freq....

LeetCode DFS 题目 26 删除排序数组中的重复项 用两个指针 len 和 i 分别表示没有重复的项的下标与遍历数组的下标，将没有重复的项拷贝到 nums[len] 下然后 ++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 删除排序数组中的重复项 II 用两个指针 len 和 i 分别表示没有最多重复 2 次的项的下标与遍历数组的下标，将重复数小于等于 1 的项拷贝到 nums[len] 下然后 ++len 即可。...

LeetCode DFS 题目 78 子集 典型的回溯，找出所有可能情况。 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[sr][sc] 开始 DFS 或 BFS，将相邻的值相同的点的值全部修改为 newColor，注意要判断给定的 image[sr][sc] 是否等于 newColor，否则如果不使用额外空间的 visited 数组记录已经访问过的点的话会造成死循环栈溢出。...