力扣热题100再刷

160.相交链表

读一遍A，一个set存节点，遍历B的时候判断即可。复习下set的STL：set有set和unordered_set，同样有insert，find，count，对于set而言，自动从小到大排序，还有：

s.lower_bound(k)	O ( l o g N )	返回大于等于k的第一个元素的迭代器
s.upper_bound(k)	O ( l o g N )	返回大于k的第一个元素的迭代器

注意都是大于！（或大于等于）

234.回文链表

无

226.翻转二叉树

翻转二叉树是经典题了，必须掌握。就是递归遍历树，然后从下往上交换左右子树。（实际上很多和树相关的都会涉及递归和遍历）

class Solution {
public:void switchlr(TreeNode* root){if(root==nullptr)return;switchlr(root->left);switchlr(root->right);TreeNode*l=root->left;root->left=root->right;root->right=l;return;}TreeNode* invertTree(TreeNode* root) {switchlr(root);return root;}
};

221.最大正方形

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。（再次提醒，返回的不是边长，而是边长的平方！）

同样是经典dp了，f(i,j)表示以(i,j)为右下角的正方形的最大边长，有了dp的思路然后画个图就知道dp方程

class Solution {
public:int maximalSquare(vector<vector<char>>& matrix) {int dp[310][310];memset(dp,0,sizeof dp);int ans=0;int m=matrix.size();int n=matrix[0].size();for(int i=0;i<m;i++){if(matrix[i][0]=='0')dp[i][0]=0;else{ans=1;dp[i][0]=1;}}for(int j=0;j<n;j++){if(matrix[0][j]=='0')dp[0][j]=0;else{ans=1;dp[0][j]=1;}}for(int i=1;i<m;i++){for(int j=1;j<n;j++){if(matrix[i][j]=='0'){dp[i][j]=0;continue;}else if(matrix[i][j]=='1'){dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1]))+1;ans=max(ans,dp[i][j]);}}}return ans*ans;}
};

215.数组中的第k个最大元素

线性查找模板——在快排的基础上改的partion

class Solution {
public:int partion(vector<int>&nums,int l,int r,int k){int bench=nums[l];int mid=(l+r)/2;int i=l,j=r;int z=nums.size();if(l==r)return nums[k];while(i<j){while(nums[j]>=bench&&j>i)j--;while(nums[i]<=bench&&i<j)i++;if(i<j)swap(nums[i],nums[j]);else if(i>=j)break;}nums[l]=nums[i];nums[i]=bench;if(i+1==k)return nums[i];else if(i+1<k)return partion(nums,i+1,r,k);else if(i+1>k)return partion(nums,l,i,k);return -1;}int findKthLargest(vector<int>& nums, int k) {int z=nums.size();if(z==1)return nums[0];return partion(nums,0,z-1,z-k+1);}
};

208.实现trie

记住字典树的结构：每个节点由一个字符vector和bool组成（标识是否是末尾）

class Trie {
private:vector<Trie*>ch;bool isend;
public:Trie() {ch=vector<Trie*>(26);isend=false;}void insert(string word) {int m=word.size();Trie* node=this;//注意注释中给出的调用for(int i=0;i<m;i++){char c=word[i]-'a';if(node->ch[c]==nullptr){node->ch[c]=new Trie();}node=node->ch[c];}node->isend=true;}bool search(string word) {int m=word.size();Trie* node=this;//注意注释中给出的调用for(int i=0;i<m;i++){char c=word[i]-'a';if(node->ch[c]==nullptr){return false;}node=node->ch[c];}return node->isend;}bool startsWith(string prefix) {int m=prefix.size();Trie* node=this;for(int i=0;i<m;i++){char c=prefix[i]-'a';if(node->ch[c]==nullptr)return false;node=node->ch[c];}return true;}
};
/*** Your Trie object will be instantiated and called as such:* Trie* obj = new Trie();* obj->insert(word);* bool param_2 = obj->search(word);* bool param_3 = obj->startsWith(prefix);*/

207.课程表

拓扑排序显然是和queue相关的，使用队列记录候选头，此外，正确做法应在减少邻接节点入度时立即检查其是否为0。

class Solution {
public:queue<int>que;unordered_map<int,vector<int>>store;bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int m=prerequisites.size();int a,b;vector<int>book(numCourses,0);vector<int>deg(numCourses,0);for(int i=0;i<m;i++){a=prerequisites[i][0];b=prerequisites[i][1];store[b].push_back(a);deg[a]+=1;}for(int i=0;i<deg.size();i++){if(deg[i]==0)que.push(i);}while(!que.empty()){int head=que.front();que.pop();book[head]=1;auto vec=store[head];for(int i=0;i<vec.size();i++){a=vec[i];deg[a]--;if(deg[a]==0&&book[a]==0)que.push(a);}}for(int i=0;i<book.size();i++){if(book[i]==0){return false;}}return true;}
};

236.二叉树的最近公共祖先

核心：从递归的思路出发，寻求找祖先的逻辑！

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == p || root == q)return root;TreeNode r = lowestCommonAncestor(root.right , p , q);TreeNode l = lowestCommonAncestor(root.left , p , q);return l == null ? r : (r == null ? l : root);}
}

206.反转链表

强调一些语法：for (auto it = store.rbegin(); it != store.rend(); ++it)，rend() 表示反向迭代器的结束位置（指向容器第一个元素的前一个位置），it确实是++，只不过从末尾往开头走，it代表迭代器！使用&it代表获取迭代器的地址（x），而*it代表获取迭代器代表的元素（√）

739.每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

