树
- 7.重建二叉树
- 26.判断是不是树的子结构
- 27.二叉树的镜像
- 28.对称的二叉树
- 32-1.从上到下打印二叉树—层序遍历
- 33.二叉搜索树的后序遍历序列
- 34.二叉树中和为某一值的路径（回溯）
- 37.序列化二叉树
- 54.二叉搜索树的第k大节点(利用中序遍历)
- 55-1.二叉树的深度（最大高度）
- 55-2.判断是否平衡二叉树（仅高度）
- 55-拓展.二叉树路径和是否为Sum
- 55-拓展2.求二叉树的最大直径
- 68-1.二叉搜索树的最近公共祖先
- 68-2.二叉树的最近公共祖先
链表
- 22.链表中倒数第k个节点（快先走）
- 35.复杂链表的复制（深拷贝）
- 52.两个链表的第一个公共节点
二分法
- 11.旋转数组的最小数字
- 53-1.在排序数组中查找数字出现次数
- 53-2.0～n-1中缺失的数字
滑动窗口
- 48.最长不含重复字符的子字符串
- 57-1.和为s的两个数字
- 57-2.和为s的连续正数序列
dfs深度遍历
- 12.矩阵中的路径，满足 bfce 的路径
- 16.数值的整数次方pow
bfs广度遍历
- 13.机器人的运动范围
DP动态规划
- 10.斐波那契数列 / 青蛙跳
- 42.连续子数组的最大和（经典）
- 46.把数字翻译成字符串（规律+DP / 0对应a）
- 47.礼物的最大价值
- 60.n个骰子的点数的概率
STL容器
- 6.从头到尾打印链表（deque）
- 9.用两个栈实现队列（stack）
- 30.包含min函数的栈（stack）
- 31.栈的压入、弹出序列（stack）
- 41.数据流中的中位数（优先队列priority_queue/大小顶堆）
- 59-1.滑动窗口的最大值（deque）
- 59-2.队列的最大值（deque）
回溯法
- 12.矩阵中的路径，满足string = bfce的路
- 34.二叉树中和为某一值的路径
- 38.字符串排列的所以可能性（难点在于剪枝）
位运算
- 15.二进制中1的个数
- 56-1.数组中数字出现的次数(异或)
快慢指针
- 22.链表中倒数第k个节点 / 快先走
归并算法
- 51.数组中的逆序对
01 - 25
3.数组中重复的数字
题目：数组长度n，元素大小0—n-1，查找重复元素
交换对应元素至下标（最优解）
4.二维顺序数组的查找
题目：行有序、列有序，查找数组中元素
右上角开始查找，类似二分查找row++，col–。
5.替换空格
题目：s = “We are happy.”——》”We%20are%20happy.”
s.replace(i, 1,”%20”);
replace(start, len , string change);
上题目只替换len=1长度元素
6.从头到尾打印链表
方法1.利用vector—vector
vis(deq.rbegin(),deq.rend()) 方法2.利用deque
头：push_front() pop_front()/ 【1、2、3】尾：push_back() -pop_back()
双向队列经典问题：维护数组最大值：头MAX，尾进然后比较
7.重建二叉树
方法：前序定根，中序定区间
return build(preorder,inorder,0, 0,inorder.size()-1);
对应：先序数组、中序数组、root节点，begin，end;
9.用两个栈实现队列
方法：利用辅助栈
通过一个栈来换一下手
10-1.斐波那契数列
方法1.dp方程
方法2.a = a + b；b = a - b；//b用来保存前值
10-2 .青蛙跳台阶问题
方法1.dp方程
方法2.a = a + b；b = a - b；//b用来保存前值
11.旋转数组的最小数字
有序数组部分颠倒，就是找到最小的那个数
典型的：二分查找
二分的关键：mid区间的取值判断
12.矩阵中的路径BFCE
每个节点都需要尝试，典型的回溯问题，再加上DFS深度遍历
13.机器人的运动范围
典型BFS广度遍历的题目
auto [x, y] = Q.front();
14-1.剪绳子
方法1.找规律,以3划分的乘积是最大的
方法2.DP动态规划,dp[1] = 1;dp[2] = 2;dp[3] = 3;dp[4] = 4;
15.二进制中1的个数
位运算
16.数值的整数次方
dfs——拆分拆分 / 化繁为简
17.String的大数打印
String大数问题，用字符串模拟数字
18.删除链表的节点
原题剑指1：给定头节点和要删除的节点（快速删除） / 删除要删除节点的下一个节点，将删除节点的值赋给前一个结点。
原题剑指2：删除链表中的重复节点 / 使用两个辅助指针实现
19.正则表达式匹配（困难未做）
20.表示数值的字符串（中等未做）
21.调整数组顺序使奇数位于偶数前面
一次快排、快排需要注意：while右边先写
22.链表中倒数第k个节点
方法1.vector保存所有结点
方法2.快慢指针，快指针先走K，然后慢指针开始走，sum - k = 要走的步数
24.反转链表
方法1.辅助指针
方法2.dfs递归遍历到最后一个节点开始反转
25.合并两个排序的链表
类似归并排序，归的时候，逐步组成一个有序集合，双指针
26 - 47
26.判断是不是树的子结构
1.首先：每个节点都有可能是树的子结构，所以需要遍历树的左子树，右子树，所以是 ||
- 主函数：return dfs(father,son) || isSubStructure(father->left,son) || isSubStructure(father->right,son);
2.然后：当单个节点满足，是要延顺下去的每个节点满足,所以是&&
- DFS函数：return dfs(father->left,son->left) && dfs(father->right,son->right);
27.二叉树的镜像
方法一DFS：直接进行节点交换，然后再次遍历左右节点
方法二层序遍历：利用queue
- 需要注意 if(tmp->left) q.push(tmp->left);
- 需要注意 if(tmp->right) q.push(tmp->right);
28.对称的二叉树
首先：空树为真，左等于右为真
然后：
- 两空树：真，一空一不空树：假，值不相等：假
- 需要判断的是左子树的左和右子树的右是否相等
- 需要判断的是左子树的右和右子树的左是否相等
29.顺时针打印矩阵
边界判断：上下左右，逐渐缩小范围
30.包含min函数的栈
空间换时间，入栈两个
31.栈的压入、弹出序列
利用辅助栈，当辅助栈内的数据 = pop数组的数据需要弹出。
32-1.从上到下打印二叉树
利用队列的层序遍历
关键点：
- int size = q.size() 然后for(int i =0;i<size;i++)
- if(q->left)加入；if(q->right)加入
初始化可以vector(arr.rbegin().arr.rend());
33.二叉搜索树的后序遍历序列
二叉搜索树：左 < 中 < 右
后序遍历：左 右 中
- 输入：后序遍历数组，left，root
- 所以找到：后序遍历：左 index 右的区分下标，满足右>root值。这个区间满足
- 再次检查别的区间：后序遍历数组 的左、右子树是否满足
- return dfs(postorder,left,i-1)&&dfs(postorder,i,root-1);
34.二叉树中和为某一值的路径
首先：需要遍历到最后一个节点为NULL，才符合条件
- root == NULL的情况下才会返回
- root == sum && root->left==NULL && root->right==NULL才满足条件
35.复杂链表的复制
1.复制原指针A -> B -> C 变 A -> A’-> B -> B’-> C-> C’
2.改变random指针指向，上一步复制的节点包含了random节点
3.断开链表，同时复原
36.二叉搜索树与双向链表
二叉搜索树——左中右形式存储——利用中序将节点截取下来
37.序列化二叉树(层序困难)
利用getline截取数值
前序、中序、后续、层序都是可以的。对应的反序列化即可。
38.字符串排列的所以可能性
回溯法 + 剪枝
- 1.先排序，便于找到重复的元素位置
- 2.做出选择：char —> #，撤销选择： # —> char
- 3.关键的剪纸操作难点在于：
- if (s[i] == ‘#’ || (i > 0 && s[i] == s[i - 1])) continue;
39.数组中出现次数超过一半的数字
摩尔投票法——极限一换一
40.最小的K个数
各种排序
41.数据流中的中位数
优先队列：元素经过队列过一次手，大根堆存小的一半数，小根堆存大的一半数
- priority_queue<int, vector
, std::less > maxStack; - priority_queue<int, vector
, std::greater > minStack;
- priority_queue<int, vector
42.连续子数组的最大和
dp动态规划 / 变负反转
贪心算法
43.1～n整数中1出现的次数
找规律，然后区分低位、高位、当前位、位因子
44.连续数字中的第N个数
找规律，范围 / 数量 / 位数 / 占位的情况，从而总结。
45.把数组中所有整数排成最小的连续数
利用sort排序，自定义sort函数，重写Compare
46.把数字翻译成字符串
DP动态方程： dp[i] = dp[i - 1] / dp[i] = dp[i - 1] + p[i - 2];
47.礼物的最大价值
典型的dp动态方程
48 - 68
48.最长不含重复字符的子字符串
经典滑动窗口
49. 丑数
丑数本身是丑数，丑数是在丑数的基础上*2 或 *3 或 *5
所以我们在三个丑数数组中选取最小的数来组成，三个变量a、b、c
50. 第一个只出现一次的字符
哈希表统计
51.数组中的逆序对
归并来做，部分的res相互叠加，计算出最后的res。
52. 两个链表的第一个公共节点
a + c + b = b + c + a程序员的浪漫
53-1. 在排序数组中查找数字出现次数
二分法！！有序一般都是二分法
53-2. 0～n-1中缺失的数字
二分法，但是最后的判断很难。找到最左边不等于下标的数。
54. 二叉搜索树的第k大节点
利用搜索二叉树的中序遍历得到顺序数组
更加优秀的，直接利用倒置的中序遍历，反向从大到小开始遍历。
55-1.二叉树的深度
dfs求取树的深度，往下+1就可以了
55-2. 判断是否平衡二叉树（仅高度）
首先：每个节点需要满足高度差要求
然后：每个节点都需要满足左右子树
55-拓展 二叉树路径和是否为Sum
首先：只要有一个到头的节点，那么就是有路径为Sum
只有：左为空，右为空，同时Sum值符合，return true。
- 如果节点为空，return false；
55-拓展2 求二叉树的最大直径
首先：不一定根节点为最大直径节点，所以每次需要比较
然后：同时每个节点的最大直径为，max（左树的左、左树的右）+ max（右树的左、右树的右）
- 所以每个节点：return max（L、R）+1
56-1. 数组中数字出现的次数
方法一：哈希表
方法二：位运算
A&(-A)：结果最低位
56-2.数组中数字出现的次数变形
方法一：哈希表
方法二：位运算
统计那个没出现N次的为，取余取不到那就是那个位置。
57-1. 和为s的两个数字
方法一：哈希表
方法二：滑动区间：left = 0；right = nums.size()；
57-2. 和为s的连续正数序列
方法一：哈希表
方法二：滑动区间
58-1. 翻转单词顺序 / stringstream
getline分割字符 / cin>>s的区别
stringstream
58-2. 左旋转字符串 / substr
substr（i，len）
i:从0开始，起始下标
59-1. 滑动窗口的最大值
利用deque维护
- 头部存储最大元素（同时也是老元素），存放的是元素的下标index，从而识别出是否超出窗口范围
- 元素从尾部进入，逐一比较，然后删除
- 然后装入queue，再次判断转入res
59-2. 队列的最大值
利用deque维护
60. n个骰子的点数
DP动态规划
61. 扑克牌中的顺子
顺序比较
62. 圆圈中最后剩下的数字 / 约瑟夫环问题
约瑟夫环问题，f（m，n）=【f（m - 1，n）+ n】 % m
63. 股票的最大利润
dp动态规划
记录之前的最小价格即可
64. 求1+2+…+n / 利用sizeof
利用sizeof
65. 不用加减乘除做加法
位运算，&进位和^非进位
- while(b){
- int temp = (unsigned int)(a & b) << 1; //c:进位和————双1才1
- a ^= b; //a:非进位和——单1才1
- b = temp; //b = 进位
- }
- return a;
66. 构建乘积数组 / 左乘、然后再右乘
先左乘，再右乘O（n）
67. 把字符串转换成整数 / isdigit( char )函数
利用函数isdigit（）
68-1. 二叉搜索树的最近公共祖先
利用二叉搜索树的特性：左 < 中 < 右
p、q都小于找右
p、q都大于找左
否则就是正好
68-2.二叉树的最近公共祖先
首先：每个节点都有可能是祖先，依次往下遍历找到相对应的节点
当L && R都有值的时候，返回root。