力扣hot100分类整理及解题方法_hot100题单
hot100 题单
二叉树 16道
层序遍历，左孩子下标 i*2；右孩子下标 i*2+1 （下标从1开始
栈
二叉树的中序遍历 94 简单
左根右
一直向左一直进栈，取栈输出，再向右
class Solution {public: vector inorderTraversal(TreeNode* root) { vector res; stack sk; while (root || !sk.empty()) { while (root) { sk.push(root); root = root->left; } root = sk.top(); sk.pop(); res.push_back(root->val); root = root->right; } return res; }};BFS
二叉树的层序遍历 102
class Solution {public: vector<vector> levelOrder(TreeNode* root) { if(!root) return {}; vector<vector> res; queue que; que.push(root); while(!que.empty()){ int n=que.size(); //这层的大小 vector level;//这层的数据 for(int i=0;ival); //将下一层结点放入队列 if(node->left) que.push(node->left); if(node->right) que.push(node->right); } res.push_back(level); } return res; }};递归
1. 翻转二叉树 226 简单
class Solution {public: void dfs(TreeNode* t){ if(!t) return; dfs(t->left); dfs(t->right); TreeNode* l=t->left; TreeNode* r=t->right; t->left=r; t->right=l; } TreeNode* invertTree(TreeNode* root) { dfs(root); return root; }};2. 合并二叉树 617 简单
class Solution {public: TreeNode* dfs(TreeNode* t1,TreeNode* t2){ TreeNode* t=new TreeNode(); if(t1 && t2){ t->val=t1->val+t2->val; t->left=dfs(t1->left,t2->left); t->right=dfs(t1->right,t2->right); return t; }else if(t1){ return t1; }else if(t2){ return t2; }else{ return nullptr; } } TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { return dfs(root1,root2); }};3. 二叉树的最大深度 104 简单 略
略
4. 对称二叉树 101 简单
root是轴对称的：root的左子树和右子树是对称的
树 a 和树 b 是对称的：根相等 && a 的左子树和b右子树是对称的 && a的右子树和b的左子树是对称的
class Solution {public: bool dfs(TreeNode* l, TreeNode* r) { if (!l && !r) return true; if (!l && r || l && !r) return false; if (l->val != r->val) { return false; } return dfs(l->left, r->right) && dfs(l->right, r->left); } bool isSymmetric(TreeNode* root) { if (!root) return true; return dfs(root->left, root->right); }};5. 把二叉搜索树转换为累加树 538
右根左
全局变量sum
class Solution {public: int sum=0; void dfs(TreeNode* t){ if(!t){ return; } dfs(t->right); sum+=t->val; t->val=sum; dfs(t->left); } TreeNode* convertBST(TreeNode* root) { dfs(root); return root; }};6. 验证二叉搜索树 98 √
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
保证结点t的值在(low,up)之间
class Solution {public: bool dfs(TreeNode* t, long long low, long long up) { if (!t)return true; long long x = t->val; return x low && dfs(t->left, low, x)&&dfs(t->right, x, up); } bool isValidBST(TreeNode* root) { return dfs(root, LLONG_MIN, LLONG_MAX); }};7. 二叉树的最近公共祖先 236
先序遍历，目标：找到 p 和 q
class Solution {public: TreeNode* dfs(TreeNode* t, TreeNode* p, TreeNode* q) { if (!t || t == p || t == q) { return t; } TreeNode* l = dfs(t->left, p, q); TreeNode* r = dfs(t->right, p, q); if (l && r) { // p,q 在t左右两侧 return t; } if (l) { // p q都在左侧 return l; } if (r) { // 都在右侧 return r; } return nullptr; // 左右都没有 } TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { return dfs(root, p, q); }};8. 二叉树的直径 543 简单
一条路径的长度 = 该路径经过的节点数 - 1
而任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。
class Solution { int ans;//答案经过的结点数 int depth(TreeNode* t){ //求以t为根的树的深度（深度意思是最大深度） if (t == NULL) { return 0; // 访问到空节点了，返回0 } int L = depth(t->left); // 左儿子为根的子树的深度 int R = depth(t->right); // 右儿子为根的子树的深度 ans = max(ans, L + R + 1); // 经过t的结点数量为 左深度+右深度+t本身=L+R+1 return max(L, R) + 1; // 返回t为根的子树的深度 }public: int diameterOfBinaryTree(TreeNode* root) { ans = 0; depth(root); return ans - 1; }};9. 路径总和 III 437
根左右 前缀和
class Solution {public: unordered_map mp;//前缀和数组，mp[s]表示从根到某结点和为s的路径数量 //sum为从根节点到t的路径value和。需要作为参数传递，返回时sum回退。 int dfs(TreeNode* t,long long sum,int targetSum){ if(!t) return 0; int res=0; //t子树包含的答案数 sum+=t->val; if(mp.count(sum - targetSum)){//sum-mp=target，大前缀和-小前缀和 = 一段的和 res += mp[sum-targetSum]; } mp[sum]++; res+=dfs(t->left,sum,targetSum); res+=dfs(t->right,sum,targetSum); mp[sum]--;//需要回退 return res; } int pathSum(TreeNode* root, int targetSum) { mp[0]=1; //考虑根节点value=tagert的情况 return dfs(root,0,targetSum); }};10. 二叉树展开为链表 114
采用头插法构建链表，也就是从节点 6 开始，在 6 的前面插入 5，在 5 的前面插入 4，依此类推。
为此，要按照 6→5→4→3→2→1 的顺序访问节点，也就是按照右子树 - 左子树 - 根的顺序 DFS 这棵树。
DFS 的同时，记录当前链表的头节点为 head。一开始 head 是空节点。
class Solution {public: TreeNode* head=nullptr; void dfs(TreeNode* t){ if(!t) return; dfs(t->right); dfs(t->left); //头插法 t->right=head; t->left=nullptr; head=t; } void flatten(TreeNode* root) { dfs(root); }};11. 从前序与中序遍历序列构造二叉树 105
根左右
左根右
根据前序的根，去中序中定位根的位置，从而能确定左子树的范围。
map: 方便“去中序中定位根的位置”
int preorder_left, int preorder_right, int inorder_left, int inorder_right : 边界位置下标
class Solution {public: unordered_map mp; TreeNode* dfs(vector& preorder, vector& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right)return nullptr; int preorder_root = preorder_left; // 根节点在前序遍历中的位置下标 int inorder_root = mp[preorder[preorder_root]]; // 求出根节点在中序遍历中的位置下标 TreeNode* root = new TreeNode(preorder[preorder_root]); // 构建根节点 int size_left_subtree = inorder_root - inorder_left; // 左子树的节点数目 // 算出前序、中序的左、右子树的边界下标 root->left = dfs(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1); root->right = dfs(preorder, inorder, preorder_left + size_left_subtree + 1,preorder_right, inorder_root + 1, inorder_right); return root; } TreeNode* buildTree(vector& preorder, vector& inorder) { int n = preorder.size(); // 建立map for (int i = 0; i < n; i++) { mp[inorder[i]] = i; } return dfs(preorder, inorder, 0, n - 1, 0, n - 1); }};字典树
实现 Trie (前缀树) 208
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie()初始化前缀树对象。void insert(String word)向前缀树中插入字符串word。boolean search(String word)如果字符串word在前缀树中，返回true（即，在检索之前已经插入）；否则，返回false。boolean startsWith(String prefix)如果之前已经插入的字符串word的前缀之一为prefix，返回true；否则，返回false。
解：
class Trie {public: vector next; bool isEnd; Trie() { next=vector(26); isEnd=false; } void insert(string word) { Trie* node=this; // 谁调用谁就是node for(char c:word){ if(node->next[c-\'a\']==NULL){//新建一个“叉” node->next[c-\'a\']=new Trie(); } node=node->next[c-\'a\']; } node->isEnd=true; } bool search(string word) { Trie* node=this; for(char c:word){ if(node->next[c-\'a\']==NULL){ return false; } node=node->next[c-\'a\']; } if(node->isEnd){ return true; } return false; } bool startsWith(string prefix) { Trie* node=this; for(char c:prefix){ if(node->next[c-\'a\']==NULL){ return false; } node=node->next[c-\'a\']; } 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); */位运算 3道
1 汉明距离 461 简单
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4输出：2解释：1 (0 0 0 1)4 (0 1 0 0) ↑ ↑上面的箭头指出了对应二进制位不同的位置。异或^
%2：二进制的最后一位
/2 ：二进制右移一位
class Solution {public: int hammingDistance(int x, int y) { int ans=0; int z=x^y; while(z>0){ if(z%2==1){ ans++; } z=z/2; } return ans; }};2 比特位计数 338 动态规划
找规律 背诵
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
6 - ->110
奇数的个位一定是1，偶数是0
奇数：比前一个数多一个 个位的 1
偶数：比它除以2的数多一个0（因为/2相当于右移一位）
class Solution {public: vector countBits(int n) { vector ans; vector dp(n+1); //dp[i]表示数字i的1的个数 dp[0]=0; ans.push_back({0}); for(int i=1;i<=n;i++){ if(i%2==1){//奇数 dp[i]=dp[i-1]+1; } else{//偶数 dp[i]=dp[i/2]; } ans.push_back(dp[i]); } return ans; }};3 只出现一次的数字 136 简单
背诵
- 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。
- 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。
- 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。
出现两次的数⊕ 得0，0⊕出现一次的数，得到出现一次的数
class Solution {public: int singleNumber(vector& nums) { int res=0; for(int num:nums){ res=res^num; } return res; }};字符串 4道
1 字母异位词分组 49 √
map
class Solution {public: vector<vector> groupAnagrams(vector& strs) { vector<vector> ans; unordered_map<string,vector> mp; for(string str:strs){ string x=str; sort(x.begin(),x.end()); mp[x].push_back(str); } for(auto e:mp){ ans.push_back(e.second); } return ans; }};2 找到字符串中所有字母异位词 438 滑动窗口
滑动窗口大小=p.size()，在s中滑动
p中每个字符出现次数 == s的滑动窗口中 每个字符出现次数
class Solution {public: vector findAnagrams(string s, string p) { vector ans; vector count_s(26); vector count_p(26); int n=s.size(),m=p.size(); if(n<m) return ans; //计算p中每个字符出现次数。并初始滑动窗口 for(int i=0;i<m;i++){ count_p[p[i]-\'a\']++; count_s[s[i]-\'a\']++; } if(count_p==count_s){ ans.push_back(0); } //在s中进行窗口滑动 for(int i=0;i<n-m;i++){ count_s[s[i]-\'a\']--; //左侧滑走 count_s[s[i+m]-\'a\']++; //右侧滑入 if(count_s==count_p){ ans.push_back(i+1); } } return ans; }};3 无重复字符的最长子串 3 滑动窗口
class Solution {public: int lengthOfLongestSubstring(string s) { unordered_map mp;//滑动窗口中字母出现次数 int ans=0; int n=s.size(); int start,end=0; //滑动窗口边界 while(end=2){//左边界向右滑，直至没有重复字母 mp[s[start]]--; start++; } ans=max(ans,end-start+1); end++;//右边界向左滑 } return ans; }};4 字符串解码 394 递归
每层dfs返回一个string，是这个括号内 解码后 的字符串
入口：遇到 [ 进入下一层递归
出口：遇到 ] 返回当前层递归处理后的字符串
class Solution {public: int idx=0;//注意是全局变量，每层递归共享 string dfs(string s){ int n=s.size(); string res;//当前层递归要返回的解码后字符串 while(idx=\'0\'&&s[idx]=\'0\'&&s[idx]<=\'9\'){ num=num*10+(s[idx]-\'0\'); idx++; } //数字后一定跟的是左括号，现在idx是左括号 idx++; string ress= dfs(s); //ress是下层递归处理后的字符串，需要乘以当前倍数 for(int i=1;i=\'a\'&&s[idx]<=\'z\'){//字母拼入res res=res+s[idx]; }else{//右括号 return res; } idx++; }//while return res; } string decodeString(string s) { return dfs(s); }};栈 3道
1 有效的括号 20 简单 √
( [ ) ] 是false
左括号进栈，右括号和栈顶匹配
class Solution {public: bool isValid(string s) { stack sk; unordered_map mp={ {\')\',\'(\'}, {\']\',\'[\'}, {\'}\',\'{\'} }; for(char x:s){ if(mp.count(x)>0){//右括号 if(sk.empty() || sk.top()!=mp[x]){ return false; } sk.pop();//匹配了 }else{ //左括号 sk.push(x); } } return sk.empty(); }};2 每日温度 739
单调栈。从底向顶递减。从右往左遍历数组。向右看，看到第一个比自己高的。
class Solution {public: vector dailyTemperatures(vector& temperatures) { int n=temperatures.size(); vector ans(n); stack sk; for(int i=n-1;i>=0;i--){ while(!sk.empty()){ if(temperatures[i]<temperatures[sk.top()]){//找到第一个比自己大的 ans[i]=sk.top()-i; break; } sk.pop();//栈里比自己小的不要，出栈 } if(sk.empty()){ ans[i]=0; } sk.push(i); } return ans; }};3 最小栈 155
辅助栈
class MinStack {public: stack sk; //主栈，正常入栈出栈 stack sk_min; //栈顶保存主栈当前的最小值 MinStack() { sk_min.push(INT_MAX); } void push(int val) { sk.push(val); if(valpush(val); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */链表 11道
1 反转链表 206 简单 √
反转单链表head
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public: ListNode* reverseList(ListNode* head) { //if(!head) return nullptr; ListNode* cur=head,*pre=nullptr; while(cur){ ListNode* nxt=cur->next; cur->next=pre; pre=cur; cur=nxt; } return pre; }};哈希：
2 相交链表 160 简单√
遍历A，将每个结点加入set
遍历B，返回第一个在set中的结点
class Solution {public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { unordered_set set_a; ListNode* a=headA; while(a){ set_a.insert(a); a=a->next; } ListNode* b=headB; while(b){ if(set_a.count(b)>0){ return b; } b=b->next; } return NULL; }};3 环形链表 141 简单√
与上一题类似
class Solution {public: bool hasCycle(ListNode *head) { unordered_set set; ListNode* p=head; while(p){ if(set.count(p)>0){ return true; } set.insert(p); p=p->next; } return false; }};4 合并两个有序链表 21 简单 √
class Solution {public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* h=new ListNode(); ListNode *m=h,*a=list1,*b=list2; while(a&&b){ if(a->valval){ m->next=a; a=a->next; }else{ m->next=b; b=b->next; } m=m->next; } if(a){ m->next=a; }else{ m->next=b; } return h->next; }};扩展：
双指针：
5 排序链表 148
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
解：分成左右两个子链表，分别排序 —–> 合并两个升序链表
class Solution {public: //找中间节点函数。偶数返回前一半的最后一个节点，奇数返回中间结点 ListNode* findmid(ListNode* head){ ListNode* slow=head,*fast=head; while(fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } return slow; } ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* h=new ListNode(); ListNode *m=h,*a=list1,*b=list2; while(a&&b){ if(a->valval){ m->next=a; a=a->next; }else{ m->next=b; b=b->next; } m=m->next; } if(a){ m->next=a; }else{ m->next=b; } return h->next; } ListNode* sortList(ListNode* head) { //递归出口：空结点或只有一个节点，不用排序了 if(!head|| !head->next){ return head; } ListNode * mid=findmid(head); ListNode* head2=mid->next; mid->next=nullptr; return mergeTwoLists(sortList(head),sortList(head2)); }};6 回文链表 简单 234 (1+5)
拆成两半（用快慢指针找到中间结点），第二半反转，再比较
class Solution {public: //找中间节点函数。偶数返回前一半的最后一个节点，奇数返回中间结点 ListNode* findmid(ListNode* head){ ListNode* slow=head,*fast=head; while(fast&&fast->next&&fast->next->next){ slow=slow->next; fast=fast->next->next; } return slow; } //反转函数 ListNode* reverse(ListNode* head){ ListNode* cur=head;//当前遍历结点 ListNode* ne;//下一个要处理的结点 ListNode* pre=nullptr;//哨兵 while(cur){ ne=cur->next; cur->next=pre; pre=cur; cur=ne; } return pre; } //主函数 bool isPalindrome(ListNode* head) { ListNode* tail=findmid(head); ListNode* right=tail->next; tail->next=nullptr; ListNode* head2=reverse(right); //如果是奇数，head2比head短 while(head2){ if(head->val!=head2->val) return false; head=head->next; head2=head2->next; } return true; }};7 环形链表 II 142
快慢指针。
背诵方法：快慢指针相等时，慢指针=head，两指针同时移动一步，直到重合
class Solution {public: ListNode *detectCycle(ListNode *head) { ListNode* slow=head,*fast=head; while(true){ if(fast==NULL|| fast->next==NULL) return NULL; slow=slow->next; fast=fast->next->next; if(slow==fast) break; } slow=head; while(slow!=fast){ slow=slow->next; fast=fast->next; } return fast; }};类似思想：
8 寻找重复数 287 位运算
与上一题一样：
class Solution {public: int findDuplicate(vector& nums) { int slow=0,fast=0; while(true){ slow=nums[slow];//移动一步 fast=nums[nums[fast]];//移动两步 if(slow==fast) break; } slow=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return slow; }};9 删除链表的倒数第 N 个结点 19 √ 注意哨兵
fast 移动n个。slow在头。
fast和slow同时移动。fast移动到尾，要移动len-n个; 此时slow也移动len-n个，则slow到尾就是len-(len-n)=n个
class Solution {public: ListNode* removeNthFromEnd(ListNode* head, int n) { ListNode *a=new ListNode(0,head);//哨兵结点 ListNode *slow=a,*fast=head; //q移动n个 for(int i=1;inext; } //同时移动 while(fast){ slow=slow->next; fast=fast->next; } //pre->next就是倒数第n个结点 slow->next=slow->next->next; //删除操作 return a->next; }};10 两数相加 2
模拟。
class Solution {public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* l=new ListNode(); ListNode* head=l;//保存头结点，以便最后返回 int carry=0; while(l1 || l2){ int n1=l1?l1->val:0; //不存在则补0 int n2=l2?l2->val:0; int sum=n1+n2+carry; carry=sum/10; ListNode* t=new ListNode(); t->val=sum%10; l->next=t; l=t; if(l1) l1=l1->next; if(l2) l2=l2->next; } if(carry>0){ l->next=new ListNode(carry); } return head->next; }};11 LRU 缓存 146
双链表。dummy->pre即为队尾
O(1)，需要用map
struct Node { int key; int value; Node* pre; Node* next; Node() { key = 0; value = 0; }};class LRUCache {public: int capacity; Node* dummy; unordered_map key_to_node; LRUCache(int c) { capacity=c; dummy=new Node(); dummy->pre=dummy; dummy->next=dummy; } void remove_node(Node* x){ x->pre->next=x->next; x->next->pre=x->pre; } void add_to_head(Node* x){ x->next=dummy->next; x->pre=dummy; dummy->next->pre=x; dummy->next=x; } void move_to_head(Node* x){ remove_node(x); add_to_head(x); } int get(int key) { if(key_to_node.count(key)==0){ return -1; } Node* a=key_to_node[key]; move_to_head(a); return a->value; } void put(int key, int value) { //有这个key if(key_to_node.count(key)>0){ key_to_node[key]->value=value; move_to_head(key_to_node[key]); return; } //没有 Node* node=new Node(); node->key=key; node->value=value; add_to_head(node); key_to_node[key]=node; if(key_to_node.size()>capacity){ Node* a=dummy->pre; remove_node(a); key_to_node.erase(a->key); } }};/** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); *数组 18道
1 旋转图像 48
背诵
先对矩阵求对称，再对每一行左右翻转
class Solution {public: void rotate(vector<vector>& matrix) { int n=matrix.size(); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ swap(matrix[i][j],matrix[j][i]); } } for(int i=0;i<n;i++){ for(int j=0;j<n/2;j++){ swap(matrix[i][j],matrix[i][n-j-1]); } } }};二分查找 3道
模板：
- 返回第一个出现的位置
左侧是=它的
int find(vector nums,int target){ int n=nums.size(); int l=0,r=n-1; while(lnums[mid]) l=mid+1; else r=mid-1; } return l;}- 简单的找
int find(vector nums,int target){ int n=nums.size(); int l=0,r=n-1; while(lnums[mid]) l=mid+1; else r=mid-1; } return -1;}1 在排序数组中查找元素的第一个和最后一个位置 34
第一个：用模板1.
最后一个：用模板1查target+1，得到的位置再减一
class Solution {public: //模板 int find(vector nums,int target){ int n=nums.size(); int l=0,r=n-1; while(lnums[mid]) l=mid+1; else r=mid-1; } return l; } vector searchRange(vector& nums, int target) { vector ans; int first=find(nums,target); if(first>=nums.size()||nums[first]!=target){ return {{-1,-1}}; } int last=find(nums,target+1); ans.push_back(first); ans.push_back(last-1); return ans; }};2 搜索旋转排序数组 33
nums是无序的，不能直接用二分
nums一定是这样的左右两段有序数组，称为左段、右段。
左段都是>=nums[0]的，右段都是<nums[0]的。
先判断mid在左段还是右段，再判断target在mid左侧还是右侧
class Solution {public: int search(vector& nums, int target) { int n=nums.size(); int l=0,r=n-1; while(l<=r){ int mid=(l+(r-l)/2); if(nums[mid]==target) return mid; if(nums[0]=nums[0]&&targetnums[mid]&&target<=nums[n-1]){ l=mid+1; }else{ r=mid-1; } } } return -1; }};3 搜索二维矩阵 II 240 矩阵 √
遍历每行，对每一行用二分查找。
class Solution {public: bool find(vector &nums,int target){//注意要写&号，不然会超出内存限制 int n=nums.size(); int l=0,r=n-1; while(l<=r){ int mid=l-(l-r)/2; if(nums[mid]==target) return true; if(target<nums[mid]) r=mid-1; else l=mid+1; } return false; } bool searchMatrix(vector<vector>& matrix, int target) { int m=matrix.size(); int n=matrix[0].size(); for(int i=0;i<m;i++){ if(find(matrix[i],target)){ return true; } } return false; }};快排 2道
模板
void quickSort1(vector& nums, int l, int r) { // 1. 递归终止条件：当子数组长度为1或空时，无需排序 if (l >= r) return; // 2. 初始化分区参数： // - i 初始在左边界左侧（l-1） // - j 初始在右边界右侧（r+1） // - 基准值 x 选中间元素（避免极端情况如全排序数组导致最坏时间复杂度） int i = l - 1, j = r + 1; int x = nums[l+(r-l)/2]; // 3. Hoare 分区循环：双指针从两端向中间移动 while (i =x 的元素 do i++; while (nums[i] < x); // 3.2 移动右指针 j：跳过所有大于 x 的元素，直到找到 x); // 3.3 如果指针未交错，交换左右指针的元素（确保左边 =x） if (i = j 时，j 是左半部分的最右端） // - 左子数组：[l, j]（所有元素 =x） quickSort1(nums, l, j); quickSort1(nums, j + 1, r);}1 数组中的第K个最大元素 215
class Solution {public: //从大到小排序。 k是数组下标 int helper(vector& nums,int l,int r,int k){ if(l>=r) return nums[k];//递归出口.排好序了 int n=nums.size(); int p=l+(r-l)/2; int x=nums[p]; //枢轴 int i=l-1,j=r+1; while(ix); do{j--;}while(nums[j]<x); if(i[j+1,r]中的元素 if(k<=j) return helper(nums,l,j,k);//不用管右边的具体顺序 else return helper(nums,j+1,r,k);//不用管左边 } int findKthLargest(vector& nums, int k) { int n=nums.size(); return helper(nums,0,n-1,k-1); }};2 前 K 个高频元素 347
class Solution {public: vector ans; //按频率由大到小排序。k：还要找出k个高频数 void helper(vector nums,int l,int r,int k,unordered_map v_f){ if(k==0) return; int p=l+(r-l)/2; int fre=v_f[nums[p]]; int i=l-1,j=r+1; while(ifre); do{j--;} while(v_f[nums[j]]<fre); if(i=len){ //[l,j]的数全加进ans for(int i=l;i<=j;i++){ ans.push_back(nums[i]); } helper(nums,j+1,r,k-len,v_f);//还要找k-len个 }else{ helper(nums,l,j,k,v_f); } } vector topKFrequent(vector& nums, int k) { unordered_map v_f;//值--频次 unordered_set v; //set用于数组去重 //遍历nums，构造map for(int x:nums){ v_f[x]++; v.insert(x);//去重 } //构造去重后的数组a vector a; for(int x:v){ a.push_back(x); } helper(a,0,a.size()-1,k,v_f); return ans; }};双指针 6道
1 移动零 283 数组 简单
时刻保证 p1左边全是非0
class Solution {public: void moveZeroes(vector& nums) { int n=nums.size(); int p1=0,p2=0; while(p2<n){ if(nums[p2]!=0){ swap(nums[p1],nums[p2]); p1++; } p2++; } }};类似：
2 颜色分类 75
保证：p0左面全是0，p2右面全是2
class Solution {public: void sortColors(vector& nums) { int n=nums.size(); int p0=0,p1=0,p2=n-1; while(p1<=p2){ if(nums[p1]==0){ swap(nums[p0],nums[p1]); p0++; p1++; }else if(nums[p1]==2){ swap(nums[p1],nums[p2]); p2--; //不能p1++，因为i的位置可能是0，要和p0换 }else{ p1++; } } }};3 盛最多水的容器 11 √
class Solution {public: int maxArea(vector& height) { int n=height.size(); int i=0,j=n-1; int ans=0; while(i<j){ ans=max(ans,(j-i)*min(height[i],height[j])); if(height[i]<height[j]){ i++; }else{ j--; } } return ans; }};4 最短无序连续子数组 581
左段的最大值小于右边，右段的最小值大于左边
找中段的左右边界begin end
end：从左到右，最后一个<左面的max的
class Solution {public: int findUnsortedSubarray(vector& nums) { int n=nums.size(); int begin=0,end=-1; int max=nums[0],min=nums[n-1]; for(int i=0;i<n;i++){ //从左到右确定end 、更新max //end最终停在 最后一个max的 if(nums[i]>=max){ max=nums[i]; }else{ end=i; } //从右到左确定begin 、更新min //begin最终停在 最后一个>min的地方。所以begin左边都是<min的 int j=n-i-1; if(nums[j]<=min){ min=nums[j]; }else{ begin=j; } } return end-begin+1; //初始化begin=0,end=-1，这样end-begin+1=0 }};5 三数之和 15
先排序，再枚举。这样枚举的[a,b,c] 满足 a<=b<=c ，时间复杂度低
class Solution {public: vector<vector> threeSum(vector& nums) { int n=nums.size(); sort(nums.begin(),nums.end()); vector<vector> ans; for(int i=0;i0&&nums[i]==nums[i-1]) continue;// 跳过重复元素 // 双指针，目标是找到 nums[l] + nums[r] = -nums[i] int l=i+1,r=n-1; int target=-nums[i]; while(l<r){ int sum=nums[l]+nums[r]; if(sum==target){ ans.push_back({nums[i],nums[l],nums[r]}); l++; r--; // 跳过重复元素 while(l<r&&nums[l]==nums[l-1]) l++; while(l<r&&nums[r]==nums[r+1]) r--; }else if(sum<target){ l++; }else{ r--; } } } return ans; }};6 下一个排列 31
升序是最小的排列，降序是最大的排列。变大需要升序变降序
改变的地方越靠后，改变越小
class Solution {public: void nextPermutation(vector& nums) { int n=nums.size(); //从后往前找 第一个升序对nums[i]=0&&nums[i]>=nums[j]){ i--; j--; } if(i>=0){ //找满足nums[k]>nums[i]的最小的nums[k] int k=n-1; while(nums[k]<=nums[i]) k--; swap(nums[i],nums[k]); } //逆置 [j,n-1]，使其升序。升序是最小的排列 int l=j,r=n-1; while(l<r){ swap(nums[l],nums[r]); l++; r--; } }};蓝色的下一个排列为橙色：
回溯 6道
-
确定回溯函数参数
-
确定终止条件（叶子
-
确定单层遍历逻辑（处理、递归、回溯）
-
组合
1 组合总和 39 搜索
class Solution {public: vector<vector> ans; vector path; void backtracking(vector& candidates,int target,int sum,int idx){ if(sum==target){ ans.push_back(path); return; } if(sum>target){ return; } for(int i=idx;i<candidates.size();i++){ path.push_back(candidates[i]); backtracking(candidates,target,sum+candidates[i],i); //可重复选，所以是i，不是i+1 path.pop_back(); } } vector<vector> combinationSum(vector& candidates, int target) { backtracking(candidates,target,0,0); return ans; }};2 电话号码的字母组合 17 搜索
class Solution {public: string map[10]={ \"\",\"\",\"abc\",\"def\",//0，1，2，3 \"ghi\",\"jkl\",\"mno\",//4，5，6 \"pqrs\",\"tuv\",\"wxyz\"//7，8，9 }; vector ans; string path; void backtracking(string digits,int idx){ if(idx==digits.size()){ ans.push_back(path); return; } string letters=map[digits[idx]-\'0\']; for(int i=0;i<letters.size();i++){//遍历数字对应的字母集合 path.push_back(letters[i]); backtracking(digits,idx+1); path.pop_back(); } } vector letterCombinations(string digits) { if(digits.size()==0){ return {}; } backtracking(digits,0); return ans; }};子集：
要获取所有节点
3 子集 78
class Solution {public: vector<vector> ans; vector path; void backtracking(vector& nums,int idx){ if(idx>nums.size()){ return; } ans.push_back(path); for(int i=idx;i<nums.size();i++){ path.push_back(nums[i]); backtracking(nums,i+1); path.pop_back(); } } vector<vector> subsets(vector& nums) { backtracking(nums,0); return ans; }};- 排列
- 每层都是从0开始搜索而不是idx
- 需要used数组记录path里都放了哪些元素了
4 全排列 46 搜索
class Solution {public: vector<vector> ans; vector path; void backtracking(vector &nums,vector used){ if(path.size()==nums.size()){ ans.push_back(path); return; } for(int i=0;i<nums.size();i++){ if(used[i]==true) continue; path.push_back(nums[i]); used[i]=true; backtracking(nums,used); path.pop_back(); used[i]=false; } } vector<vector> permute(vector& nums) { vector used(nums.size(),false); backtracking(nums,used); return ans; }};- 其他
5 括号生成 22 搜索
class Solution {public: vector ans; string path; void dfs(int l,int r,int n){//左括号数量、右括号数量 if(l==n&&r==n){ ans.push_back(path); return; } if(l<n){//如果还能加入左括号 就加入 path.push_back(\'(\'); dfs(l+1,r,n); path.pop_back(); } if(r<l&&r<n){//只有还有左括号的时候才能压入右括号 path.push_back(\')\'); dfs(l,r+1,n); path.pop_back(); } } vector generateParenthesis(int n) { dfs(0,0,n); return ans; }};6 单词搜索 79 矩阵
class Solution {public: bool dfs(vector<vector>& board,string word,int i,int j,int idx){ int m=board.size(); int n=board[0].size(); //过界 或 不是要找的字母 if(i=m||j=n||board[i][j]!=word[idx]){ return false; } //找完了 if(idx==word.size()-1){ return true; } //符合board[i][j]=word[idx]，继续找下一个字母: board[i][j]=\'\\0\';//标记，防止重复 bool res=dfs(board,word,i+1,j,idx+1)||dfs(board,word,i-1,j,idx+1)|| dfs(board,word,i,j+1,idx+1)||dfs(board,word,i,j-1,idx+1); //上下左右继续 board[i][j]=word[idx];//回溯 return res; } bool exist(vector<vector>& board, string word) { int m=board.size(); int n=board[0].size(); for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(dfs(board,word,i,j,0)){ return true; } } } return false; }};动态规划 20道
动规五部曲分别为：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
基础
1 爬楼梯 70 简单 √
class Solution {public: int climbStairs(int n) { vector dp(50); dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]; } return dp[n]; }};2 不同路径 62 √
class Solution {public: int uniquePaths(int m, int n) { //dp[i][j]：到这格有多少条不同路径 vector<vector> dp(m,vector(n)); //最左一列 for(int i=0;i<m;i++){ dp[i][0]=1; } //最上一行 for(int j=0;j<n;j++){ dp[0][j]=1; } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1];//从左边来+从上边来 } } return dp[m-1][n-1]; }};3 最小路径和 64 动态规划 √
dp[i][j]：走到grid[i][j]处的最小路径和
分从左走过来、从上走过来 两种情况
class Solution {public: int minPathSum(vector<vector>& grid) { int m=grid.size(); int n=grid[0].size(); vector<vector> dp(m,vector(n)); dp[0][0]=grid[0][0]; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(i==0&&j==0) continue; if(i==0){ //第一行 边界 dp[0][j]=dp[0][j-1]+grid[0][j]; }else if(j==0){ //第一列边界 dp[i][0]=dp[i-1][0]+grid[i][0]; }else{ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]; } } } return dp[m-1][n-1]; }};4 最大正方形 221 动态规划
左、上、左上，三者取最小
class Solution {public: int maximalSquare(vector<vector>& matrix) { int m=matrix.size(); int n=matrix[0].size(); vector<vector> dp(m,vector(n)); int max_side=0;//最大边长 //处理第一行和第一列边界 for(int i=0;i<m;i++){ if(matrix[i][0]==\'1\'){ dp[i][0]=1; max_side=1; } } for(int j=0;j<n;j++){ if(matrix[0][j]==\'1\'){ dp[0][j]=1; max_side=1; } } for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][j]==\'1\'){ dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1; max_side=max(max_side,dp[i][j]); } } } return max_side*max_side; }};5 不同的二叉搜索树 96 树
dp[i] :总结点数为i的数，有dp[i]种
一棵二叉搜索树，总结点数为num，根节点的值为value，则左子树的结点个数为value-1，右子树的结点个数为num-value
种数=左子树种数*右子树种数
class Solution {public: int numTrees(int n) { vector dp(n+1); dp[0]=1; //空结点也算1种 dp[1]=1; for(int num=2;num<=n;num++){//num是总结点数 for(int value=1;value<=num;value++){//value是根结点的值，范围肯定是在[1,num]之间 dp[num]+=dp[value-1]*dp[num-value]; } } return dp[n]; }};子序列
1 回文子串 647 字符串
dp[i][j]：s[i]到s[j]的子串是否是回文串
注意：i和j遍历的顺序，要先遍历更短的子串。（动态规划的依赖性）
class Solution {public: int countSubstrings(string s) { int ans=0; int n=s.size(); vector<vector> dp(n,vector(n)); for(int j=0;j<n;j++){ for(int i=0;i<=j;i++){ if(i==j){ dp[i][j]=true; }else if(j==i+1){ dp[i][j]=s[i]==s[j]; }else{ dp[i][j]=s[i]==s[j]&&dp[i+1][j-1]; } if(dp[i][j]) ans++; } } return ans; }};2 最长回文子串 5 字符串
和上一题几乎一样，只要记录、更新长度就好
class Solution {public: string longestPalindrome(string s) { int maxlen=0; int begin=0; int n=s.size(); vector<vector> dp(n,vector(n)); for(int j=0;j<n;j++){ for(int i=0;imaxlen){ maxlen=j-i+1; begin=i; } } } } return s.substr(begin,maxlen); }};3 编辑距离 72 字符串
dp[i][j]：word1的前i个字符 转变成 word2的前j个字符，最少的操作次数
遍历两个字符串
- 字符相等。转化为：word1-1转变为word2-1
- 字符不等
- 替换这个字符。转化为：word1-1转变为word2-1 +1次操作
- word1插入这个字符。word1转变为word2 -1 +1次操作
- word2删除这个字符。word1-1转变为word2 +1次操作
dp[i][j]为以上情况的最小的那个
class Solution {public: int minDistance(string word1, string word2) { int len1 = word1.size(); int len2 = word2.size(); vector<vector> dp(len1 + 1, vector(len2 + 1, 0x3f3f3f3f)); // 初始化dp for (int i = 0; i <= len1; i++) { dp[i][0] = i; // word1删除i次变成空 } for (int j = 0; j <= len2; j++) { dp[0][j] = j; // 空串插入n次变成word2 } // 遍历两个字符串 for (int i = 1; i <= len1; i++) { for (int j = 1; j <= len2; j++) { if (word1[i - 1] == word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } int replace = dp[i - 1][j - 1] + 1; int insert = dp[i][j - 1] + 1; int deletee = dp[i - 1][j] + 1; dp[i][j] = min(dp[i][j], min(replace, min(insert, deletee))); } } return dp[len1][len2]; }};4 最大子数组和 53 数组
dp[i]：以第i个数结尾的子数组（必须选上），最大和为dp[i]
class Solution {public: int maxSubArray(vector& nums) { int n=nums.size(); vector dp(n+1); int ans=-0x3f3f3f3f; dp[0]=0; for(int i=1;i<=n;i++){ if(dp[i-1]<=0){ dp[i]=nums[i-1]; }else{ dp[i]=dp[i-1]+nums[i-1]; } ans=max(ans,dp[i]); } return ans; }};5 乘积最大子数组 152 数组
类似上一题
class Solution {public: int maxProduct(vector& nums) { int n=nums.size(); int dp_max[n+1];//以第i个数为结尾的子数组的乘积最大值 int dp_min[n+1]; memset(dp_max,0,n+1); memset(dp_min,0,n+1); dp_max[0]=1; dp_min[0]=1; int ans=nums[0]; for(int i=1;i<=n;i++){ dp_max[i]=max(nums[i-1], max(dp_max[i-1]*nums[i-1],dp_min[i-1]*nums[i-1])); dp_min[i]=min(nums[i-1], min(dp_max[i-1]*nums[i-1],dp_min[i-1]*nums[i-1])); ans=max(ans,dp_max[i]); } return ans; }};6 最长递增子序列 300 数组
dp[i]表示以nums的第i个元素结尾的最长递增子序列长度
class Solution {public: int lengthOfLIS(vector& nums) { int n=nums.size(); int dp[n+1]; memset(dp,0,n+1); int ans=0; for(int i=1;i<=n;i++){ dp[i]=1; for(int j=1;j<i;j++){ if(nums[j-1]<nums[i-1]){ dp[i]=max(dp[i],dp[j]+1); }else{ dp[i]=dp[i]; } } ans=max(ans,dp[i]); } return ans; }};7 最长连续序列 128 数组 不是动规
class Solution {public: int longestConsecutive(vector& nums) { int ans=0; unordered_set st(nums.begin(),nums.end());//nums加入set去重 //遍历set for(int num:st){ if(st.count(num-1)) continue; //以num-1开头的序列肯定比以num开头的序列长，已经处理过了，跳过 int x=num+1; //不断找num+1,num+2.....把此序列全找完，断了就结束 while(st.count(x)){ x++; } //此序列以num开头，x-1结尾 ans=max(ans,x-num); } return ans; }};其他
1 打家劫舍 198 数组
class Solution {public: int rob(vector& nums) { int n=nums.size(); vector dp(n+1);//dp[i]：偷前i间房子的最高金额 dp[0]=0; dp[1]=nums[0]; for(int i=2;i<=n;i++){ dp[i]=max(nums[i-1]+dp[i-2],dp[i-1]);//偷，不偷 } return dp[n]; }};2 打家劫舍 III 337 树
递归。左右根，因为要先知道左右子树，才能知道根
两个dp数组：
yes[t] : 以t为根的树，选择偷t，获得的最高金额
no[t] : 以t为根的树，选择不偷t，获得的最高金额
class Solution {public: unordered_map yes,no; void dfs(TreeNode* t) { if (!t) return; dfs(t->left); dfs(t->right); yes[t] = no[t->left] + no[t->right] + t->val; no[t] = max(yes[t->left], no[t->left]) + max(yes[t->right], no[t->right]); } int rob(TreeNode* root) { dfs(root); return max(yes[root], no[root]); }};3 最佳买卖股票时机含冷冻期 309 数组
今天结束后，有四种状态：
- 不持有（今天肯定没买）
- 今天卖了——昨天是持有状态
- 没买没卖——昨天不持有
- 持有（今天肯定没卖）
- 今天买了——昨天不持有、没卖（冷冻）
- 没买没卖——昨天持有
class Solution {public: int maxProfit(vector& prices) { int n=prices.size(); int dp[n][4]; //dp[i][j]：第i天结束，状态为j，目前的收益。 //prices从第0天开始 memset(dp,0,sizeof dp); //4种状态： dp[0][0]=0;//不持有，今天卖出 dp[0][1]=0;//不持有，今天没卖（也没买） dp[0][2]=-prices[0];//持有，今天买的（也没卖） dp[0][3]=-prices[0];//持有，今天没买，之前买的（今天没买没卖） for(int i=1;i<n;i++){ dp[i][0]=prices[i]+max(dp[i-1][2],dp[i-1][3]);//昨天是持有状态 dp[i][1]=max(dp[i-1][0],dp[i-1][1]);//昨天不持有 dp[i][2]=-prices[i]+dp[i-1][1];//今天买，说明昨天不持有且没卖 dp[i][3]=max(dp[i-1][2],dp[i-1][3]);//昨天持有 } return max(dp[n-1][0],dp[n-1][1]);//最后肯定全卖了，不持有 }};背包 5道
01 背包：
物品不可重复使用。
外循环遍历物品，内循环遍历背包 target，且内循环倒序
完全背包：
元素可重复使用。内循环正序。
（1）组合：不考虑物品之间顺序：物品放在外循环，背包target在内循环。
（2）排列：需考虑物品之间的顺序：背包 target 放在外循环，物品放在内循环。
01背包：
1 分割等和子集 416 数组
物品：nums 物品重量：nums[i] 背包容量：sum/2
//bool dp[i][j]：从前i个数选，和为j，可以选出来吗class Solution {public: bool canPartition(vector& nums) { int sum=0; for(int x:nums){ sum+=x; } if(sum%2==1){//不能是奇数 return false; } int n=nums.size(); int target=sum/2; vector<vector> dp(n+1,vector(target+1)); dp[0][0]=true; for(int i=1;i<=n;i++){ for(int j=0;j<=target;j++){ if(nums[i-1]<=j){//可选可不选 dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];//不选 or 选 }else{//不能选 dp[i][j]=dp[i-1][j]; } } } return dp[n][target]; }};//公式版：class Solution {public: bool canPartition(vector& nums) { int n=nums.size(); int sum=0; for(int num:nums){ sum+=num; } if(sum%2==1) return false; int target=sum/2; vector dp(target+1); //dp[j]:和为j能不能选出 dp[0]=true; for(int i=0;i=0;j--){ if(j>=nums[i]){ dp[j]=dp[j]||dp[j-nums[i]]; //不选 or 选 }else{ dp[j]=dp[j]; //只能不选 //这行可以没有 } } } return dp[target]; }};2 目标和 494
充当正数的num和 - 充当负数的num和=要求的target
充当正数的num和 + 充当负数的num和 =sum 是固定的
综合得，2*充当正数的num和=target+sum
target_new=(target+sum)/2
//dp[i][j]：从前i个数中选，和为j的种数class Solution {public: int findTargetSumWays(vector& nums, int target) { int n=nums.size(); int sum=0; for(int x:nums){ sum+=x; } if((sum+target)%2==1) return 0; int t=(sum+target)/2; if(t<0) return 0; vector<vector> dp(n+1,vector(t+1)); dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=0;j<=t;j++){ if(nums[i-1]<=j){//可选可不选 dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]];//不选+选 }else{//不能选 dp[i][j]=dp[i-1][j]; } } } return dp[n][t]; }};//公式法：class Solution {public: int findTargetSumWays(vector& nums, int target) { int n=nums.size(); int sum=0; for(int num:nums){ sum+=num; } if((sum+target)%2==1) return 0; int target_new=(sum+target)/2; if(target_new<0) return 0; vector dp(target_new+1);//dp[j] 表示和为 j 的 num 组合有 dp[j] 种。 dp[0]=1; for(int i=0;i=0;j--){ if(j>=nums[i]){ dp[j]=dp[j]+dp[j-nums[i]];//不选的组合种数+选的组合种数 }else{//不选 dp[j]=dp[j]; } } } return dp[target_new]; }};完全背包：
1 零钱兑换 322
组合。
dp[j]：j元最少需要的硬币数
class Solution {public: int coinChange(vector& coins, int amount) { int n=coins.size(); vector dp(amount+1,INT_MAX); dp[0]=0; for(int i=0;i<n;i++){ for(int j=1;j<=amount;j++){ if(coins[i]<=j){ dp[j]=min(dp[j],dp[j-coins[i]]+1);//不选或选 } } } if(dp[amount]==INT_MAX) return -1;//没找到 return dp[amount]; }};2 完全平方数 279
**组合。**物品：1,4,16,25…；背包：n
class Solution {public: int numSquares(int n) { vector dp(n+1,INT_MAX); dp[0]=0; for(int i=1;i<=sqrt(n);i++){ for(int j=1;j<=n;j++){ if(j<i*i){ dp[j]=dp[j]; }else{ dp[j]=min(dp[j],dp[j-i*i]+1); } } } return dp[n]; }};3 单词拆分 139
排列。物品：wordDict；背包：s
dp[i]：s的以第i个字母结尾的字符串是否能由 wordDict 中组合而成
class Solution {public: bool wordBreak(string s, vector& wordDict) { int n=s.size(); vector dp(n+1); dp[0]=true; for(int i=1;i<=n;i++){ for(int j=0;ji){//不能选 dp[i]=dp[i]; }else{ dp[i]=dp[i]|| (dp[i-len]&&word==s.substr(i-len,len)); //不选或选 } } } return dp[n]; }};贪心 10道
1 多数元素 169 简单√
1
2 买卖股票的最佳时机 121 简单
1
3 两数之和 1 简单
map
4 找到所有数组中消失的数字 448
奇技淫巧
num范围是1到n，可以映射数组的[0,n)，n个位置。
当前元素是 nums[i]，那么我们把第 nums[i]−1 位置的元素 乘以 -1，表示这个该位置出现过
class Solution {public: vector findDisappearedNumbers(vector& nums) { int n=nums.size(); vector ans; for(int i=0;i0){ nums[j-1]=-nums[j-1]; } } for(int i=0;i0){ ans.push_back(i+1); } } return ans; }};5 根据身高重建队列 406
h从大到小，k从小到大 排序。依次插入ans中
class Solution {public: bool static compare_design(vector a,vector b){ if(a[0]!=b[0]) return a[0]>b[0]; return a[1]<b[1]; } vector<vector> reconstructQueue(vector<vector>& people) { int n=people.size(); vector<vector> ans; sort(people.begin(),people.end(),compare_design); for(auto p:people){ if(p[1]>=ans.size()){ ans.push_back(p); }else{ ans.insert(ans.begin()+p[1],p); } } return ans; }};6 除自身以外数组的乘积 238 前缀和
前缀和数组left：左面的元素乘积
right：右面的元素乘积
ans=left*right
class Solution {public: vector productExceptSelf(vector& nums) { int n=nums.size(); vector left(n); vector right(n); left[0]=1; for(int i=1;i=0;i--){ right[i]=right[i+1]*nums[i+1]; } vector ans(n); for(int i=0;i<n;i++){ ans[i]=left[i]*right[i]; } return ans; }};7 和为 K 的子数组 560 前缀和
想找[i , j]数组和为k
前缀和数组sum
sum[j]-sum[i]=k
想找前面有没有sum[i]
即有没有sum[i]=sum[j]-k
前面都保存到map里，去map中找 sum[j]-k
class Solution {public: int subarraySum(vector& nums, int k) { int n=nums.size(); vector sum(n+1); sum[0]=0; for(int i=1;i<=n;i++){ sum[i]=nums[i-1]+sum[i-1]; } unordered_map mp;//前缀和为sum的数量是mp[sum] int ans=0; //遍历sum for(int i=0;i0){ ans+=mp[x]; } mp[sum[i]]++; } return ans; }};8 任务调度器 621
建立大小为 n+1 的桶子，个数为任务数量最多的那个任务
答案 = (桶个数 - 1) * (n + 1) + 最后一桶的任务数
情况：如果被桶全被填满了，没有空闲时间，答案就是任务的数量
class Solution {public: int leastInterval(vector& tasks, int n) { unordered_map mp; int tong=0;//桶个数 for(char task:tasks){ mp[task]++; tong=max(tong,mp[task]); } int count=0;//最后一桶的任务数 for(auto x:mp){ if(x.second==tong){ count++; } } int ans=(tong-1)*(n+1)+count; int len=tasks.size(); return max(ans,len); }};9 跳跃游戏 55
- 如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
- 可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
- 如果可以一直跳到最后，就成功了
class Solution {public: bool canJump(vector& nums) { int n=nums.size(); int reach=0; for(int i=0;ireach) return false;//前面没有能跳到i的 reach=max(reach,i+nums[i]); if(reach>=n-1){ return true; } } return false; }};10 合并区间 56 双指针
j，起点比i起点小的都合并
class Solution {public://按起点由小到大排序 static bool cmp(vector a,vector b){ if(a[0]!=b[0]) return a[0]<b[0]; return a[1]<b[1]; } vector<vector> merge(vector<vector>& intervals) { sort(intervals.begin(),intervals.end(),cmp); int n=intervals.size(); vector<vector> ans; int i=0; while(i<n){ int t=intervals[i][1];//目前最右的 int j=i+1; //起点<t的合并 while(j<n&&intervals[j][0]<=t){ t=max(t,intervals[j][1]);//更新最右 j++; } ans.push_back({intervals[i][0],t}); i=j; } return ans; }};图 3道
1 岛屿数量 200 搜索（联通块）dfs
- 0 —— 海洋格子
- 1 —— 陆地格子（未遍历过）
- 2 —— 陆地格子（已遍历过） 避免重复遍历
遍历。是1则DFS它相邻的。
class Solution {public: void dfs(vector<vector> &grid,int i,int j){//注意&，否则不对 if(!isValid(grid,i,j)){ return; } if(grid[i][j]!=\'1\'){ return; } grid[i][j]=\'2\'; // 访问上、下、左、右四个相邻结点 dfs(grid,i-1,j); dfs(grid,i+1,j); dfs(grid,i,j-1); dfs(grid,i,j+1); } //判断是否出界 bool isValid(vector<vector> &grid,int i,int j){////注意&，否则超时 int m=grid.size(); int n=grid[0].size(); if(i<0||j=m||j>=n) return false; return true; } int numIslands(vector<vector>& grid) { int m=grid.size(); int n=grid[0].size(); int ans=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(grid[i][j]==\'1\'){//b ans++; dfs(grid,i,j); } } } return ans; }};2 课程表 207 搜索（拓扑排序）
拓扑排序的过程，其实就两步：
- 找到入度为0 的节点，加入结果集
- 将该节点从图中移除
循环以上两步，直到 所有节点都在图中被移除了。
结果集的顺序，就是我们想要的拓扑排序顺序
入度为0的课程可以学。
class Solution {public: bool canFinish(int numCourses, vector<vector>& prerequisites) { vector indegree(numCourses);//记录每个课程的入度（它的前置课程数） unordered_map<int,vector> mp; //课程号-它的后置课程集合 //构造indegree和mp： for(int i=0;i<prerequisites.size();i++){ indegree[prerequisites[i][0]]++; mp[prerequisites[i][1]].push_back(prerequisites[i][0]); } queue q;//存放入度为0的课程号 //构造q： for(int i=0;i<numCourses;i++){ if(indegree[i]==0){ q.push(i); } } int count=0; while(!q.empty()){ //入度为0的课程出队，从图中去掉 int x=q.front(); q.pop(); count++; //x从图中去掉，那么x的后置课程入度要减1： for(int i=0;i0){ indegree[num]--; if(indegree[num]==0){ q.push(num); } } } } if(count==numCourses) return true; return false; }};3 除法求值 399 搜索（图，dfs）
那么我们求解 a / c 相当于计算从节点 a 到 节点 c 的路径的权重乘积。
class Solution {public: vector ans; unordered_map<string,vector<pair>> graph; unordered_map visited; bool found; void dfs(string start,string end,double path){ //path是一路走来的乘积和 if(found){ return; } if(start==end){ found=true; ans.push_back(path); return; } // 枚举该节点的所有邻节点： for(pair neighbor:graph[start]){ string node=neighbor.first; double weight=neighbor.second; if(visited[node]==0){ visited[node]=1; dfs(node,end,path*weight);//递归处理邻节点 visited[node]=0; } } } vector calcEquation(vector<vector>& equations, vector& values, vector<vector>& queries) { //构造双向图： for(int i=0;i<equations.size();i++){ graph[equations[i][0]].push_back(make_pair(equations[i][1],values[i])); graph[equations[i][1]].push_back(make_pair(equations[i][0],1.0/values[i])); } // 对于每个query，寻找从起点start到终点end的最短路径，并计算权重积 for(int i=0;i<queries.size();i++){ if(graph.count(queries[i][0])==0){//没有这个字母 ans.push_back(-1.0); continue; } found=false; dfs(queries[i][0],queries[i][1],1); if(found==false){ ans.push_back(-1.0); } } return ans; }};
