leetcode 78. 子集
class Solution { public: vector<vector<int>> res; vector<vector<int>> subsets(vector<int>& nums) { vector<int> track; int start = 0; backtrack(nums, start, track); return res; } void backtrack(vector<int>& nums, int start, vector<int>& track) { res.push_back(track); for (int i = start; i < nums.size(); ++i) { track.push_back(nums[i]); backtrack(nums, i + 1, track); track.pop_back(); } } };leetcode 236. 二叉树的最近公共祖先
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (root == nullptr) return nullptr; if (root == p || root == q) return root; TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left == nullptr && right == nullptr) return nullptr; if (left != nullptr && right != nullptr) return root; return left == nullptr ? right : left; } };leetcode 300. 最长递增子序列
class Solution { public: int lengthOfLIS(vector<int>& nums) { // patience sorting int n = nums.size(); vector<int> top(n, 0); int piles = 0; // 牌的堆数 for (int i = 0; i < n; ++i) { int poker = nums[i]; /*** 寻找左侧边界的二分搜索 ***/ int left = 0, right = piles; while (left < right) { int mid = left + (right - left) / 2; if (top[mid] > poker) right = mid; else if (top[mid] < poker) left = mid + 1; else right = mid; } if (left == piles) ++piles; top[left] = poker; } return piles; } };leetcode 111. 二叉树的最小深度
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int minDepth(TreeNode* root) { if (root == nullptr) return 0; int depth = 1; queue<TreeNode*> que; que.emplace(root); while (!que.empty()) { int sz = que.size(); for (int i = 0; i < sz; ++i) { TreeNode* node = que.front(); que.pop(); if (node->left == nullptr && node->right == nullptr) { return depth; } if (node->left != nullptr) { que.emplace(node->left); } if (node->right != nullptr) { que.emplace(node->right); } } ++depth; } return depth; } };leetcode 3. 无重复字符的最长子串
class Solution { public: int lengthOfLongestSubstring(string s) { // sliding window unordered_map<char, int> window; int left = 0, right = 0; int res = 0; while (right < s.size()) { char c = s[right]; ++right; ++window[c]; while (window[c] > 1) { char d = s[left]; ++left; --window[d]; } res = max(res, right - left); } return res; } };leetcode 1143. 最长公共子序列
class Solution { public: int longestCommonSubsequence(string text1, string text2) { // dynamic programming int m = text1.size(), n = text2.size(); vector<vector<int>> dp(m+1, vector<int>(n+1, 0)); for (int i = 1; i < m+1; ++i) { for (int j = 1; j < n+1; ++j) { if (text1[i-1] == text2[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; } else { dp[i][j] = max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; } };leetcode 46. 全排列
class Solution { public: vector<vector<int>> res; vector<vector<int>> permute(vector<int>& nums) { vector<int> track; backtrack(nums, track); return res; } void backtrack(vector<int>& nums, vector<int>& track) { if (track.size() == nums.size()) { res.push_back(track); return; } for (int i = 0; i < nums.size(); ++i) { vector<int>::iterator it = find(track.begin(), track.end(), nums[i]); if (it != track.end()) continue; track.push_back(nums[i]); backtrack(nums, track); track.pop_back(); } } };leetcode 55. 跳跃游戏
class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(); int farthest = 0; // 站在当前位置能够跳到的最远距离 for (int i = 0; i < n - 1; ++i) { // 不断计算能跳到的最远距离 farthest = max(farthest, i + nums[i]); // 如果可以直接跳到最后一个下标，返回true if (farthest >= n-1) return true; // 可能碰到了0，卡柱跳不动了 if (farthest <= i) return false; } return true; // 最后必须要有这个额外的return } };leetcode 875. 爱吃香蕉的珂珂
class Solution { public: int minEatingSpeed(vector<int>& piles, int h) { // 最小速度应至少为1，最大速度是piles中的最大值 int left = 1; int right = *max_element(piles.begin(), piles.end()); // 寻找左侧边界的二分搜索 while (left < right) { int mid = left + (right - left) / 2; if (canFinish(mid, piles, h)) right = mid; else left = mid + 1; } return left; } bool canFinish(int speed, vector<int>& piles, int h) { int time = 0; for (int n : piles) { // 注意：下面这个表达式中的括号不能省略 time += (n / speed) + ((n % speed > 0) ? 1 : 0); } return time <= h; } }; 时间复杂度： O ( n log ? n ) O(n\log n) O(nlogn)leetcode 17. 电话号码的字母组合
class Solution { public: vector<string> res; vector<string> letterCombinations(string digits) { if (digits.empty()) return res; unordered_map<char, string> phoneMap = { {'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"} }; string combination; backtrack(digits, 0, combination, phoneMap); return res; } void backtrack(const string& digits, int index, string& combination, const unordered_map<char, string>& phoneMap) { if (index == digits.size()) { res.push_back(combination); return; } string letters = phoneMap.at(digits[index]); for (char c : letters) { combination.push_back(c); backtrack(digits, index + 1, combination, phoneMap); combination.pop_back(); } } }; 时间复杂度： O ( 3 m × 4 n ) O(3^m \times 4^n) O(3m×4n)leetcode 560. 和为 K 的子数组
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> hash_table; hash_table[0] = 1; // 前缀和数组的最左端需要引入一个0，它出现的次数是1 int res = 0, preSum = 0; for (int num : nums) { preSum += num; if (hash_table.find(preSum - k) != hash_table.end()) { res += hash_table[preSum - k]; } ++hash_table[preSum]; } return res; } }; 时间复杂度： O ( n ) O(n) O(n)leetcode 200. 岛屿数量
class Solution { public: vector<vector<int>> DIRECTION = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; int numIslands(vector<vector<char>>& grid) { if (grid.empty()) return 0; int m = grid.size(), n = grid[0].size(); int res = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { ++res; bfs(grid, i, j); } } } return res; } void bfs(vector<vector<char>>& grid, int x, int y) { queue<pair<int, int>> que; que.push({x, y}); grid[x][y] = '0'; while (!que.empty()) { auto [x, y] = que.front(); que.pop(); for (vector<int> d : DIRECTION) { int dx = x + d[0]; int dy = y + d[1]; if (dx < 0 || dx >= grid.size() || dy < 0 || dy >= grid[0].size() || grid[dx][dy] == '0') continue; que.push({dx, dy}); grid[dx][dy] = '0'; } } } };
 1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。 |
标签： #leetcode刷题记录 #leetcode #236 #二叉树的最近公共祖先 #111 #二叉树的最小深度