显然是从后往前遍历，维护一个day数组，day[a]=b;比a温度高的是第b天这样如果前面天的温度更高，j=day[j]; 直接跳到比j温度高的天比较，然后继续跳……

class Solution {
public:vector<int> dailyTemperatures(vector<int>& temperatures) {int k=temperatures.size();vector<int>day(k,-1);//day[a]=b;比a温度高的是第b天for(int i=k-1;i>0;i--){int j=i;while(j!=-1){if(temperatures[i-1]<temperatures[j]){day[i-1]=j;break;}else{j=day[j];}}}vector<int>ans;for(int i=0;i<k;i++){if(day[i]==-1)ans.push_back(0);else{ans.push_back(day[i]-i);}}return ans;}
};

200.岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

dfs，染色和岛屿数量由color决定。

class Solution {
public:int board[310][310];int color;int dire[4][2]={{1,0},{0,-1},{-1,0},{0,1}};void paint(const vector<vector<char>>&grid,int x,int y){int m=grid.size();int n=grid[0].size();int tx,ty;board[x][y]=color;for(int i=0;i<4;i++){tx=x+dire[i][0];ty=y+dire[i][1];if(tx<0||tx>=m||ty<0||ty>=n||grid[tx][ty]=='0'||board[tx][ty]!=0)continue;paint(grid,tx,ty);}}int numIslands(vector<vector<char>>& grid) {memset(board,0,sizeof board);color=0;int m=grid.size();int n=grid[0].size();for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(board[i][j]==0&&grid[i][j]=='1'){color+=1;paint(grid,i,j);}}}return color;}
};

198.打家劫舍

老dp了，关于i-1和i-2的，拿与不拿（注意下只有一家的特殊情况）。

class Solution {
public:int rob(vector<int>& nums) {int k=nums.size();vector<int>dp(k,0);if(k==1)return nums[0];dp[0]=nums[0];dp[1]=max(nums[0],nums[1]);for(int i=2;i<k;i++)dp[i]=max(dp[i-2]+nums[i],dp[i-1]);return dp[k-1];}
};

169.多数元素

略

238.除自身以外数组的乘积

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

看到O（n）就应该想到双指针，两个数组，一个存前缀乘积一个存后缀乘积

注意一个小点：vector已经声明了空间长度，就不要再用push_back！

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int m=nums.size();vector<int>pre(m,1);vector<int>behind(m,1);for(int i=1;i<m;i++){pre[i]=(pre[i-1]*nums[i-1]);}for(int i=m-2;i>=0;i--){behind[i]=(behind[i+1]*nums[i+1]);}vector<int>ans(m);for(int i=0;i<m;i++)ans[i]=(pre[i]*behind[i]);return ans;}
};

155.最小栈

要强调一个点：这里不等同于单调栈！（如果是单调栈，请问获取栈顶的元素和获取最小元素有什么区别）

方法很简单——同时维护一个栈，记录此时此刻在栈中的最小值就行。（与元素栈同步插入与删除，用于存储与每个元素对应的最小值。）

class MinStack {
private:stack<int>store,work;
public:MinStack() {work.push(INT_MAX);}void push(int val) {store.push(val);work.push(min(work.top(),val));}void pop() {store.pop();work.pop();}int top() {return store.top();}int getMin() {return work.top();}
};

152.乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

看题目就想到求连续最大值的一遍扫描，只不过这里是乘法，需要考虑负负得正的情况，办法很简单，引入两个变量代表当前乘积最大和最小值，然后同时与nums[i]相乘并比较就好！

框架肯定不变的，就看怎么解决乘积，所以想到引入变量

int maxProduct(vector<int>& nums) {int neg = nums[0], pos = nums[0], ans = nums[0]; for (int i = 1; i < nums.size(); i++) {int pre_neg = neg; int pre_pos = pos;neg = min({nums[i], nums[i] * pre_neg, nums[i] * pre_pos});pos = max({nums[i], nums[i] * pre_neg, nums[i] * pre_pos});ans = max(ans, pos);}return ans;
}

比较易错的是这样：

for(int i=1;i<k;i++){neg=trimin(nums[i],nums[i]*neg,nums[i]*pos);pos=trimax(nums[i],nums[i]*neg,nums[i]*pos);ans=max(ans,pos);}

这样肯定不对，neg被更新后立即用于计算新的 pos，而不是上一轮的原始值

148.排序链表

略。

其实严格意义上，这里不应该图省事用快排sort，标准想考查的事链表的归并排序。

sort(store.begin(), store.end(), Comparator());// 使用结构体比较而非 Lambda

成员函数后的 const 保证函数不修改结构体状态

两个括号：

operator() 实现函数调用语义 bool operator()(...)

private:// 定义比较结构体struct Comparator {bool operator()(const ListNode* a, const ListNode* b) const {return a->val < b->val;}};

补充：常数空间内找到链表中点——快慢指针法！！！

141.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

略。链表中的经典套路——快慢指针

142.环形链表2

加一个返回入环的结点（如果有环的话）。略。遍历的同时维护一个unordered_set

146.LRU缓存

究极面试经典题。关键在于put这个点要是常数复杂度，所以用栈是不行的，堆也是不行的（设计到删除插入），只能考虑双向链表，头部最新，尾部最老（单向的话删除需要遍历找pre，也不行）；缓存使用一个map。

还有就是插删的细节问题，以及初始化操作。

