最大子數組和

這道題是非常經典的適用動態規劃解決題目，但同時這里給出兩種解法
動態規劃、分治法
那么動態規劃方法大家可以在我的另外一篇博客總結中看到，因此直接給出代碼，著重講第二道題

動態規劃：

//使用動態規劃方法
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;}
};