53最大子数组和是拼爹还是靠自己这是一个问题...从前面累加到现在是谓继承从现在另起炉灶是谓靠自己这个题目在我之前的文章中有详细分析过这里可以用贪心来解决不多介绍int maxSubArray(vectorint nums) { int maxarrValue INT32_MIN; int sum 0; int index 0; for(int i index; i nums.size(); i){ sum nums[i]; maxarrValue max(maxarrValue, sum); if(sum 0){ sum 0; } } return maxarrValue; }56 合并区间#includebits/stdc.h using namespace std; vectorvectorint merge(vectorvectorint intervals) { if(intervals.size() 1){ return intervals; } sort(intervals.begin(), intervals.end()); vectorvectorint result; int resultLeft intervals[0][0]; int resultRight intervals[0][1]; for(int i1; iintervals.size(); i){ if(intervals[i][0] resultRight){ resultRight max(resultRight, intervals[i][1]); }else{ result.push_back({resultLeft, resultRight}); resultLeft intervals[i][0]; resultRight intervals[i][1]; } } result.push_back({resultLeft, resultRight}); return result; } int main(){ vectorvectorint intervals {{1,3},{2,6},{8,10},{15,18}}; vectorvectorint result merge(intervals); for(const auto element1 : result){ for(const auto element2 : element1){ cout element2 ; } cout endl; } return 0; }核心思路排序这是解决问题的关键第一步。我们需要将所有区间按照它们的起始点进行升序排序。如果两个区间的起始点相同它们的相对顺序不重要。排序之后所有潜在的重叠区间都会被“相邻”地排列在一起。初始化“工作区”创建了一个名为result的空数组用于存放最终合并后的区间。这里我们用resultLeft 和 resultRight 两个变量来存储和更新正在合并的当前区间。将它们初始化为排序后的第一个区间 intervals[0] 的起始和结束点。这两个变量就像一个临时的“工作台”用来处理所有重叠的区间。循环与合并如果当前区间与“工作区”有重叠(intervals[i][0] resultRight)更新了“工作区”的右边界。你使用了 max(resultRight, intervals[i][1])这确保了工作区的右边界总是包含所有重叠区间的最大值。如果当前区间与“工作区”没有重叠(else)这说明前面连续的重叠区间已经全部处理完毕。将“工作区”中的结果{resultLeft, resultRight}推入result数组。然后将“工作区”重置用当前的区间intervals[i]的起始点和结束点来作为新的工作区准备处理下一组重叠区间。两个区间 [a, b] 和 [c, d]重叠的条件是 c b。4.收尾工作循环结束后最后一个正在合并的区间还没有被推入 result 数组。这是因为它的“工作区”没有遇到下一个不重叠的区间来触发 else 分支。因此需要在循环结束后再将最后的“工作区” {resultLeft, resultRight} 推入 result 数组。这一步是确保所有区间都被处理的关键。189 轮转数组好的我们来聊聊 LeetCode 189 题“轮转数组”Rotate Array。这道题有很多种解法每种方法都有不同的优缺点。1. 额外数组法这是最直观的解法。创建一个新数组然后将原数组的元素按照轮转后的位置放到新数组中。思路:创建一个和原数组大小一样的新数组new_nums。遍历原数组nums对于每个元素nums[i]计算它在新数组中的位置(i k) % n其中n是数组长度k是轮转的步数。将nums[i]放到new_nums[(i k) % n]。最后将新数组的元素复制回原数组。优点: 简单易懂不易出错。缺点: 需要额外的 O(n) 空间。#include vector #include iostream class Solution { public: void rotate(std::vectorint nums, int k) { int n nums.size(); // 对 k 进行取模防止 k 超过数组长度 k k % n; // 创建一个临时数组 std::vectorint temp(n); // 将轮转后的元素放入临时数组中 for (int i 0; i n; i) { temp[(i k) % n] nums[i]; } // 将临时数组的元素复制回原数组 nums temp; } };三次翻转法这是最高效且优雅的解法空间复杂度为 O(1)时间复杂度为 O(n)。它的核心思想是利用反转操作的特性。思路:反转整个数组。反转前 k 个元素。反转后 n - k 个元素。举例:数组nums [1, 2, 3, 4, 5, 6, 7],k 31. 反转整个数组:[7, 6, 5, 4, 3, 2, 1]2. 反转前 k 个元素: 反转[7, 6, 5]得到[5, 6, 7]。数组变为[5, 6, 7, 4, 3, 2, 1]。3. 反转后 n - k 个元素: 反转[4, 3, 2, 1]得到[1, 2, 3, 4]。数组变为[5, 6, 7, 1, 2, 3, 4]。最终结果正确。优点: 算法简洁易于实现且效率最高。#include vector #include algorithm // 包含 std::reverse class Solution { public: void rotate(std::vectorint nums, int k) { int n nums.size(); // 对 k 进行取模防止 k 超过数组长度 k k % n; // 1. 反转整个数组 std::reverse(nums.begin(), nums.end()); // 2. 反转前 k 个元素 std::reverse(nums.begin(), nums.begin() k); // 3. 反转后 n-k 个元素 std::reverse(nums.begin() k, nums.end()); } };238 除自身以外数组的乘积这道题可以通过两次遍历来解决核心思想是对于数组中的每一个元素nums[i]它的结果应该是它左侧所有元素的乘积乘以右侧所有元素的乘积。第一次遍历计算左侧乘积创建一个result向量大小与输入数组nums相同。从左到右遍历nums用一个变量left_product累积左侧的乘积。在result向量的对应位置存入left_product的值。第二次遍历计算右侧乘积并更新结果从右到左遍历nums用一个变量right_product累积右侧的乘积。将result向量中对应位置的值乘以right_product。#includebits/stdc.h using namespace std; vectorint productExceptSelf(vectorint nums) { int length nums.size(); vectorint result(length); int leftMul 1; for(int i0; ilength; i){ result[i] leftMul; leftMul * nums[i]; } int rightMul1; for(int ilength-1; i0; i--){ result[i] *rightMul; rightMul * nums[i]; } return result; } int main(){ vectorint nums {1,2,3,4}; vectorint result productExceptSelf(nums); for(const auto element : result){ cout element ; } return 0; }