class LRUCache {
struct linknode{int key,value;linknode*next,*pre;linknode():key(0),value(0),next(nullptr),pre(nullptr){}linknode(int key,int val):key(key),value(val),next(nullptr),pre(nullptr){}
};
private:unordered_map<int,linknode*>umap;linknode* head;linknode* tail;int maxcap,cap;
public:void removenode(linknode* p){linknode* p1=p->pre;linknode* p2=p->next;p1->next=p2;p2->pre=p1;return;}void addtohead(linknode* p){p->pre=head;p->next=head->next;head->next->pre=p;head->next=p;return;}LRUCache(int capacity) {head=new linknode();tail=new linknode();head->next=tail;tail->pre=head;this->maxcap=capacity;cap=0;return;}int get(int key) {if(umap.find(key)==umap.end())return -1;linknode* p=umap[key];removenode(p);addtohead(p);return p->value;}void put(int key, int value) {if(umap.find(key)!=umap.end()){linknode* p=umap[key];removenode(p);p->value=value;addtohead(p);}else{linknode* p=new linknode(key,value);addtohead(p);umap[key]=p;cap++;if(cap>maxcap){linknode* p=tail->pre;removenode(p);umap.erase(p->key);delete p;cap--;}}}
};

139.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

直接开搜，但注意搜索可能会导致超时，所以采取一些策略：首先是引入memo这个map，用于缓存已经计算过的子问题的结果，以避免重复计算；第二个是全部改为引用调用，这样有的递归调用都共享同一个，如果不这样，则每个递归分支都有自己的独立副本（即memo是每个分支独立的），也就失去了memo的意义。

此外，强烈建议再看STL中各种string的函数，很有用！

class Solution {
public:bool search(string s,const vector<string>&wordDict,unordered_map<string,bool>&memo){if(s=="")return true;if(memo.find(s)!=memo.end())return memo[s];for(auto word:wordDict){if(s.size()>=word.size()&&s.substr(0,word.size())==word){if(search(s.substr(word.size()),wordDict,memo)){memo[s]=true;return true;}}}memo[s]=false;return false;}bool wordBreak(string s, vector<string>& wordDict) {unordered_map<string,bool>memo;return search(s,wordDict,memo);}
};

136.只出现一次的数字

给你一个非空整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

找元素，且只用常量空间——往位运算上面想！ 异或^=

647.回文子串

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。

注意一个点：回文的判断用双指针。

class Solution {
public:int isregu(const string &s,int sta,int len){int i=sta;int j=sta+len-1;while(i<=j){if(s[i]==s[j]){j--;i++;continue;}else return 0;}return 1;}int countSubstrings(string s) {int ans=0;int k=s.size();for(int i=1;i<=k;i++){for(int j=0;j+i-1<k;j++){ans+=isregu(s,j,i);}}return ans;}
};

128.最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。要求是O(n)的复杂度

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

从基础版的代码开始一步步想解决办法：x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案。所以将基础暴力n^2降到n的做法是确定这个数是不是开头，如果是才遍历，如果不是就跳过，即判断set中有没有num-1！ ——这种从基础到最终的解决思想是值得学习的

class Solution {
public:int longestConsecutive(vector<int>& nums) {//遍历开头的做法unordered_set<int>store;for(int num:nums)store.insert(num);int ans=0;for(int num:store){if(!store.count(num-1)){int cur=num;int curlen=1;while(store.count(cur+1)){cur++;curlen++;}ans=max(ans,curlen);}}return ans;}
};

124.二叉树中的最大路径和

二叉树中的路径被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

显然是递归：显然每次返回的应该是单边的最大值（而不是折线，意会一下），但是，这个可能是折线的最大路径和完全可以在递归的过程中更新呀~ 具体看代码，还是很经典的

class Solution {
public:int ans;int dfs(TreeNode* root){if(root==nullptr){return 0;}int maxleft=max(dfs(root->left),0);int maxright=max(dfs(root->right),0);//更新最大路径和ans=max(ans,maxleft+maxright+root->val);//返回的值又是另一回事：//他的贡献只能带其中一个孩子（带大孩子走），整个路径才能向上延伸return root->val+max(maxleft,maxright);}int maxPathSum(TreeNode* root) {ans=INT_MIN;dfs(root);return ans;}
};

322.零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。（每种硬币数量无限)

这里使用闫式dp法

class Solution {
public:int coinChange(vector<int>& coins, int amount) {if(amount==0)return 0;vector<int>dp(amount+1,amount+1);dp[0]=0;for(int i=1;i<=amount;i++){for(auto coin:coins){if(coin>i)continue;dp[i]=min(dp[i],dp[i-coin]+1);}}return dp[amount]>amount?-1:dp[amount];}
};

试了一下dfs+剪枝似乎也能过：不过这种求最值的问题还是优先dp！（必须想到）

复杂度amount*len(nums)，这里的剪枝搜索也是模板！此外，倒排序：用rbegin

class Solution {
private:vector<int>store;
public:int dfs(const vector<int>&coins,int amount){if(amount==0)return 0;if(store[amount]!=-2)return store[amount];int min_count=0x3f3f3f;for(int coin:coins){if(coin>amount)continue;int res=dfs(coins,amount-coin);if(res!=0x3f3f3f){min_count=min(min_count,res+1);}}store[amount]=min_count;return store[amount];}int coinChange(vector<int>& coins, int amount) {sort(coins.rbegin(),coins.rend());store=vector<int>(amount+1,-2);int result=dfs(coins,amount);return result==0x3f3f3f?-1:result;}
};

494.目标和

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

超级经典的动态规划！

所以转化为背包问题，选哪些组合可以把package_b装满（使用b来判断，b为负有0种情况）

461.汉明距离

注意左移运算符：>>= 此外，左移是高位补0

class Solution {
public:int hammingDistance(int x, int y) {int ans=0;//x和y任意一个不为零都循环while(x|y){ans+=(x&1)^(y&1);x>>=1;y>>=1;}return ans;}
};

448.找到所有数组中消失的数字

略

438.找到字符串中的所有异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

令人惊讶的是不考虑任何优化，直接每次考虑两个map是否相等也能过。

class Solution {
public:unordered_map<char,int>pstore,sstore;int thesame(){for(auto it=pstore.begin();it!=pstore.end();it++){char ch=it->first;if(sstore.find(ch)==sstore.end()||sstore[ch]!=pstore[ch])return 0;}return 1;}vector<int> findAnagrams(string s, string p) {int k1=s.size();int k2=p.size();for(int i=0;i<k2;i++){pstore[p[i]]+=1;}vector<int>ans;if(k1<k2)return ans;for(int i=0;i<k2;i++){sstore[s[i]]+=1;}for(int i=1;i+k2<=k1;i++){if(thesame())ans.push_back(i-1);sstore[s[i-1]]-=1;sstore[s[i+k2-1]]+=1;}if(thesame())ans.push_back(k1-k2);return ans;}
};

显然是只用比较移入和移出之后的变化的，所以可以有更快的做法：

避免在每次滑动窗口时完整比较两个哈希表，我们可以改用固定大小的数组（大小128，覆盖所有ASCII字符），并利用数组直接比较是否相等。

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;if (p.empty()) {for (int i = 0; i <= s.size(); i++) ans.push_back(i);return ans;}if (s.size() < p.size()) return ans;vector<int> p_count(128, 0);vector<int> s_count(128, 0);int pLen = p.size();for (char c : p) p_count[c]++;for (int i = 0; i < pLen; i++) s_count[s[i]]++;if (p_count == s_count) ans.push_back(0);for (int i = pLen; i < s.size(); i++) {s_count[s[i - pLen]]--;s_count[s[i]]++;if (p_count == s_count) ans.push_back(i - pLen + 1);}return ans;}
};

