力扣热题100——普通数组（不普通）

最大子数组和

这道题是非常经典的适用动态规划解决题目，但同时这里给出两种解法
动态规划、分治法
那么动态规划方法大家可以在我的另外一篇博客总结中看到，因此直接给出代码，着重讲第二道题

动态规划：

//使用动态规划方法
class Solution {
public:int ans = INT_MIN;//动态规划方法：令A[i]表示以i结尾的连续子数组的和int maxSubArray(vector<int>& nums) {int n = nums.size();int A[n];for(int i = 0;i<n;i++){if(!i){A[0] = nums[0];ans = nums[0];continue;}A[i] = max(A[i-1]+nums[i],nums[i]);ans = max(A[i],ans);}return ans;}
};

使用分治法
分治法就可以片面的理解为递归 若只是应对公司的笔试 不必分的那么清 咱又不写教科书：
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
1.我们来定义get(a,l,r)表示查询a序列 [l,r] 区间内的最大子段和，那么最终的答案就是get(nums,0,num.size()-1)。则实现分治法应该将区间进行划分：
对于一个区间[l,r]，取m = [(l+r)/2]，对区间[l,m]和[m+1,r]分治分解。当递归逐层深入直到区间长度缩小为1的时候，递归开始回升。
2. 对于一个区间[l,r] 我们可以维护四个量：
lSum表示[l,r]内以l为左端点的最大子段和；
rSum表示[l,r]内以r为右端点的最大子段和
msum表示[l,r]内的最大子段和
iSum表示[l,r]的区间和
以下简称[l,m]为[l,r]的左子区间，[m+1,r]为[l,r]的右子区间。且对于长度为1的区间[i,j]，四个量的值都和nums[i]相等。

对于长度为1的区间：

• 首先最好维护的是isum，区间[l,r]的iSum就等于[左子区间]的iSum加上[右子区间]的iSum。
• 对于[l,r]的lSum，存在两种可能，要么等于左子区间的lSum，要么等于左子区间的iSum加上右子区间的lSum，二者取大。
• 对于[l,r]的rSum，同理，要么等于右子区间的rSum，要么等于右子区间的iSum加上左子区间的rSum，二者取大。
• 当计算好上面的三个量之后，就很好计算[l,r]的mSum了。可以考虑[l,r]的mSum对应的区间是否跨越m——它可能不跨越m，，也就是[l,r]的mSum可能是左子区间的mSum和右子区间的mSum中的一个；它也可能跨越m，可能是左子区间的rSum和右子区间的lSum求和。三者取大。
  下面给出代码：

class Solution{
public:struct Status{int lSum,rSum,mSum,iSum;};Status pushUp(Status l,Status r){int iSum = l.iSum + r.iSum;int lSum = max(l.lSum,l.iSum + r.lSum);int rSum = max(r.rSum,r.iSum+l.rSum);int mSum = max(max(l.mSum,r.mSum),l.rSum+r.lSum);return (Status) {lSum,rSum,mSum,iSum};};Status get(vector<int> &a,int l,int r){if(l==r){return (Status) {a[l],a[l],a[l],a[l]};}int m = (l+r)/2;Status lSub = get(a,l,m);Status rSub = get(a,m+1,r);return pushUp(lSub,rSub);}int maxSubArray(vector<int>& nums){return get(nums,0,nums.size()-1).mSum;}
};

合并区间

这道题的解题思路就是先将intervals内的区间按照左端点进行排序，再定义一个新的vector<vector<int>>数组merged，且如果下一个遍历到的区间的左端点如果比 比merged最后一个区间的右端点还要大，则两个区间就没有交集了，否则就将merged最后一个区间的右端点设置为merged最后一个区间的右端点与intervals中的当前区间中右端点这两者之间的最大值，以此循环即可。最后得到的merged数组便是最终的结果 。

下面给出代码：

class Solution{
public:vector<vector<int>> merge(vector<vector<int>>& intervals){if(intervals.size()==0) return {};//这里默认排序是左端点递增 左端点相同的话则按照右端点递增的顺序进行排序sort(intervals.begin(),intervals.end());vector<vector<int>> merged;for(int i=0;i<intervals.size();i++){int L = intervals[i][0], R = intervals[i][1];if(!merged.size()||merged.back()[1]<L){merged.push_back({L,R});}else{merged.back()[1] = max(merged.back()[1],R);}}return merged;}
}

轮转数组

这里给出使用额外数组和翻转数组的两种方法

---

1.使用额外数组与原数组元素的位置对应关系为：原数组下标为i的元素放至新数组下标为(i+k)%n的位置
下面给出代码：

class Solution{
public:void rotate(vector<int>& nums,int k){int n=nums.size();vector<int> newArr(n);//定义动态数组for(int i=0;i<n;i++){newArr[(i+k)%n] = nums[i];}nums.assign(newArr.begin(),newArr.end());//assign是STL的成员函数，用于替换容器中的元素，指定容器中的元素为新内容}
}

2.翻转数组：将原数组的末尾元素放至在数组的头部等价于是将整个数组进行翻转，然后将前[0,k-1]个元素翻转，再将[k,n-1]的元素进行翻转，示例如下：

下面给出代码：

class Solution{
public:void reverse(vector<int>& nums,int start,int end){swap(nums[start],nums[end]);start++;end--;}void rotate(vector<int>& nums,int k){k %= nums.size();reverse(nums,0,nums.size()-1);reverse(nums,0,(k-1));reverse(nums,k,nums.size()-1);}
}

除自身以外数组的乘积

这道题按照你以为的常规的方法做会超时，笔者已经试过了类似下面这样吧

