53最大子数组和
是拼爹还是靠自己？这是一个问题...
从前面累加到现在是谓继承
从现在另起炉灶是谓靠自己
这个题目在我之前的文章中有详细分析过，这里可以用贪心来解决，不多介绍
int maxSubArray(vector<int>& 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 合并区间
#include<bits/stdc++.h> using namespace std; vector<vector<int>> merge(vector<vector<int>>& intervals) { if(intervals.size() <= 1){ return intervals; } sort(intervals.begin(), intervals.end()); vector<vector<int>> result; int resultLeft = intervals[0][0]; int resultRight = intervals[0][1]; for(int i=1; i<intervals.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(){ vector<vector<int>> intervals = {{1,3},{2,6},{8,10},{15,18}}; vector<vector<int>> 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::vector<int>& nums, int k) { int n = nums.size(); // 对 k 进行取模，防止 k 超过数组长度 k = k % n; // 创建一个临时数组 std::vector<int> 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::vector<int>& 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。
#include<bits/stdc++.h> using namespace std; vector<int> productExceptSelf(vector<int>& nums) { int length = nums.size(); vector<int> result(length); int leftMul = 1; for(int i=0; i<length; i++){ result[i] = leftMul; leftMul *= nums[i]; } int rightMul=1; for(int i=length-1; i>=0; i--){ result[i] *=rightMul; rightMul *= nums[i]; } return result; } int main(){ vector<int> nums = {1,2,3,4}; vector<int> result = productExceptSelf(nums); for(const auto& element : result){ cout << element << ' '; } return 0; }