437.路径综合3

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

深度搜索的同时引入一个前缀和哈希进行判断！

class Solution {
public:unordered_map<long, int> prefixSumCount; // 存储前缀和出现次数的哈希表int totalCount; // 记录满足条件的路径总数void dfs(TreeNode* node, long currentSum, int targetSum) {if (!node) return;// 更新当前路径和currentSum += node->val;// 检查是否存在前缀和使得 currentSum - prefixSum = targetSumif (prefixSumCount.find(currentSum - targetSum) != prefixSumCount.end()) {totalCount += prefixSumCount[currentSum - targetSum];}// 更新当前前缀和的出现次数prefixSumCount[currentSum]++;// 递归遍历左右子树dfs(node->left, currentSum, targetSum);dfs(node->right, currentSum, targetSum);// 回溯：当前节点访问完成后，从哈希表中去除当前前缀和prefixSumCount[currentSum]--;if (prefixSumCount[currentSum] == 0) {prefixSumCount.erase(currentSum);}}int pathSum(TreeNode* root, int targetSum) {prefixSumCount.clear();prefixSumCount[0] = 1; // 重要：初始化空路径的前缀和为0的出现次数为1totalCount = 0;dfs(root, 0, targetSum);return totalCount;}
};

416.分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

略。经典拆成0-1背包。

406.根据身高重建队列

其实是个不错的锻炼思维的题，题目有点绕，核心是输入的数组是乱序的，让你给排序。

解法为将输入按照身高升序排序，然后遍历，这样每次遍历的时候必然是当前最小的身高。

class Solution {
public:// struct ope{//     bool operator()(const vector<int>&a,const vector<int>&b){//         if(a[0]<b[0])return true;//         else if(a[0]==b[0]&&a[1]<b[1])return true;//     }// };vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {unordered_map<int,vector<int>>store;int k=people.size();int height[k+5];memset(height,-1,sizeof height);sort(people.begin(),people.end());for(int i=0;i<k;i++){int h=people[i][0];int pos=people[i][1];int count=0;for(int j=0;j<k;j++){if(pos==count){while(j<k&&height[j]!=-1)j++;height[j]=h;store[j]=people[i];break;}if(height[j]==-1&&count<pos){count++;}else if(height[j]>=h&&count<pos){count++;}else if(height[j]!=-1&&height[j]<h)continue;}}vector<vector<int>>ans;for(int i=0;i<k;i++){ans.push_back(store[i]);}return ans;}
};

399.除法求值

除法问题，首先的思路是找基准，比如a/b以b为基准……但显然这个基准不好找，所以想到的是并查集，通过并查集能将相关联的字符归为一个基准！即：根节点（祖先）为基准，且这是个带权的并查集（它的压缩与合并必须掌握）

不同的字符串（这个题好像不约分，即ab/bc就是ab/bc，而并不等于a/c）用哈希表存储，将字符串映射为int，这样就和并查集结合了。

