欢迎来到小林的博客

【题目】：704. 二分查找左闭右闭区间[l, r]： class Solution {public: int search(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = l + (r - l) / 2; while(l <= r) { // 因为边界条件：[1, 1]时，l = r if(nums[mid] == target) { return mid; }else if(nums[mid] > target) { r = mid - 1; // 因为是左闭右闭，nums[mid]已经不满足了，所以r = mid - 1（跳过mid） }else { l =...

【题目】：560. 和为 K 的子数组方法1. 前缀和 class Solution {public: int subarraySum(vector<int>& nums, int k) { int res = 0; int n = nums.size(); vector<int> preSum(n + 1, 0); // 下标从1开始存储 for(int i = 0; i < n; ++i) { preSum[i + 1] = preSum[i] + nums[i]; } for(int i = 0; i < n; ++i) { for(int j = i + 1; j <= n; ++j) { if(preSum[j] - preSum[i] == k) { // i 到 j 的和 ...

【题目】：543. 二叉树的直径 class Solution {public: int res = 0; // 求节点的最大深度 int help(TreeNode* root) { if(root == nullptr) { return 0; } int l = help(root->left); // 左儿子为根的最大子树深度 int r = help(root->right); // 右儿子为根的最大子数深度 res = max(res, l + r); // 更新res return max(l, r) + 1; // 返回节点的最大深度 } int diameterOfBinaryTree(TreeNode* root) { help(root); return res; }}; 时间复杂度:...

【题目】：56. 合并区间 class Solution {public: vector<vector<int>> merge(vector<vector<int>>& intervals) { // 按照左端点排序 sort(intervals.begin(), intervals.end(), [&](vector<int> lhs, vector<int> rhs) { return lhs[0] < rhs[0]; }); vector<vector<int>> res; for(vector<int> interval : intervals) { if(res.size() != 0 && interval[0] <= res.back()[1])...

【题目】：54. 螺旋矩阵 class Solution {public: vector<int> spiralOrder(vector<vector<int>>& matrix) { int startx = 0, starty = 0; // 起始坐标 vector<int> res; int m = matrix.size(), n = matrix[0].size(); int count = min(m, n) / 2; int i, j; int offset = 1; // 填充边缘 while(count--) { // 向右 for(j = startx; j < n - offset; ++j) { res.push_back(matrix[startx][j]); ...

【题目】：438. 找到字符串中所有字母异位词 class Solution {public: vector<int> findAnagrams(string s, string p) { vector<int> res; vector<int> curVec(26, 0); // 统计p中字母出现的次数 for(char c : p) { curVec[c - 'a']++; } for(int l = 0, r = 0; r < s.size(); ++r) { curVec[s[r] - 'a']--; // 右侧字母进入滑窗 // 如果某个字母正好满足要求，并且此时窗口长度 = p.size()，说明此时滑窗内是p的异位词 if(curVec[s[r] -...

【题目】：53. 最大子数组和方法1. 前缀和 class Solution {public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int res = INT_MIN; int cur = 0; vector<int> preSum(n + 1, 0); for(int i = 0; i < n; ++i) { preSum[i + 1] = nums[i] + preSum[i]; } for(int i = 0; i < n; ++i) { for(int j = i + 1; j <= n; ++j) { res = max(res, preSum[j] - preSum[i]); ...

【题目】：48. 旋转图像 class Solution {public: void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); for(int i = 0; i < n / 2; ++i) { for(int j = 0; j < (n + 1) / 2; ++j) { // 奇数的话，要向下取整 int temp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; ...

【题目】：238. 除自身以外数组的乘积方法1. 前后缀分解 + 两个数组存放前后缀的乘积 class Solution {public: vector<int> productExceptSelf(vector<int>& nums) { // res[i] = 当前数字的左边数乘积 * 当前数字的右边数乘积 int n = nums.size(); vector<int> left(n, 1); // nums[i]左边数乘积 vector<int> right(n, 1); // nums[i]右边数乘积 for(int i = 1; i < n; ++i) { left[i] = left[i - 1] * nums[i - 1]; } for(int i = n - 2; i >= 0; --i) { ...

【题目】：25. K 个一组翻转链表 while(cur && kk--) 分类讨论：退出循环有两种情况， kk == 0：此时说明仍然有k个元素可以进行反转，可以直接将反转后的结果和尾部相连 cur == nullptr：此时如果kk > 0，说明链表中已经不足k个了，此时不应该反转，但是我之前已经将链表反转过了，所以需要再进行二次反转。这样最多只需要再遍历k-1次，比事先判断是否满足k个再进行反转的效率相对也会高点。 class Solution {public: ListNode* reverse(ListNode* head) { ListNode* res = nullptr, *cur = head; while(cur) { ListNode* temp = cur->next; cur->next = res; res = cur; cur = temp; ...