最小覆盖子串
首先建立对字符串t的哈希映射，这题用到了滑动窗口的思想。假设字串是ABC，如果主串是AAABBC，那么只有到最后一位的时候才能满足。而当满足的时候，我们可以建立一个左指针，他会逐渐右移，直到不满足哈希映射退出。这里注意，不能每次左指针右移都去做substr，会超出内存限制。可以用一个differ来存储不同的数目，把每次check哈希表是否都为0的时间从O(n)降低到O(1),代码如下
class Solution {
public:string minWindow(string s, string t) {//必须包含t中其中一个字母才能开头int n=s.size(),m=t.size();unordered_map<char,int> mp;int differ=0,r=0,l=0;int ans=0x3f3f3f3f;for(int i=0;i<m;i++){if(mp.find(t[i])==mp.end())differ++;mp[t[i]]++;}string s1;int ansl=-1;for(r=0;r<n;r++){if(mp.count(s[r])&&--mp[s[r]]==0) differ--;while(differ==0&&l<=r){if(r-l+1<ans){ans=r-l+1;ansl=l;}if(mp.count(s[l])&&++mp[s[l]]>0)differ++;l++;}}if(ans==0x3f3f3f3f)return "";return s.substr(ansl,ans);}
};最大子数组和
做法1：想像一个最大子数组，必然需要加上一个正数。当前位置的最大子数组是什么呢，如果加上当前位置的数字之后，数组更大了，或者说 大于当前这里的数字，那么就选择。其实就是动态规划的思想。这里也不需要开一个数组，可以利用类似滚动数组的思想，只开一个pre就够了
class Solution {
public:int maxSubArray(vector<int>& nums) {int pre=0;int ans=-0x3f3f3f3f;for(auto &x:nums){pre=max(pre+x,x);ans=max(ans,pre);}return ans;}
};做法2：线段树解法 虽然因为递归，时间复杂度和空间复杂度都不如做法一优秀，但这个方法可以求解任意区间。感觉自己还是有进步的，之前根本不会线段树，现在都可以很快写出来了
const int N要在类外定义。这里要么在类外定义，要么类内加上static
const int N=1e5+5;
class Solution {
public://const int N=1e5+5;struct tree{int l,r;int lsum,rsum,sum,msum;}tr[N<<2];void pushup(int s){int ls=s<<1,rs=s<<1|1;tr[s].lsum=max(tr[ls].lsum,tr[ls].sum+tr[rs].lsum);tr[s].rsum=max(tr[rs].rsum,tr[rs].sum+tr[ls].rsum);tr[s].sum=tr[ls].sum+tr[rs].sum;tr[s].msum=max(max(tr[ls].msum,tr[rs].msum),tr[ls].rsum+tr[rs].lsum);}void build(int l,int r,int id,vector<int>& nums){tr[id].l=l;tr[id].r=r;if(l==r){tr[id].sum=tr[id].lsum=tr[id].rsum=tr[id].msum=nums[l];return;}int mid=(l+r)>>1;build(l,mid,id<<1,nums);build(mid+1,r,id<<1|1,nums);pushup(id);}int maxSubArray(vector<int>& nums) {build(0,nums.size()-1,1,nums);return tr[1].msum;}
};合并区间
做法：这题在acwing算法基础课有，所以做起来很快。先给vector排序，按照左端点，空间复杂度O(logn)，时间复杂度O(nlogn)，然后遍历一遍vector即可。最后跳出循环后，不要忘记再push_back一次。
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end());//左端点从小到大排序int rp=-1;int lp=-1;vector<vector<int>> vec;for(const auto&x:intervals){if(rp==-1&&lp==-1){lp=x[0];rp=x[1];continue;}if(x[0]<=rp){rp=max(rp,x[1]);//合并}else{vec.push_back({lp,rp});lp=x[0],rp=x[1];}}vec.push_back({lp,rp});return vec;}
};轮转数组
做法一：开额外的空间，assign一下就好了
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());}
};做法二：
假设转了a圈回到当前位置，那么a*n就是走过的距离=b（每次遍历的元素）*k也就是步数*步距
每次循环都只需要一个变量prev来交换就可以了。
class Solution {
public:void rotate(vector<int>& nums, int k) {int n=nums.size();k%=n;int count=gcd(k,n);for(int i=0;i<count;i++){int current=i;int prev=nums[i];do{int next=(current+k)%n;swap(nums[next],prev);current=next;}while(i!=current)}}
};做法三：翻转数组，k%=n,那么后k个元素会被移动到开头，所以只需要整体翻转之后，再翻转头部和尾部就可以啦
class Solution {
public:void rotate(vector<int>& nums, int k) {k%=nums.size();reverse(nums.begin(),nums.end());reverse(nums.begin(),nums.begin()+k);reverse(nums.begin()+k,nums.begin()+nums.size());}
};
除自身数组以外的乘积
做法一，因为题目不让用除法。如果暴力的话复杂度达到O(n^2)，所以不妨采用预处理前缀后缀积的方法。
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<int> L(n,0),R(n,0);vector<int> answer(n);L[0]=1;for(int i=1;i<n;i++)L[i]=L[i-1]*nums[i-1];R[n-1]=1;for(int i=n-2;i>=0;i--)R[i]=R[i+1]*nums[i+1];for(int i=0;i<n;i++)answer[i]=L[i]*R[i];return answer;}
};做法二：其实差不多，只是更节省内存了而已，小优化
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n=nums.size();vector<int> answer(n);answer[0]=1;for(int i=1;i<n;i++)answer[i]=nums[i-1]*answer[i-1];int R=1;for(int i=n-1;i>=0;i--){answer[i]=answer[i]*R;R*=nums[i];}return answer;}
};缺失的第一个正数
做法：首先 这个数字一定在[1,n+1]之间，因为如果n数组为[1,n]，那么就为n+1，否则的话就是[1,n]。因为这道题没有办法用哈希表，也不能用双重循环，所以就要利用已有的空间进行类似哈希表的标记。如果我们想让整数1被标记已经出现过了，我们没有办法改变数组值，但是可以加上负号，让nums[0]=-abs(nums[0])即可，后面再进行一次循环，只要读到一个负数，那么这个位置就是答案。
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;}
};做法二：还是要利用这个数组，假如存在数字3，那么就和数组nums[3-1]元素交换，直到该位置元素不属于[1,n]，要注意要在相等的时候跳出循环。如果最后某个位置一直没有换。那么说明，这个位置不存在对应元素
class Solution {
public:int firstMissingPositive(vector<int>& nums) {int n=nums.size();for(int i=0;i<n;i++){while(nums[i]>0&&nums[i]<=n&&nums[nums[i]-1]!=nums[i]){swap(nums[nums[i]-1],nums[i]);}}for(int i=0;i<n;i++)if(nums[i]!=i+1)return i+1;return n+1;}
};矩阵置零
做法一：直接暴力
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {int m=matrix.size();int n=matrix[0].size();vector<int> row(m),col(n);for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(!matrix[i][j])row[i]=col[j]=true;}}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(row[i]||col[j])matrix[i][j]=0;}}}
};做法二：之前的做法需要O(m+n)的空间，但其实可以缩减到常量级空间，所以，我们必须要利用已经存在的空间。先开两个常量，用来判断第一行和第一列需不需要全部置0，然后用第一行第一列来判断。如果某一位置的元素为0，那么第一行第一列对应元素置0，如果本来就为0，那也是一样的。
class Solution {
public:void setZeroes(vector<vector<int>>& matrix) {bool flag_row=false,flag_col=false;int n=matrix.size();//行int m=matrix[0].size();//列;for(int i=0;i<m;i++){if(matrix[0][i]==0){flag_row=true;break;}}for(int i=0;i<n;i++){if(matrix[i][0]==0){flag_col=true;break;}}for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(matrix[i][j]==0)matrix[i][0]=matrix[0][j]=0;for(int i=1;i<n;i++)for(int j=1;j<m;j++)if(matrix[i][0]==0||matrix[0][j]==0){matrix[i][j]=0;}if(flag_row)for(int i=0;i<m;i++)matrix[0][i]=0;if(flag_col)for(int i=0;i<n;i++)matrix[i][0]=0;}
};螺旋矩阵
做法一：设计一个标记数组即可，因为每次转向方向固定，所以可以用一个数组来存储要转向的方向，变动方向的时候只需要加一即可
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size()==0||matrix[0].size()==0)return {};int rows=matrix.size(),cols=matrix[0].size();vector<vector<bool>> visited(rows,vector<bool>(cols,false));int count=rows*cols;vector<int> ans(count);int row=0,col=0;int index=0;for(int i=0;i<count;i++){ans[i]=matrix[row][col];visited[row][col]=true;int nerow=row+dir[index][0],necol=col+dir[index][1];if(nerow<0||nerow>=rows||necol<0||necol>=cols||visited[nerow][necol])index=(index+1)%4;row+=dir[index][0];col+=dir[index][1];}return ans;}
};做法二：不开标记数组，直接设置四个指针，然后遍历。要注意的是，需要考虑一种情况，[[2],[3]]，也就是一列下来有两行，如果不特判一下，下面会多存
class Solution {
public:vector<int> spiralOrder(vector<vector<int>>& matrix) {if(matrix.size()==0||matrix[0].size()==0)return {};int rows=matrix.size(),columns=matrix[0].size();vector<int> ans;int left=0,right=columns-1,top=0,bottom=rows-1;while(left<=right&&top<=bottom){for(int column=left;column<=right;column++){ans.push_back(matrix[top][column]);//cout<<1;}for(int row=top+1;row<=bottom;row++){ans.push_back(matrix[row][right]);//cout<<2;}if(right>left&&bottom>top){for(int column=right-1;column>left;column--){ans.push_back(matrix[bottom][column]);//cout<<3;}for(int row=bottom;row>top;row--){ans.push_back(matrix[row][left]);//cout<<4;}}left++;right--;top++;bottom--;}return ans;}};旋转图像
做法一：需要额外空间的做法。观察可得式子。每一行九十度旋转后，都对应旋转后的一列。满足matrix[row][col]->matrix_new[col][n-row-1]
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();auto m1=matrix;for(int i=0;i<n;i++)for(int j=0;j<n;j++){m1[j][n-i-1]=matrix[i][j];}matrix=m1;}
};做法二：不需要额外矩阵空间.但需要注意 当为奇数的时候 (n^2-1)/4=(n+1)/2*(n-1)/2。
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++)for(int j=0;j<(n+1)/2;j++){int temp=matrix[i][j];matrix[i][j]=matrix[n-j-1][i];matrix[n-j-1][i]=matrix[n-i-1][n-j-1];matrix[n-i-1][n-j-1]=matrix[j][n-i-1];matrix[j][n-i-1]=temp;}}
};做法三：进行翻转.我们画一个简单图就能发现，先进行水平轴翻转再进行主对角线（左上到右下）翻转就能得到相应翻转矩阵。推导如下
水平轴翻转：matrix[row][col]->matrix[n-row-1][col]
主对角线翻转：matrix[n-row-1][col]->matrix[col][n-row-1]。这其实就和那个式子一样了
class Solution {
public:void rotate(vector<vector<int>>& matrix) {int n=matrix.size();for(int i=0;i<n/2;i++){for(int j=0;j<n;j++){swap(matrix[i][j],matrix[n-i-1][j]);}}for(int i=0;i<n;i++)for(int j=0;j<i;j++)swap(matrix[i][j],matrix[j][i]);}
};搜索二维矩阵
解法一：对每一行二分，时间复杂度O(mlogn)，空间复杂度O(1)，用lower_bound，其本质就是二分。代码如下
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {for(const auto &row:matrix){auto it=lower_bound(row.begin(),row.end(),target);if(it!=row.end()&&*it==target)return true;}return false;}
};解法二： 从矩阵右上角开始判断，这个真的有点难想
class Solution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {int m=matrix.size(),n=matrix[0].size();int x=0,y=n-1;while(x<m&&y>=0){if(matrix[x][y]==target)return true;if(matrix[x][y]>target)y--;else x++;}return false;}
};相交链表
做法一：曾经不知道什么时候做过，哎，大一的时候为啥不好好努力呢。用一个set来存储，一个先遍历，然后每个都存入，另外一个逐渐遍历即可
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*>visited;ListNode *temp=headA;while(temp!=nullptr){visited.insert(temp);temp=temp->next;}temp=headB;while(temp!=nullptr){if(visited.count(temp))return temp;temp=temp->next;}return nullptr;}
};做法二：双指针，分别遍历两条链表，这个真的太妙了。力扣官方的题解解释的很清楚
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==NULL||headB==NULL)return NULL;ListNode *pa=headA,*pb=headB;while(pa!=pb){pa=pa==NULL?headB:pa->next;pb=pb==nullptr?headA:pb->next;}return pb;}
};4.1 22：02结束今日学习，还是得提高效率，加油，争取能在这周清明假期结束之前结束一百题