class Solution {
private:class Union{//建立并查集private:vector<int>parents;//weights[x] 表示变量 x 相对于其当前直接父节点的权重值//如果父节点为p，那么x=p×weights[x]vector<double>weights;public:Union(int n):parents(n),weights(n,1.0){for(int i=0;i<n;i++)parents[i]=i;//并查集初始化}int findfa(int x){if(parents[x]==x)return parents[x];else{//注意这里！带权并查集的压缩的写法！int ori=parents[x];parents[x]=findfa(parents[x]);weights[x]*=weights[ori];}return parents[x];}//合并，将x所在的子树连到y所在的子树void unite(int x,int y,double value){int rootx=findfa(x);int rooty=findfa(y);if(rootx==rooty)return;parents[rootx]=rooty;//x把y当做基weights[rootx]=weights[y]*value/weights[x];}double isconnected(int x,int y){int rootx=findfa(x);int rooty=findfa(y);if(rootx==rooty)return weights[x]/weights[y];else return -1.0;}};
public:vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {int k=equations.size();//注意初始化的表达Union theunion(2*k);//变量到id的映射unordered_map<string,int>hashmap(2*k);int id=0;for(int i=0;i<k;i++){string var1=equations[i][0];string var2=equations[i][1];if(!hashmap.count(var1))hashmap[var1]=id++;if(!hashmap.count(var2))hashmap[var2]=id++;//建立两个字符串的连接，字符串用id映射表示theunion.unite(hashmap[var1],hashmap[var2],values[i]);}int q=queries.size();vector<double>res(q);for(int i=0;i<q;i++){string var1=queries[i][0];string var2=queries[i][1];//新出现的变量if(!hashmap.count(var1)||!hashmap.count(var2))res[i]=-1.0;//计算else res[i]=theunion.isconnected(hashmap[var1],hashmap[var2]);}return res;}
};

394.字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

很不错的一道递归题，对于一个字符串，它可能很多地方都会有压缩（即[]），压缩处的标志即数字（这里要注意数字可能有多位），所以当在数字标记处时，求得当前压缩的次数，while结束后进入压缩（跳过[，进入下一轮递归，出来的时候res加上压缩串），其他情况则为没有压缩的字符，正常加即可。

class Solution {
public:string decodeString(string s) {int i = 0;return decodeSub(s, i);}private:string decodeSub(const string& s, int& i) {string res;while (i < s.size() && s[i] != ']') {if (isdigit(s[i])) {int num = 0;while (i < s.size() && isdigit(s[i])) {num = num * 10 + (s[i] - '0');i++;}if (i < s.size() && s[i] == '[') {i++; // 跳过左括号string t = decodeSub(s, i);for (int j = 0; j < num; j++) {res += t;}}} else {res += s[i];i++;}}if (i < s.size() && s[i] == ']') {i++;}return res;}
};

347.前k个高额元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

其实正确做法应该是用堆排序和优先队列（这种看题就应该想到）

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int>store;int u=nums.size();for(int i=0;i<u;i++){store[nums[i]]+=1;}map<int,vector<int>>temp;for(auto it=store.begin();it!=store.end();it++){int a=it->second;int b=it->first;temp[a].push_back(b);}vector<int>ans;for(auto it=temp.rbegin();it!=temp.rend();it++){auto vec=it->second;if(k>0){for(int j=0;j<vec.size();j++){ans.push_back(vec[j]);k--;}}else break;}return ans;}
};

338.比特位计数

略。（此为第37题）

337.打家劫舍3

经典的树形dp了！可以看之前acwing的记录：

这类问题都有一个共同点，或者说同时都属于dp问题的状态机类问题，所谓状态机：

当问题的状态转移涉及多个条件或选择时，直接定义状态转移方程可能变得复杂。状态机通过显式地划分状态和转移条件，使动态规划的逻辑更清晰，避免遗漏可能性。（多个dp空间，这里用map存储+树的遍历）

class Solution {
public:unordered_map<TreeNode*,vector<int>>store;void search(TreeNode* root){if(root==nullptr)return;else if(root->left==nullptr&&root->right==nullptr){store[root].push_back(0);store[root].push_back(root->val);return;}else if(root->left==nullptr&&root->right!=nullptr){search(root->left);search(root->right);vector<int>t(2,0);t[0]=max(store[root->right][0],store[root->right][1]);t[1]=store[root->right][0]+root->val;store[root]=t;}else if(root->left!=nullptr&&root->right==nullptr){search(root->left);search(root->right);vector<int>t(2,0);t[0]=max(store[root->left][0],store[root->left][1]);t[1]=store[root->left][0]+root->val;store[root]=t;}else{search(root->left);search(root->right);vector<int>t(2,0);t[0]=max(store[root->left][0],store[root->left][1])+max(store[root->right][0],store[root->right][1]);t[1]=store[root->left][0]+store[root->right][0]+root->val;store[root]=t;}return;}int rob(TreeNode* root) {search(root);return max(store[root][0],store[root][1]);}
};

121.买卖股票的最佳时期

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

简单题，不难，关键是想清楚思路：不断更新截止到第i天的股票最低点。

class Solution {
public:int maxProfit(vector<int>& prices) {int k=prices.size();int sta=0;int ans=0;for(int i=0;i<k;i++){if(prices[sta]>=prices[i]){sta=i;continue;}else if(prices[sta]<prices[i]){ans=max(ans,prices[i]-prices[sta]);}}return ans;}
};

312.戳气球

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

动态规划解决的问题，需要满足三个条件：最优子结构，无后效性和子问题重叠。

第一次戳哪个气球不满足无后效性

那么就试试最后一次戳哪个气球——这是核心！戳最后一个气球！

因为是最后一个被戳爆的，所以它周边没有球了！没有球了！只有这个开区间首尾的 i 和 j 了！！
这就是为什么DP的状态转移方程是只和 i 和 j 位置的数字有关

class Solution {
public:int maxCoins(vector<int>& nums) {int n = nums.size();vector<vector<int>> rec(n + 2, vector<int>(n + 2));vector<int> val(n + 2);val[0] = val[n + 1] = 1;for (int i = 1; i <= n; i++) {val[i] = nums[i - 1];}for (int i = n - 1; i >= 0; i--) {for (int j = i + 2; j <= n + 1; j++) {for (int k = i + 1; k < j; k++) {int sum = val[i] * val[k] * val[j];sum += rec[i][k] + rec[k][j];rec[i][j] = max(rec[i][j], sum);}}}return rec[0][n + 1];}
};

309.买卖股票的最佳时期含冷冻时期

dp神题了——分析状态——多个状态，那么和前面打家劫舍一样多维的dp就行

// f[i][0]: 手上持有股票的最大收益

// f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益

// f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益

class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size()==0)return 0;int k=prices.size();vector<vector<int>>dp(k,vector<int>(3));dp[0][0]=-1*prices[0];for(int i=1;i<k;i++){//持有股票，要么是i-1才买的，要么是之前买的dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);//不持有股票且冷冻，只能是前一天卖了dp[i][1]=dp[i-1][0]+prices[i];//不持有股票不冷冻，可能是前面卖了dp[i][2]=max(dp[i-1][1],dp[i-1][2]);}return max(dp[k-1][1],dp[k-1][2]);}
};

301.删除无效的括号

给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。

返回所有可能的结果。答案可以按 任意顺序 返回。

valid函数判断s有不有效（即左右括号是否相同），要求返回删最小数量括号后的有效集合，显然是宽度优先搜索！——对于每个括号，都给他删了看是不是有效的。

不错的题，想想思路。

class Solution {
public:bool isValid(string s) {int count = 0;for (char c : s) {if (c == '(') {count++;} else if (c == ')') {count--;if (count < 0) return false;}}return count == 0;}vector<string> removeInvalidParentheses(string s) {vector<string> res;queue<string> q;unordered_set<string> visited;q.push(s);visited.insert(s);bool found = false;while (!q.empty()) {int size = q.size();unordered_set<string> nextLevelSet;for (int i = 0; i < size; i++) {string cur = q.front(); q.pop();if (isValid(cur)) {res.push_back(cur);found = true;}if (found) continue;for (int j = 0; j < cur.size(); j++) {if (cur[j] != '(' && cur[j] != ')') continue;string nextStr = cur.substr(0, j) + cur.substr(j + 1);if (visited.find(nextStr) == visited.end()) {nextLevelSet.insert(nextStr);visited.insert(nextStr);}}}if (found) break;for (auto& str : nextLevelSet) {q.push(str);}}return res;}
};

300.最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

最经典的一道dp题！dp[i][j]表示以i为始（i必选），到j的递增子序列的最长长度，（至少得确定选一个才有dp的必要），所以有：

class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = (int)nums.size();if (n == 0) {return 0;}vector<int> dp(n, 0);for (int i = 0; i < n; ++i) {dp[i] = 1;for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) {dp[i] = max(dp[i], dp[j] + 1);}}}return *max_element(dp.begin(), dp.end());}
};

