1定长滑动窗口
1进入窗口，更新当前符合条件的值
2更新答案
3离开窗口，更新当前符合条件的值
2不定长滑动窗口
2.1求最长最大
当窗口向右扩增检测到不符合条件时，将窗口左侧不断缩小直到符合条件，记录窗口在变化过程中的最大值
2.2求最小
当窗口向右扩增检测到满足条件时，将left指针右移直到不满足条件，每次右移更新ans
使用双指针，循环结束后将两个指针都移动到最右端，满足条件时，左指针右移，但不能超过右指针，直到不满足条件，每次右移检查左右指针切割产生的子数组大小和答案的比较，取最小值，每一轮循环结束时将右指针右移
ans = move(t);字符串的直接赋值
2.3求子数组个数
2.3.1越长越合法
写ans+=left，每次循环读入新的元素，然后检查是否满足合法条件，使用一个while循环不断++left数值，并更新条件变量直到不满足，再将ans+=left即可，一般有合法字眼
2.3.2越短越合法
一般要写 ans += right - left + 1，每次循环读入新的元素然后检查是否满足合法条件，使用while循环不断删去left的数值，更新条件变量直到满足条件，接下来+=right-left+1，这个right一般用i来代替
2.3.3恰好型滑动窗口
计算元素相加恰好满足条件k
int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;int count = 0, pre = 0;for (int i = 0;i<nums.size();i++) {mp[pre]++;pre += nums[i];if (mp.find(pre - k) != mp.end()) {count += mp[pre - k];}}return count;
}
可以分解成两个数组，满足至少为k和至少为k+1，即两个越长越合法问题，再用至少为k的ans减去至少为k+1的ans即可
也可以变为两个至多，即满足至多为k和至多为k-1
热题100
1哈希
t1数组找相加为target的元素下标，关键是find target-numi
做法：使用哈希表储存已经寻找过target-nums[i]的元素，每次储存前使用find函数寻找是否存在对应元素，若存在则直接返回，否则继续存入，只要On即可
t2字母异位词分组 排序并作为关键字存入哈希表
求一个字符串数组中字母异位词的分组，字母异位词即字母相同，字母的数量相同，但是字母位置不同
做法：对字符串进行排序，如果两个词是字母异位词，则排序结果相同，将排序结果作为key存入哈希表即可
t3最长连续序列,set储存原数组并遍历
求一个非顺序数组中最长的连续整数序列（不要求连续）
不要求在原数组中连续，这里不能用滑动窗口解（好像可以直接sort然后使用滑动窗口，不过需要on时间复杂度所以可能有点问题）
做法：先用set储存原数组，方便后续查找；遍历set，使用count作为查找函数，如果存在元素自身-1的对象，则跳过该元素，如果不存在，则从该元素开始向后枚举，每次+1直到不存在对象，同时记录长度，使用一个ans保存最大长度最后返回
//遍历一次使用set储存全部数字
unordered_set<int> num_set;
for (const int& num : nums) {num_set.insert(num);
}int longestStreak = 0;
//遍历set，使用count作为查找函数，如果存在count会返回1
for (const int& num : num_set) {//如果当前数字不存在前缀数if (!num_set.count(num - 1)) {//从当前数字开始向后枚举计算序列长度int currentNum = num;int currentStreak = 1;//如果能找到后缀数，则继续向后枚举while (num_set.count(currentNum + 1)) {currentNum += 1;currentStreak += 1;}//将序列长度和最长长度比较得到结果longestStreak = max(longestStreak, currentStreak);}
}return longestStreak;
2双指针
t1移动零，slow维护第一个0的位置
将所有0移动到数组最右且不影响其他元素的相对顺序
以下是高级解法，只需要一个指针，另一个指针用i代替，正常的双指针是使用while和两个指针
SLOW初值为0，每次交换后++，得到下一个要被交换的对象，如果numi非0则进行交换，确保了slow位置前是正常顺序且没有0
从左向右遍历，遇到非0时，将非0元素和slow对应的0交换位置即可
int slow = 0;
for (int i = 0; i < nums.size(); i++) {if (nums[i] != 0) {// 每次保证是0和非0的交换swap(nums[slow++], nums[i]);}
}
正常解法，使用while循环，结束条件是right>=nums.size，即右指针指到数组结尾，左指针一直指向正确序列的末尾，右指针指向待处理序列的头部即左右指针中间部分是0，左指针一直指向第一个0
int left =0,right = 0;
while(right<nums.size()){if(nums[right]){//右指针指到非0数，说明右指针右侧还可以被整理swap(nums[right],nums[left]);left++;//左边序列可以增大一位}//右指针增加right++;
}
t2盛最多水的容器，停止条件是垂线长度大于高
计算一个垂线长度数组中由任意两条垂线和它们之间的x轴构成的容器最大值
解法：使用left=0,right=size-1代表左和右的垂线位置，while的条件是（left<right）每次循环都计算容器的高（为l和r的垂线长度最小值）和底（r-l），将计算出的容器大小和ans比较取最大值，接下来使用两个while循环，当left对应垂线<=高时，left右移，移至垂线>高为止，right同理左移，需要注意两个while循环还有额外的结束条件即left<right
int ans = 0;int left = 0,right = height.size()-1;int high = 0;while(left<right){high=min(height[left],height[right]);ans = max(ans,(right-left)*high);while(height[left]<=high&&left<right)left++;while(height[right]<=high&&left<right)right--;}return ans;
t3三数之和，关键是去重
求一个数组中三数之和为0的所有子序列，且不能重复
解法：将数组排序，从起始点开始for循环遍历，遍历的元素若大于0，则break；去重，若起始值等于上一个元素，则continue，因为得到的结果会与上一次相同；
前面条件都满足之后，设置两个指针l=i+1，r=n-1，while循环条件l<r，循环开始
判断lri三者相加是否为0
为0则加入结果集，进入下一步两个while循环去重，如果l+1=l，则l++，如果r-1=r则r--直到不符合条件，最后再次将l++，r--；
如果不为0，则结果<0则l++；结果>0则r--（这里也可以使用去重）；
if(nums.size()<3)return{};
vector<vector<int>>ans;
sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i++){if(nums[i]>0)break;if(i>0&&nums[i]==nums[i-1])continue;int l=i+1,r=nums.size()-1;while(l<r){if(nums[i]+nums[l]+nums[r]==0){ans.push_back({nums[i],nums[l],nums[r]});while(l<r&&nums[l]==nums[l+1])l++;while(l<r&&nums[r]==nums[r-1])r--;l++;r--;}else if(nums[i]+nums[l]+nums[r]<0)l++;else r--;}
}
return ans;
t4接雨水，双指针，用层数作为停止条件
非常好解法使我大脑旋转
定义一个双指针，以及层数h=1，双指针在两头往中间移动，只要指针大于等于h，就停下来
目的：当两边指针都停下来的时候，计算第一层的面积（直接左指针减右指针+1），然后h++计算第二层的面积，以此类推计算每一层的面积，然后用这个面积减去height的和，剩下的就是水量了
int l=0,r=height.size()-1;int sumh = 0;//计算边缘线段长for(int i =0;i<r+1;i++){sumh+=height[i];}int sum =0;int h =1;//每次上升1层，当lr都大于等于该层时计算该层的大小，相当于吧整个图看做金字塔，一层层计算while(l<=r){while(l<=r&&height[l]<h){l++;}while(l<=r&&height[r]<h){r--;}sum+=r-l+1;h++;}sum-=sumh;return sum;
3滑动窗口
t1无重复字符的最长子串，不定长滑动窗口，求最大
使用最大滑动窗口，使用一个哈希表记录字符数量，记录一个l，当li之间的内容不满足要求（当前的i在哈希表中可以找到，说明i字符重复）时，使用while清除哈希表中，l代表的字符并l++；每个for循环比较一次ans和i-l+1的最大值，并插入当前i代表的字符；
int n = s.length();
unordered_set<char> set;
int sum = 0;
int left = 0;
for(int i =0;i<n;i++){while(set.find(s[i])!=set.end())set.erase(s[left++]);sum=max(sum,i-left+1);set.insert(s[i]);
}
return sum;
t2找字母异位词，定长滑动窗口，vector比较功能
定长滑动窗口，这里确定ans的条件是使用vector的比较功能，vector如果相同说明字符的数量相同
建立两个vector，一个用来储存给定的目标字符串各个字符的数量，一个用来储存滑动窗口内字符的数量，使用for循环遍历源字符串，滑动窗口大小是目标字符串的长度，if判断两个vector是否相等；使用定长的模版即可
vector<int> c(26);
vector<int> sc(26);
vector<int>ans;
int k = p.size();
for(int i = 0;i<p.size();i++){c[p[i]-'a']++;
}
for(int i =0;i<s.size();i++){sc[s[i]-'a']++;if(i<k-1)continue;if(c==sc)ans.push_back(i-k+1);sc[s[i-k+1]-'a']--;
}
return ans;
4子串
t1和为k的子数组，前缀和
初看可以视作一个恰好为k的滑窗问题，这里编写新函数采用至少为k进行计算（这里不能用滑窗）
所以本题采用前缀和
这里给出前缀和的基础写法：
1首先你有一个随机的数组
2建立一个vector或者数组p，将首位设为0，即p[0]=0
3遍历你的数组，i设为1，i<size+1；每次循环p[i]=p[i-1]+nums[i-1]
END
我的写法：先计算前缀和，再嵌套for循环，外循环和内循环都遍历p，j从i+1开始，每个内循环都检查ij前缀和相减的结果是否等于k，若相等则ans++，这种方法和枚举实际上并无区别，甚至连时间都差不多
高级写法：通过前缀和和hash表得到答案，建立pre和map，遍历数组，每次都让pre加上当前元素，检查mp中是否存在pre-k的元素（只要当前前缀和减去这个前缀和就能得到k），若存在，则ans+mp[pre-k]，不存在则不操作，循环结束前mp[pre]++
t2滑动窗口最大值（优先队列或双端队列）
滑动窗口每次向右一格，给出整个滑窗过程中每次移动后的元素最大值
这里采用优先队列做，使用pair<int,int>创建优先队列，优先队列会根据第一个int自动排序，第二个int作为寿命进行储存，每次向右滑动时，将新元素进入优先队列，同时加载其寿命，再对栈顶元素进行检测，如果寿命到了滑窗之外则进行pop，最后将符合条件的栈顶元素记录进结果集中
vector<int>ans;
//单调队列维护
priority_queue<pair<int, int>> q;
for(int i =0;i<nums.size();i++){q.emplace(nums[i],i);if(i<k-1)continue;while(q.top().second<i-k+1){q.pop();}ans.push_back(q.top().first);}
return ans;
解法2 On 使用双端队列，队列内储存的是元素的入栈位置，但是按照元素大小进行排序，每个新入栈的元素都需要和栈尾元素比较，如果大于栈尾元素，则栈尾出栈（因为原来的栈尾元素寿命肯定小于新入栈元素，如果小于新元素则永远不会轮到它做最大值）直到找到新元素适合的栈尾，结束循环并让新元素入栈，此时再对栈顶进行处理，如果栈顶元素的寿命已尽，则使其出栈，直到栈顶寿命合适，结束循环，最后将栈顶位置代表的值记录进结果集中
deque<int>q;
vector<int>ans;
for(int i = 0;i<nums.size();i++){while(!q.empty()&&nums[i]>=nums[q.back()])q.pop_back();q.push_back(i);while(q.front()<i-k+1)q.pop_front();if(i<k-1)continue;ans.push_back(nums[q.front()]);
}
return ans;
t3最小覆盖子串（不定长滑动窗口）
给出字符串s和t，返回s中覆盖t的最小子串（不要求顺序）
编写一个judge函数，用来判断map1是否覆盖map2
使用map2来储存t中所有字母的数量
主函数：
1初始化ans，left，和ansl（ans和ansl是用来返回最小覆盖子串的，left记录当前窗口的最左位置）
2遍历整个源字符串，每次将新字符加入map1中，并检查judge条件，如果符合，更新ans和ansl，将left增加缩小窗口
3使用ans和ansl返回最小覆盖子串
5普通数组
t1最大子数组和（分治或者动规）
这里使用分治法做，有三种可能
1最大值在mid左侧
2最大值在mid右侧
3最大值包含mid
这里需要单独给第三种情况写一个计算函数，设l mid r，计算包含mid的左区间最大值，再计算包含mid的右区间最大值，最后返回两者相加
分治函数的退出条件是l==r，直接返回num[l]即可
int maxSubArray(vector<int>& nums) {int n = int(nums.size());int result =0;result = rtmaxlr(nums,0,n-1);return result;
}int rtmaxlr(vector<int>&nums,int l,int r){if(l==r){return nums[l];}int mid = (l+r)/2;int lmax = rtmaxlr(nums,l,mid);int rmax = rtmaxlr(nums,mid+1,r);int midmax = rtmaxcross(nums,l,mid,r);int result = max(lmax,rmax);result = max(result,midmax);return result;}
int rtmaxcross(vector<int>&nums,int l,int mid,int r){int leftsum = INT_MIN;int sum = 0;for(int i =mid;i>=l;i--){sum+=nums[i];leftsum=max(leftsum,sum);}int rightsum= INT_MIN;sum=0;for(int i =mid+1;i<=r;i++){sum+=nums[i];rightsum=max(rightsum,sum);}return (leftsum+rightsum);
}
也可以采用动态规划法做：
需要消除后效性，dp的元素表示以i结尾的连续子数组的最大值，可以得知dpi=dpi-1+nums[i]或dpi=nums[i]，取决于dpi-1是否小于0
在动规过程中记录最大值即可
dp[i]=max(dp[i-1]+nums[i],nums[i])
因此可以写出
//动规,dpi是包含numsi的子数组最大和
int dp[100010];
dp[0]=nums[0];
int ans = dp[0];
for(int i = 1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);ans=max(dp[i],ans);
}
return ans;
t2合并区间，暴力法（先排序再根据左边界合并）
直接使用暴力也很快，设置一个start和end记录区间开头和结尾，初始值设为给出的第1个区间
将所有区间按照左边界排序
遍历所有区间，被遍历的区间如果左边界大于end，则原来的start和end记录进结果集，start和end设为该区间
否则end值取end和当前区间右边界的最大值
//暴力
//将所有区间按照左边界排序
sort(intervals.begin(),intervals.end());
vector<vector<int>>ans;
int start = intervals[0][0];
int end = intervals[0][1];
for(int i = 1 ;i<intervals.size();i++){if(intervals[i][0]>end){ans.push_back({start,end});start = intervals[i][0]; }end = max(end,intervals[i][1]);
}
ans.push_back({start,end});
return ans;
t3轮转数组，三次反转法
暴力解法，直接建立新数组，将原数组和新数组的位置对应调换即可
//暴力，建立一个新数组，将旧数组导入新数组
int n = nums.size();
vector<int>ans;
for(int i = 0;i<n;i++){ans.push_back(nums[(n-k%n+i)%n]);
}
nums = ans;
空间复杂度1的解法
三次反转法
先将整个数组反转，再将前k个和后n-k个分别反转即可
int n = nums.size();
k=k%n;
int l =0,r=n-1;
while(l<r){swap(nums[l++],nums[r--]);
}
l=0;
r=k-1;
while(l<r){swap(nums[l++],nums[r--]);
}
l=k;
r=n-1;
while(l<r){swap(nums[l++],nums[r--]);
}
t4除自身以外数组的乘积
vector<int>ans;
int pre =1;//map<int,int>dp;
int suf =1;//map<int,int>pp;
//dp[0]=1;
for(int i = 0;i<nums.size();i++){//dp[i]=dp[i-1]*nums[i-1];ans.push_back(pre);pre*=nums[i];
}
for(int i = nums.size()-1;i>-1;i--){//pp[i]=pp[i+1]*nums[i+1];ans[i]*=suf;suf*=nums[i];
}
/*
for(int i = 0;i<nums.size();i++){ans.push_back(dp[i]*pp[i]);
}
*/
return ans;
t5缺失的第一个正数
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;
6矩阵
t1矩阵置0
要求Om*n 空间复杂度常数
方法是利用第0行和第0列作为标记列，将它们自身的0留到最后处理，第一次遍历整个矩阵，遇到0就在第0行和第0列的对应位置标记，第二次遍历根据第0行和第0列对矩阵进行处理，最后根据一开始0行0列是否有0，对0行0列进行置零
bool row =false,col = false;
int m = matrix.size();
int n = matrix[0].size();
for(int i=0;i<n;i++){if(matrix[0][i]==0){row=true;break;}
}
for(int i=0;i<m;i++){if(matrix[i][0]==0){col = true;break;}
}
for(int i=1;i<m;i++){for(int j = 1;j<n;j++){if(matrix[i][j]==0){matrix[i][0]=0;matrix[0][j]=0;}}
}
for(int i=1;i<m;i++){for(int j = 1;j<n;j++){if(matrix[i][0]==0||matrix[0][j]==0){matrix[i][j]=0;}}
}
if(row){for(int i = 0;i<n;i++){matrix[0][i]=0;}
}
if(col){for(int i = 0;i<m;i++){matrix[i][0]=0;}
}
t2螺旋矩阵
顺时针螺旋返回矩阵中所有元素
直接暴力遍历一次即可，需要的是编写好边界条件，这个方法为模拟法
int l = -1,r = matrix[0].size(),t = -1,b = matrix.size();
int condition =0;
int maxsize = r*b;
int count = 0;
int i=0,j=0;
vector<int>ans;
while(count<maxsize){ans.push_back(matrix[i][j]);count++;if(condition==0){j++;if(j==r){j--;i++;t++;condition=1;}}else if(condition==1){i++;if(i==b){i--;j--;r--;condition=2;}}else if(condition==2){j--;if(j==l){j++;i--;b--;condition=3;}}else if(condition==3){i--;if(i==t){i++;j++;l++;condition=0;}}
}
return ans;
t3旋转图像
要求是原地旋转，这题是数学问题，需要将整个矩阵按照对角线翻转，再逐行逆序即可
for(int i = 0;i<matrix.size();i++){for(int j = i;j<matrix.size();j++){swap(matrix[i][j],matrix[j][i]);}
}
for(int i =0;i<matrix.size();i++){for(int j = 0;j<matrix.size()/2;j++){swap(matrix[i][j],matrix[i][matrix.size()-1-j]);}
}
t4 搜索二维矩阵
从左到右升序，从上到下升序
从右上角开始，向左则变小，向下则变大，可知如果ij大于target则向左，小于则向下；
由此可以通过二叉搜索树得到答案
int m = matrix.size();
int n = matrix[0].size();
int i=0,j=n-1;
while(j>-1&&i<m){if(target==matrix[i][j])return true;else if(target<matrix[i][j])j--;else i++;
}
return false;
7链表
t1相交链表，双指针循环相交点
让两个指针不断向后循环，如果循环到空指针则跳到另一个链表的起点，直到两个指针相等
ListNode *a = headA;
ListNode *b = headB;
while(a!=b){a=a->next;b=b->next;if(a==NULL&&b!=NULL)a=headB;else if(b==NULL&&a!=NULL)b=headA;}
return a;
t2反转链表，pre暂存上一个头部
给出head，要求反转链表并返回
使用一个pre暂存已反转链表头部（初始时为NULL），使用cur指针暂存未反转链表头部即可
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur) {ListNode* nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;
}
return pre;
评论说可以使用头插法，每次将cur的next插到head前，其实和这个是一样的
t3回文链表，快慢指针加反转链表
判断一个链表是否为回文链表
我想到的方法是使用两个指针，一个指向链表尾部（单向链表行不通，放弃)
使用栈，会有特殊情况导致失效
最简单的方法是输出到数组中，再通过双指针遍历到中心检查是否为回文
看题解发现双指针可行，但是需要翻转链表和寻找链表中心值（中心值可以用快慢指针去找）
ListNode* middleNode(ListNode* head) {//快慢指针查找中心值ListNode* slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}
ListNode* reverseList(ListNode* head) {//翻转链表ListNode* pre = nullptr, *cur = head;while (cur) {ListNode* nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}
bool isPalindrome(ListNode* head) {//利用快慢指针和反转链表获取和数组一样的效果，从两端开始遍历ListNode* mid = middleNode(head);ListNode* head2 = reverseList(mid);while (head2) {if (head->val != head2->val) { // 不是回文链表return false;}head = head->next;head2 = head2->next;}return true;
}
t4环形链表，快慢指针
给你一个链表的头节点 head ，判断链表中是否有环。
初步想法是利用快慢指针，如果快指针能走到NULL则说明没有环，如果快指针和慢指针重合说明有环
ListNode *f = head;
ListNode *s = head;
while(f!=NULL){if(f->next!=NULL)f=f->next->next;else break;s=s->next;if(s==f)return true;
}
return false;
t5环形链表2，快慢指针
需要返回入环开始的节点
快慢指针，由于P2=2*P1当他们相遇时走的长度是3*P1，设环的长度是y，环前的长度是x，x+y是全长，可知p1=x+c，p2=x+c+ny，所以p1=ny，同时可以得知x+ny也是入环点，此时将快指针设置为head，和p1一起next循环，相遇时就可以得到入环点
if(head==NULL)return head;
ListNode *s = head;
ListNode *f = head;
do{if(f->next==NULL||f->next->next==NULL)return NULL;s=s->next;f=f->next->next;
}while(s!=f);
f=head;
while(s!=f){s=s->next;f=f->next;
}
return s;
t6合并两个有序链表，new节点加递归
使用递归进行插入
if(list1==NULL)return list2;
if(list2==NULL)return list1;
ListNode *tmp = new ListNode();
if(list1->val>list2->val){tmp->val=list2->val;tmp->next=mergeTwoLists(list1,list2->next);
}else{tmp->val=list1->val;tmp->next=mergeTwoLists(list1->next,list2);
}
return tmp;
t7两数相加，使用pre指针保证特殊条件，使用j储存进位
单纯的两数相加
int j = 0;
ListNode *p=l1;
ListNode *pre;
while(p!=NULL&&l2!=NULL){int sum = p->val+l2->val+j;j=sum/10;p->val=sum%10;pre = p;p=p->next;l2=l2->next;
}
if(l2!=NULL){pre->next=l2;p = l2;
}
while(p!=NULL){int sum =p->val+j;j=sum/10;p->val=sum%10;pre = p;p=p->next;
}
if(j!=0){ListNode* tmp = new ListNode();tmp->val=j;pre->next=tmp;
}
return l1;t8删除链表的倒数第n个结点
感觉也可以递归
感觉可以用快慢指针实现，倒数第几个就向后n几次，特殊情况是第n个结点刚好是头部，则需要将head向后移一位
ListNode* f=head;
ListNode* s=head;
ListNode* pre;
for(int i = 0;i<n;i++){f=f->next;
}
while(f!=NULL){f=f->next;pre = s;s=s->next;
}
if(s!=head)pre->next=s->next;
else head = s->next;
return head;
t9两两交换链表中的节点
递归即可，递归退出条件是head后为空或者head为空
if(head==NULL||head->next==NULL)return head;
ListNode *p1=head;
ListNode *p2=head->next;
p1->next=swapPairs(p2->next);
p2->next=p1;
return p2;
t10K个一组翻转链表
使用递归
首先使用计数器验证当前头部向后k位是否存在，如果不存在则直接返回当前头部
其次优先翻转后面的，所以直接用第k位当头部递归
再处理当前部分，使用计数器和反转链表方法（pre和cur）翻转前k位
最后返回pre即可
ListNode *pre=head;
ListNode *q = head;
int count = 0;
while(count<k&&pre!=NULL){pre = pre->next;count++;
}
if(count<k)return head;
pre = reverseKGroup(pre,k);
count=0;
while(count<k){ListNode *nxt=q->next;q->next=pre;pre = q;q=nxt;count++;
}
return pre;
t11随机链表的复制（深拷贝）
使用哈希表进行源地址到新地址的映射，所以第一次遍历原链表时，只建立新的节点而不给新节点中的next和random赋值
第二次遍历再进行赋值
unordered_map<Node*,Node*>map;
Node* p=head;
while(p!=NULL){Node*ptr=new Node(p->val);map[p]=ptr;p=p->next;
}
p=head;
while(p!=NULL){Node*ptr = map[p];if(p->next!=NULL)ptr->next=map[p->next];if(p->random!=NULL)ptr->random=map[p->random];p=p->next;
}
return map[head];
t12排序链表
感觉可以使用优先队列进行排序，实践可行，因为没有要求（但是很可能不让用优先队列，所以还是需要下面的题解）
typedef pair<int,ListNode*> pairint;
ListNode* sortList(ListNode* head) {if(!head)return head;priority_queue<pairint,vector<pairint>,greater<pairint>>q;ListNode*p=head;while(p){q.push({p->val,p});p=p->next;}head=q.top().second;q.pop();p=head;while(!q.empty()){p->next=q.top().second;q.pop();p=p->next;}p->next=NULL;return head;
}
如果要求常数级空间，则需要快慢指针归并法
1找中点middle
2cut
3merge
其中middle和merge都需要编写对应函数封装
快慢指针用来寻找中点，cut过程为断开中点左右节点防止乱序
public ListNode sortList(ListNode head) {// 1、递归结束条件if (head == null || head.next == null) {return head;}// 2、找到链表中间节点并断开链表 & 递归下探ListNode midNode = middleNode(head);ListNode rightHead = midNode.next;midNode.next = null;ListNode left = sortList(head);ListNode right = sortList(rightHead);// 3、当前层业务操作（合并有序链表）return mergeTwoLists(left, right);
}// 找到链表中间节点（876. 链表的中间结点）
private ListNode middleNode(ListNode head) {if (head == null || head.next == null) {return head;}ListNode slow = head;ListNode fast = head.next.next;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}return slow;
}// 合并两个有序链表（21. 合并两个有序链表）
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode sentry = new ListNode(-1);//假的头结点ListNode curr = sentry;while(l1 != null && l2 != null) {if(l1.val < l2.val) {curr.next = l1;l1 = l1.next;} else {curr.next = l2;l2 = l2.next;}curr = curr.next;}//有一方遍历完直接接上另一个链表的后段curr.next = l1 != null ? l1 : l2;return sentry.next;
}
t13合并k个升序链表
使用递归，每次合并两个链表并将新的链表插入list中
需要特判输入为空的情况，需要用到stl的部分函数
ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size()==0)return NULL;if(lists.size()==1)return lists[0];ListNode* l1 = lists[0];ListNode* l2 = lists[1];lists.erase(lists.begin(),lists.begin()+2);ListNode* dm = new ListNode(-1);ListNode* cur = dm;while(l1!=NULL&&l2!=NULL){if(l1->val>l2->val){cur->next=l2;l2=l2->next;}else{cur->next=l1;l1=l1->next;}cur=cur->next;}cur->next=l1==NULL?l2:l1;lists.push_back(dm->next);return mergeKLists(lists);
}
t14LRU缓存
需要用到双向链表加哈希表的算法
需要自己实现双向链表，因此自己写一个struct
struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};
使用map储存值和节点，用来get和put的时候使用
初始化LRU缓存时，创建链表需要一个头结点和尾节点，不保存任何值
get时，通过map的count查找，如果不存在则返回-1，如果存在则用map找到对应节点，将节点移到头部
put时，通过map的count查找，如果不存在则创建新的节点，添加至双向链表的头部，再检查是否超出容量，若超出则从尾结点开始删除直到符合容量，如果存在则直接修改，将节点移到头部
超长超麻烦
struct DLinkedNode {int key, value;DLinkedNode* prev;DLinkedNode* next;DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};class LRUCache {
private:int capacity;int size;DLinkedNode*head;DLinkedNode*tail;unordered_map<int,DLinkedNode*>map;
public:LRUCache(int _capacity):capacity(_capacity),size(0) {head = new DLinkedNode();tail = new DLinkedNode();head->next = tail;tail->prev = head;}int get(int key) {if(!map.count(key))return -1;movetohead(map[key]);return map[key]->value;}void put(int key, int value) {if(!map.count(key)){DLinkedNode* node = new DLinkedNode(key,value);map[key]=node;addtohead(node);size++;if(size>capacity){DLinkedNode* removed=removetail();map.erase(removed->key);delete removed;size--;}}else{map[key]->value=value;movetohead(map[key]);}}void deletenode(DLinkedNode*node){node->prev->next=node->next;node->next->prev=node->prev;}void movetohead(DLinkedNode*node){deletenode(node);addtohead(node);}DLinkedNode* removetail(){DLinkedNode* node = tail->prev;deletenode(node);return node;}void addtohead(DLinkedNode*node){head->next->prev=node;node->next=head->next;node->prev=head;head->next=node;}
};8二叉树
t1二叉树的中序遍历
递归解决，先向答案中输入root的值，再利用递归输入左子树再输入右子树最后返回
vector<int> inorderTraversal(TreeNode* root) {if(root==NULL)return{};vector<int>ans;vector<int>left=inorderTraversal(root->left);vector<int>right=inorderTraversal(root->right);ans.insert(ans.end(),left.begin(),left.end());ans.push_back(root->val);ans.insert(ans.end(),right.begin(),right.end());return ans;
}
迭代法则是用栈来做
t2二叉树的最大深度
同样是用递归去遍历左右子树
int rtdepth(TreeNode* root,int depth){if(!root)return depth-1;return max(rtdepth(root->left,depth+1),rtdepth(root->right,depth+1));
}
int maxDepth(TreeNode* root) {return rtdepth(root,1);
}
t3翻转二叉树
同样使用递归解决即可，先翻转子树再翻转根
TreeNode* invertTree(TreeNode* root) {if(!root)return root;TreeNode*left=root->left;TreeNode*right=root->right;invertTree(left);invertTree(right);root->left=right;root->right=left;return root;
}
t4对称二叉树
我的想法是从根节点的左右子树开始用两个中序遍历检查
递归思路是检查两个指针节点是否相等，再检查左节点的左子树和右节点的右子树，左节点的右子树和右节点的左子树是否相等
bool checklr(TreeNode*left,TreeNode*right){if(!left&&!right)return true;else if(!left)return false;else if(!right)return false;if(left->val!=right->val)return false;else return checklr(left->left,right->right)&&checklr(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {if(!root)return true;TreeNode* ptrl = root->left;TreeNode* ptrr = root->right;return checklr(ptrl,ptrr);
}
t5二叉树的直径
看评论的思路是，对每个节点，计算其左右子树深度，计算经过该节点的路径最大值（路径不包括其根节点）和其左右子树路径最大值，使用递归遍历所有节点，返回该节点和左右子树路径最大值的最大值
int diameterOfBinaryTree(TreeNode* root) {if(!root||!root->left&&!root->right)return 0;int leftmax = diameterOfBinaryTree(root->left);int rightmax = diameterOfBinaryTree(root->right);int cmax = rtdepth(root->left,1)+rtdepth(root->right,1);return max(max(leftmax,rightmax),cmax);
}
int rtdepth(TreeNode* root,int depth){if(!root)return depth-1;return max(rtdepth(root->left,depth+1),rtdepth(root->right,depth+1));
}
使用DFS进行查找，每个节点向下延伸，如果当前节点是null则返回负一，节点向下dfs时自动加一，每个节点使用max更新全局的ans，
int ans;
int dfs(TreeNode* node){if(node==nullptr)return -1;int llen = dfs(node->left)+1;int rlen = dfs(node->right)+1;ans = max(ans,llen+rlen);return max(llen,rlen);
}
int diameterOfBinaryTree(TreeNode* root) {ans = 0;dfs(root);return ans;
}
t6二叉树的层级遍历，逐层，从左向右访问
解法：正常的BFS，不过每次使用一个n来确定当前层拥有的对象数量，遍历一次之后获得一个res用来存入最终答案，再确定下一个n用来遍历
vector<vector<int>> levelOrder(TreeNode* root) {deque<TreeNode*> clist;vector<vector<int>>ans;if(root)clist.push_back(root);while(!clist.empty()){int n = clist.size();//!!!重要部分vector<int> res;for(int i = 0;i<n;i++){//!!!重要部分TreeNode* p = clist.front();clist.pop_front();res.push_back(p->val);if(p->left)clist.push_back(p->left);if(p->right)clist.push_back(p->right);}ans.push_back(res);}return ans;
t7将有序数组转化为二叉搜索树
一半给左子树一半给右子树
使用递归即可，中间值作为根节点，中间值左边做左子树，同理得到右子树
TreeNode* sortedArrayToBST(vector<int>& nums) {return buildTree(nums, 0, nums.size() - 1);
}TreeNode* buildTree(vector<int>& nums, int left, int right) {if (left > right) return nullptr;int mid = left + (right - left) / 2;TreeNode* root = new TreeNode(nums[mid]);root->left = buildTree(nums, left, mid - 1);root->right = buildTree(nums, mid + 1, right);return root;
}
t8验证二叉搜索树
不是我喜欢的题，直接递归，难点在于右子树的所有节点都大于，左子树的所有节点都小于
！中序遍历升序即可！使用递归进行中序遍历的比较
long long pre = LLONG_MIN;
bool isValidBST(TreeNode* root) {if(root==nullptr)return true;if(!isValidBST(root->left))return false;//左if(root->val<=pre)return false;//中pre = root->val;return isValidBST(root->right);//右
}
t9二叉搜索树中第k小的元素
中序遍历然后找第k个（神人）
我的解法是用一个pre作为序号，遍历到序号为k是设置答案即可
int pre = 0;
int ans = INT_MAX;
int kthSmallest(TreeNode* root, int k) {checkans(root,k);return ans;
}
void checkans(TreeNode*root,int k){if(!root)return;checkans(root->left,k);pre++;if(pre==k)ans=root->val;checkans(root->right,k);
}
t10二叉树的右视图
解法应该和层级遍历类似，只不过只返回最右侧内容
vector<int> rightSideView(TreeNode* root) {deque<TreeNode*> nq;vector<int>ans;if(root)nq.push_back(root);while(!nq.empty()){int n =nq.size();for(int i = 0;i<n;i++){TreeNode* p = nq.front();nq.pop_front();if(p->left)nq.push_back(p->left);if(p->right)nq.push_back(p->right);if(i==n-1)ans.push_back(p->val);}}return ans;
}
t11二叉树展开为链表
结果要和先序遍历相同，即根左右
一直循环，方法是将根节点的左子树根，接到根节点右孩子的位置上，再将右子树根接到原左子树最右下的节点的右子树上，接下来再使用同样的方法处理根节点的右孩子，直到根节点为空，就可以完成展开了，但是这个方法需要创建指针用来查找节点，所以空间复杂度不为o1
void flatten(TreeNode* root) {while(root){if(!root->left)root=root->right;else{TreeNode* pre=root->left;while(pre->right){pre=pre->right;}pre->right=root->right;root->right=root->left;root->left=nullptr;root=root->right;}}
}
空间复杂度为1，需要使用递归后序遍历（右、左、中），然后维护一个pre，函数循环遍历当前节点时，pre就指向左节点了，且右子树也已经访问过，其根节点已经被左子树的最右节点指向了,这样就用非常简洁且空间复杂度低的方法解决了问题
虽然这道题需要使用的是先序遍历解题，后序遍历实际上是先序遍历倒过来，使用pre记录节点就可以使最终结果成为先序遍历
TreeNode* pre;
void flatten(TreeNode* root) {if(root==nullptr)return;flatten(root->right);flatten(root->left);root->right=pre;root->left=nullptr;pre=root;
}
t12从前序和中序遍历序列构造二叉树
先序遍历是根左右，中序遍历是左根右
这里需要用到递归和循环（确定根节点在中序序列中位置），将左子树的序列提出来构造树，再将右子树的序列提出来构造树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {TreeNode* root=bt(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1);return root;
}
TreeNode* bt(vector<int>& preorder, vector<int>& inorder,int pl,int pr,int il,int ir){if(pl>pr)return nullptr;TreeNode* root=new TreeNode(preorder[pl]);int i = il;while(inorder[i]!=preorder[pl])i++;root->left=bt(preorder,inorder,pl+1,pl+i-il,il,i-1);root->right=bt(preorder,inorder,pl+i-il+1,pr,i+1,ir);return root;
}
t13路径总和III
看评论有一个暴力法符合我的思路，将每个节点作为根进行查找，再递归其子节点，将所有结果相加
int pathSum(TreeNode* root, int targetSum) {if(!root)return 0;return dfs(root,targetSum)+pathSum(root->left,targetSum)+pathSum(root->right,targetSum);
}
int dfs(TreeNode* root,long long target){if(!root)return 0;int cnt = 0;if(root->val==target)cnt++;cnt+=dfs(root->left,target-root->val);cnt+=dfs(root->right,target-root->val);return cnt;
}
t14二叉树的最近公共祖先
通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p,q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root 。
所以首先递归的出口是当前节点是p或者q，或者当前节点是null，三种情况都直接返回root即可
再递归left节点和right节点，获取返回值，分为四种情况
如果left和right都有值，说明当前节点是其公共祖先，返回当前节点
如果left或right有值，说明left或right返回的值是公共祖先，返回公共祖先
如果都没值，说明当前子树没有pq节点，返回NULL
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q||!root)return root;TreeNode* l = lowestCommonAncestor(root->left,p,q);TreeNode* r = lowestCommonAncestor(root->right,p,q);if(l&&r)return root;else if(l)return l;else if(r)return r;else return NULL;
}
t15二叉树中的最大路径和
使用全局变量保存最大路径和，每个节点作为路径根节点，左右子树dfs，每个节点都更新一次最大路径和
过于复杂，时间复杂度和空间复杂度都超标
最优解还是采取dfs，优先递归左右子树得到含子树根的路径最大和，每次递归都更新总的最大和，并返回左右子树最大和中更大的一方和根相加的值
int maxs = INT_MIN;
int maxPathSum(TreeNode* root) {dfs(root);return maxs;
}
int dfs(TreeNode* root){if(!root)return 0;int lval=dfs(root->left);int rval=dfs(root->right);maxs=max(maxs,lval+rval+root->val);return max(max(lval,rval)+root->val,0);
}
9图论
t1岛屿数量
解法是使用一个燃烧递归函数，将相连的岛屿地块全部燃烧掉，主函数内遍历所有地块，如果有岛屿地块则cnt加一并启动燃烧函数消灭该岛屿
void check(vector<vector<char>>&grid,int i,int j){if(i<0||i>grid.size()-1||j<0||j>grid[0].size()-1||grid[i][j]!='1')return;grid[i][j]='2';check(grid,i-1,j);check(grid,i,j-1);check(grid,i+1,j);check(grid,i,j+1);
}
int numIslands(vector<vector<char>>& grid) {int cnt = 0;for(int i = 0;i<grid.size();i++){for(int j =0;j<grid[0].size();j++){if(grid[i][j]=='1'){check(grid,i,j);cnt++;} }}return cnt;
}
t2腐烂的橘子
感觉类似于燃烧地块，但是有时间记录的要求
暴力解法个人思路是遍历整个网格t遍，每次让腐烂橘子进行感染，当遍历完还有新鲜橘子时，再次遍历，直到遍历完一个新鲜橘子都没有为止，但是限制条件非常多
这里使用广度优先遍历，也就是层级遍历，初始化时，找出所有腐烂的橘子作为第0层，进行BFS遍历，同时记录所有新鲜的橘子，当BFS结束后如果仍存在新鲜橘子，说明存在无法污染的橘子，返回-1.