LeetCode 热题-最大的子数组和 合并区间 轮转数组

最大子数组和

53. 最大子数组和https://leetcode.cn/problems/maximum-subarray/

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]输出：1

示例 3：

输入：nums = [5,4,-1,7,8]输出：23

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

解法1:dp

将每一段分为

由上一段加上最后一个数字

或者

只有最后一个数字

class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); // dp vector<int>dp(n,0); dp[0]=nums[0]; int maxVal = dp[0]; for(int i=1;i<n;i++) { //不然就和前面相加,不然就自己另起一段 dp[i]=max(dp[i-1]+nums[i],nums[i]); maxVal=max(maxVal,dp[i]); } return maxVal; } };

合并区间

56. 合并区间https://leetcode.cn/problems/merge-intervals/

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2：

输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例 3：

输入：intervals = [[4,7],[1,4]]输出：[[1,7]]解释：区间 [1,4] 和 [4,7] 可被视为重叠区间。

提示：

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^4

解法1:排序 双指针

class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { int n = intervals.size(); vector<vector<int>>res; vector<pair<int,int>> a; for(int i=0;i<n;i++) { a.push_back({intervals[i][0],intervals[i][1]}); } sort(a.begin(),a.end()); //int l=a[0].first,r=a[0].second; int l=-1,r=-1; for(int i=0;i<n;i++) { int tl=a[i].first,tr=a[i].second; if(i==0)l=tl,r=tr; if(r<tl&&i!=0)//分割为两段 { res.push_back({l,r}); l=tl,r=tr; continue; } if(tr>=r) { r=tr; continue; } } res.push_back({l,r}); return res; } };

轮转数组

给定一个整数数组nums，将数组中的元素向右轮转k个位置，其中k是非负数。

示例 1:

输入:nums = [1,2,3,4,5,6,7], k = 3输出:[5,6,7,1,2,3,4]解释:向右轮转 1 步:[7,1,2,3,4,5,6]向右轮转 2 步:[6,7,1,2,3,4,5]向右轮转 3 步:[5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2输出：[3,99,-1,-100]解释:向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1
• 0 <= k <= 10^5

解法1:取余

class Solution { public: void rotate(vector<int>& nums, int k) { vector<int> tmp=nums; int n = nums.size(); for(int i=0;i<n;i++) { int idx=(i+k)%n; nums[idx]=tmp[i]; } } };

解法2:环形移动

拿出一个数字暂存,然后从拿出的位置倒推,移动其他数字到对应位置,会回到原点,下一次选择不重复的余数之一即可

https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipkhttps://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk

解法3:数组翻转