但是显然，dp复杂度为n^2（题目n最大2500）

如何优化到nlogn？

需要记住一个点——dp的数组本身，其实是具有单调性的！

此题在acwing中亦有记载

287.寻找重复数

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，返回 这个重复的数 。

你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

Floyd判圈算法——快慢指针

class Solution {
public:int findDuplicate(vector<int>& nums) {int slow = 0, fast = 0;// 第一阶段：寻找相遇点do {slow = nums[slow];         // 慢指针走一步fast = nums[nums[fast]];   // 快指针走两步} while (slow != fast);        // 持续直到相遇// 第二阶段：找到环入口（重复数）int slow2 = 0;while (slow != slow2) {slow = nums[slow];slow2 = nums[slow2];}return slow; // 返回重复数}
};

283.移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

核心就是那个注意点，需要意识到，令一个变量po统计非零的个数，po的值肯定小于等于遍历时数组下标i（因为它只有数非0才++），这就意味着，我修改数组时，po的位置处已经被遍历了没有用了。

class Solution {
public:void moveZeroes(vector<int>& nums) {int po=0;int k=nums.size();for(int i=0;i<k;i++){if(nums[i]==0)continue;else{nums[po++]=nums[i];}}for(int i=po;i<k;i++)nums[i]=0;return;}
};

279.完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

从某种意义上讲，能用搜索搞的是不是都可以往dp想？

——dp的思想其实就是把一类子问题当成一个看待（或者说一个集合），这也是闫式dp的思想

——如果一个问题，可以由子问题组成，那么应该就可以用dp？

——所以先判断dp能不能用！即先看这个集合能不能被拆成更小的子集合！

——显然这里是可以的，即dp[i]=min(dp[i],dp[i-j]+dp[j]);

class Solution {
public:bool judge(int i){for(int z=0;z<=i;z++){if(z*z<i)continue;else if(z*z==i)return true;else if(z*z>i)break;}return false;}int numSquares(int n) {vector<int>dp(n+5,0);for(int i=0;i<=n;i++)dp[i]=i;dp[1]=1;dp[4]=1;for(int i=1;i<=n;i++){if(judge(i)){dp[i]=1;continue;}for(int j=1;j<i;j++){dp[i]=min(dp[i],dp[i-j]+dp[j]);}}for(int i=1;i<=n;i++)cout<<dp[i]<<" ";return dp[n];}
};

240.搜索二维矩阵2

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

核心就一个点——从右上角看，构成是一个排序的二叉树！（看到题想到这个就行）

class Solution {
public:bool ans;bool trace(int x,int y,vector<vector<int>>& matrix,int target){int m=matrix.size();int n=matrix[0].size();if(y==-1||x==m){return false;}if(matrix[x][y]==target){ans=true;return true;}else if(matrix[x][y]<target){return trace(x+1,y,matrix,target);}else if(matrix[x][y]>target){return trace(x,y-1,matrix,target);}return false;}bool searchMatrix(vector<vector<int>>& matrix, int target) {ans=false;trace(0,matrix[0].size()-1,matrix,target);return ans; }
};

22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

经典搜索框架了，搜索类题注意的就是边界条件！（一定小心）

class Solution {
public:vector<string>ans;void trace(int left,int right,int n,string&t){if(left>n||right>n)return;if(left==right&&left==n){ans.push_back(t);return;}if(left>right){t.push_back('(');trace(left+1,right,n,t);t.pop_back();t.push_back(')');;trace(left,right+1,n,t);t.pop_back();}else if(left==right){t.push_back('(');trace(left+1,right,n,t);t.pop_back();}else if(left<right)return;}vector<string> generateParenthesis(int n) {string temp="";trace(0,0,n,temp);return ans;}
};

49.字母异位词分组

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

异位词的核心是找一个基准！——比如找升序排列（string可以sort cba变为abc）

相同的异位词sort后相等，就可以用map存储。

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>>mmap;for(auto str:strs){string t=str;sort(t.begin(),t.end());mmap[t].push_back(str);}vector<vector<string>>ans;for(auto it=mmap.begin();it!=mmap.end();it++){ans.push_back(it->second);}return ans;}
};