        // int n = nums.size();// vector<int> answer(n);// for(int i=0;i<n;i++){//     int res=1;//     for(int j=0;j<n;j++){//         if(i!=j){//             res *=nums[j];//         }//     }//     answer[i] = res;// }// return answer;

这道题跟PAT算法题的"几个PTA"这道例题很像，这里应该采用活用递推的方法求解，即根据当前位置的数值应该是左边的乘积乘以右边数的乘积，对左右两边乘积可以用两个数组存放
于是有了下面的做法

class Solution{
public:vector<int> productExcepSelf(vector<int>& nums){int n = nums.size();vector<int> answer(n);vector<int> L(n,0),R(n,0); //L,R代表左右两侧的乘积列表L[0] = 1;//索引为‘0’的元素，因为左侧没有元素 因此L[0] = 1;for(int i = 1;i<n;i++){L[i] = nums[i-1]*L[i-1];}R[n-1]=1;//最后一个元素的右侧没有元素 for(int i=n-2;i>=0;i--){R[i] = nums[i+1]*R[i+1];}//以上便定义好了两个列表//对于索引i，除nums[i]之外其余各元素的乘积就是左侧所有元素的乘积乘以右侧所有元素的乘积for(int i=0;i<n;i++){answer[i] = L[i]*R[i];}return answer;}
}

此处为了降低空间的复杂度 先试用answer数组作为左侧乘积的列表，answer[i]代表的是i左侧乘积的列表。 不构造R数组，用一个遍历跟踪右侧乘积并更新数组answer[i] = answer[i] * R，然后更新R = R*nums[i]，其中变量R表示的就是索引右侧数字的乘积。

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int length = nums.size();vector<int> answer(length);// answer[i] 表示索引 i 左侧所有元素的乘积// 因为索引为 '0' 的元素左侧没有元素， 所以 answer[0] = 1answer[0] = 1;for (int i = 1; i < length; i++) {answer[i] = nums[i - 1] * answer[i - 1];}// R 为右侧所有元素的乘积// 刚开始右边没有元素，所以 R = 1int R = 1;for (int i = length - 1; i >= 0; i--) {// 对于索引 i，左边的乘积为 answer[i]，右边的乘积为 Ranswer[i] = answer[i] * R;// R 需要包含右边所有的乘积，所以计算下一个结果时需要将当前值乘到 R 上R *= nums[i];}return answer;}
};

缺失的第一个正数

这道题直接秒了：
先看我的做法：

class Solution {
public:int firstMissingPositive(vector<int>& nums) {sort(nums.begin(),nums.end());int j=1;for(int i =0;i<nums.size();i++){if(j==nums[i]) j++;if(j<nums[i]) return j;}return j;}
};

下面还是给一个更加规范的做法：
对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。这是因为如果 [1,N] 都出现了，那么答案是 N+1，否则答案是 [1,N] 中没有出现的最小正整数。这样一来，我们将所有在 [1,N] 范围内的数放入哈希表，也可以得到最终的答案。而给定的数组恰好长度为 N，这让我们有了一种将数组设计成哈希表的思路：
对数组进行遍历，对于遍历到的数x，如果它在[1,N]的范围内，那么就将数组中的第x-1个位置打上[标记]（数组下标从0开始）。在遍历结束之后，如果所有的位置都被打上了标记，那么答案是N+1，否则答案是最小的没有打上标记的位置+1。
但问题是应该如何标记 考虑到不在1-N内的话 就是N+1；则考虑将所有非整数都变为N+1；然后遍历数组中的每一个数x，他可能已经被打了标记，因此原本对应的数为|x|，其中| |为绝对值符号。如果|x|在[1,N]，那么我们给数组中的第|x|-1个位置的数添加一个负号。

class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n = nums.size();for (int& num: nums) {if (num <= 0) {num = n + 1;}}for (int i = 0; i < n; ++i) {int num = abs(nums[i]);if (num <= n) {nums[num - 1] = -abs(nums[num - 1]);}}for (int i = 0; i < n; ++i) {if (nums[i] > 0) {return i + 1;}}return n + 1;}
};