48.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

核心：分层四元素交换！

遍历每边元素（除最后一个，避免重复）：

同时交换四个位置的元素（上→右→下→左→上）。

class Solution {
public:int n;void subrot(vector<vector<int>>& matrix, int z) {int len = n - 2 * z;  // 当前层边长for (int i = 0; i < len - 1; i++) {int temp = matrix[z][z + i];  // 保存上边// 左 → 上（左边从下往上取元素）matrix[z][z + i] = matrix[n - 1 - z - i][z];// 下 → 左（下边从右往左取元素）matrix[n - 1 - z - i][z] = matrix[n - 1 - z][n - 1 - z - i];// 右 → 下（右边从上往下取元素）matrix[n - 1 - z][n - 1 - z - i] = matrix[z + i][n - 1 - z];// 上 → 右（用保存的上边元素）matrix[z + i][n - 1 - z] = temp;}}void rotate(vector<vector<int>>& matrix) {n = matrix.size();// 逐层处理从外层（0）到内层（n/2 - 1）for (int i = 0; i < n / 2; i++) {subrot(matrix, i);}}
};

46.全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

同样是非常基础的搜索题，搜索题模板。明晰标记与回退

class Solution {
public:int book[15];vector<vector<int>>ans;vector<int>t;void trace(int step,vector<int>&nums){if(step==nums.size()){ans.push_back(t);return ;}for(int i=0;i<nums.size();i++){if(book[i])continue;else{book[i]=1;t.push_back(nums[i]);trace(step+1,nums);book[i]=0;t.pop_back();}}return;}vector<vector<int>> permute(vector<int>& nums) {trace(0,nums);return ans;}
};

42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

一种做法是一行一行来——显然是会超时的（时间复杂度m*n）

class Solution {
public:int trap(vector<int>& height) {int ans=0;int k=height.size()-1;int count=0;while(true){int l=-1;int r=k+1;for(int i=0;i<=k;i++){if(height[i]!=0){l=i;break;}}for(int i=k;i>=0;i--){if(height[i]!=0){r=i;break;}}if(l>=r||l==-1||r==k+1){return ans;}for(int i=l;i<=r;i++){if(height[i]==0)ans++;else if(height[i]>0)height[i]-=1;}}return ans;}
};

基本上，看到接雨水这类题，就得想到双指针！

维护两个指针 left 和 right，以及两个变量 left_max 和 right_max 分别记录左右遍历时的最大高度。
在每个位置，能接的雨水量取决于当前侧的最大高度与当前柱子高度之差。
从左边的视角看整个数组，看过去；再从右边的视角看！

class Solution {
public:int trap(vector<int>& height) {int n=height.size();if(n<=2)return 0;int l=0;int r=n-1;int ans=0;int l_max=0;int r_max=0;while(l<r){//先把满足左边部分的求了if(height[l]<height[r]){if(height[l]>=l_max)l_max=height[l];else{//height[l]<l_max，height[l]<height[r]//即在前面部分有左边挡板l_max，后面有右边挡板，此时可以接ans+=l_max-height[l];}l++;}//右边指针的高度更小或相等//一样的，求右边部分的影响else{if(height[r]>=r_max)r_max=height[r];else ans+=r_max-height[r];r--;}}return ans;}
};

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

这里不再是简单的搜索就行，还涉及到对结果的去重，套用前面的做法似乎不太现实：unordered_set 需要自定义哈希函数才能存储 vector<int>，没有的话会编译报错。

所以只能从根源入手——遍历时限制其实的位置，让它不要找以前的

（每次遍历时的i=start也保证了该元素的可重复性）

class Solution {
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> ans;vector<int> path;backtrack(0, target, candidates, path, ans);return ans;}void backtrack(int start, int target, vector<int>& candidates, vector<int>& path, vector<vector<int>>& ans) {if (target < 0) return;if (target == 0) {ans.push_back(path);return;}for (int i = start; i < candidates.size(); i++) {path.push_back(candidates[i]);backtrack(i, target - candidates[i], candidates, path, ans);path.pop_back();}}
};

543.二叉树的直径

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

涉及数的递归时刻记住递归的意义！——trace表示子树的深度

class Solution {
public:int ans;int trace(TreeNode* root){if(root==nullptr)return 0;int le=trace(root->left);int ri=trace(root->right);ans=max(ans,le+ri);cout<<ans<<" ";return max(le,ri)+1;}int diameterOfBinaryTree(TreeNode* root) {ans=0;trace(root);return ans;}
};

34.在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

也是经典题了！——核心是考查对二分搜索的理解

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.empty())return {-1,-1};int le=0;int ri=nums.size()-1;while(le<ri){int mid=le+(ri-le)/2;if(target>nums[mid]){le=mid+1;}else if(target<=nums[mid]){ri=mid;     }}if(target!=nums[le])le=-1;int a=le;le=0;ri=nums.size()-1;while(le<ri){int mid=le+(ri-le+1)/2;if(target>=nums[mid]){le=mid;}else if(target<nums[mid]){ri=mid-1;}}if(target!=nums[le])le=-1;int b=le;return {a,b};}
};

无非就是两次搜索，一次确定左边，一次确定右边。如何使二分搜索按照左边界和按照右边界搜？

左边界——对左边动，即le+1 右边界，对右边动，即ri-1；

运用迭代来实现二分然后注意确定边界通过while来，le>=ri时退出。

33.搜索旋转排序数组

整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题

本题的核心在于对顺序数组进行二分，所以要记住——与nums[0]进行判断，然后两次if判断都是针对每个部分的顺序数组做二分！

class Solution {
public:int search(vector<int>& nums, int target) {int k=nums.size();if(k==1){return nums[0]==target?0:-1;}int le=0;int ri=k-1;while(le<=ri){int mid=(le+ri)/2;if(nums[mid]==target)return mid;if(nums[mid]>=nums[0]){//高部分的顺序if(target<nums[mid]&&target>=nums[0]){ri=mid-1;}else le=mid+1;}else{//低部分的顺序if(target>nums[mid]&&target<=nums[k-1]){le=mid+1;}else ri=mid-1;}}return -1;}
};

31.下一个排列

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。

必须原地修改，只允许使用额外常数空间。

思路！

例如 2, 6, 3, 5, 4, 1 这个排列，我们想要找到下一个刚好比他大的排列，于是可以从后往前看
我们先看后两位 4, 1 能否组成更大的排列，答案是不可以，同理 5, 4, 1也不可以
直到3, 5, 4, 1这个排列，因为 3 < 5，我们可以通过重新排列这一段数字，来得到下一个排列
因为我们需要使得新的排列尽量小，所以我们从后往前找第一个比3更大的数字，发现是4
然后，我们调换3和4的位置，得到4, 5, 3, 1这个数列
因为我们需要使得新生成的数列尽量小，于是我们可以对5, 3, 1进行排序，可以发现在这个算法中，我们得到的末尾数字一定是倒序排列的，于是我们只需要把它反转即可
最终，我们得到了4, 1, 3, 5这个数列
完整的数列则是2, 6, 4, 1, 3, 5

class Solution {
public:void nextPermutation(vector<int>& nums) {int n = nums.size();int i = n - 2;// 从后向前找第一个升序的位置（即 nums[i] < nums[i+1]）while (i >= 0 && nums[i] >= nums[i + 1]) {i--;}if (i >= 0) {int j = n - 1;// 从后向前找第一个大于 nums[i] 的数while (j > i && nums[j] <= nums[i]) {j--;}swap(nums[i], nums[j]);}// 反转 i 之后的部分（无论 i 是否找到）reverse(nums.begin() + i + 1, nums.end());}
};

再次凝练核心思路三部分：

从右往左查找第一个升序位置：我们需要找到最右边的一个位置 i，使得 nums[i] < nums[i + 1]。这个位置 i 是可以增大的位置，因为其右侧的子数组已经是降序排列，无法再增大。
从右往左查找第一个更大元素：如果找到了这样的位置 i，我们需要从右往左找到第一个比 nums[i] 大的元素 nums[j]。
交换这两个元素：交换 nums[i] 和 nums[j]，这样可以确保当前排列尽可能小地增大。
反转右侧子数组：由于 i 右侧的子数组原本是降序排列的，交换后仍然保持降序，因此反转该子数组可以使其变为升序，从而得到最小的下一个排列。

538.把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

使用反中序遍历（右-根-左）并维护一个全局累加和！

class Solution {
public:void traverse(TreeNode* root, int& sum) {if (!root) return;traverse(root->right, sum);sum += root->val;        // 累加当前节点的原始值root->val = sum;         // 更新当前节点为累加和traverse(root->left, sum);}TreeNode* convertBST(TreeNode* root) {int sum = 0;traverse(root, sum);return root;}
};

53.最大子数组

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

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

经典错误代码：

class Solution {
public:int maxSubArray(vector<int>& nums) {int k=nums.size();int a=INT_MIN;int b=0;for(int i=0;i<k;i++){if(b>=0){b+=nums[i];a=max(a,b);cout<<b<<" ";}else if(b<0)b=0;}return a;}
};

在b<0时将b置为0就结束了，压根就没处理当前元素。

正确的实现——经典的Kadane算法！

class Solution {
public:int maxSubArray(vector<int>& nums) {int k = nums.size();int a = nums[0]; // 初始化为第一个元素（确保至少包含一个元素）int b = nums[0]; // 当前子数组和从第一个元素开始for (int i = 1; i < k; i++) {if (b > 0) {    // 相当于 b + nums[i] > nums[i]b += nums[i];} else {b = nums[i]; // 当前和小于等于0，重新开始}a = max(a, b);  // 更新全局最大和}return a;}
};

将更新放在最后统一更新，b小于0直接从当前开始。