手写代码问题
Integer
contains
Character
toCharArray
Stack
Queue
LinkedList<>
双端队列
Deque
优先队列
PriorityQueue
Character.isLetterOrDigit
Character.toLowerCase(
equals
compareTo
回溯算法解题套路框架
def backtrack(…):
for 选择 in 选择列表:
做选择
backtrack(…)
撤销选择
动态规划
dp[0][0][…] = base
进行状态转移
for 状态1 in 状态1的所有取值：
for 状态2 in 状态2的所有取值：
for …
dp[状态1][状态2][…] = 求最值(选择1，选择2…)
二分查找
int binary_search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if(nums[mid] == target) {
// 直接返回
return mid;
}
}
// 直接返回
return -1;
}
二叉树的广度优先
class Solution {
Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
Set
public void dfs(TreeNode root) {
if (root.left != null) {
parent.put(root.left.val, root);
dfs(root.left);
}
if (root.right != null) {
parent.put(root.right.val, root);
dfs(root.right);
}
}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
dfs(root);
while (p != null) {
visited.add(p.val);
p = parent.get(p.val);
}
while (q != null) {
if (visited.contains(q.val)) {
return q;
}
q = parent.get(q.val);
}
return null;
}
}
二叉树的深度优先
public class Solution {
public ArrayList
ArrayList
if(root==null)
return lists;
Stack
stack.push(root);
while(!stack.isEmpty()){
TreeNode tree=stack.pop();
//先往栈中压入右节点，再压左节点，这样出栈就是先左节点后右节点了。
if(tree.right!=null)
stack.push(tree.right);
if(tree.left!=null)
stack.push(tree.left);
lists.add(tree.val);
}
return lists;
}
}
HashMap
数组中重复的数字
线性遍历集合存储，然后看集合中是否存在
数组中出现次数超过一半的数字 ：哈希、排序、摩尔投票法
第一个只出现一次的字符 ：哈希表 的使用
两个数组的交集
复制带随机指针的链表
判断链表中是否有环
找树中两个指定节点的最近公共祖先
找出最长连续序列的长度：通过将数组中的数字放入set中，然后遍历数组，查找set中是否有连续的序列
四数相加（HashMap存一组，另一组和HashMap进行比对）
最长不含重复字符的子字符串
二叉树
1.二叉树的遍历 （前中后、层序遍历）
非递归遍历要用栈来实现
二叉树的广度优先搜索 （同一层用队列存储）
二叉树的深度优先搜索 （就是前中后遍历）
判断是不是二叉树的子结构，就是判断 、根、左、右，都相同
二叉树的镜像，本质就是遍历交换，同翻转二叉树
对称二叉树，就是在递归的时候判断左右根节点是不是相同
从上到下打印二叉树：就是把节点放到队列里，然后遍历队列打印
之子型打印就是判断队列里面数量基数还是偶数
二叉树和为某一值的路径：就是递归判断是不是减到0了且左右节点都是null了就是路径
二叉搜索树一定是中序遍历，跟链表组合考察，二叉搜索树的排序，就是中序遍历
序列化二叉树，反序列化二叉树
二叉树的深度，递归左右节点，最大值加1
二叉搜索树树的最近公共祖先：hashMap、递归祖先的左右节点
建立最小高度树，通过2分形式递归创建左右子树节点
合法二叉搜索树，判断左 右 根节点的大小关系
二叉树中最大路径和：递归左右节点，然后加起来最大的值
合并二叉树：递归合并值
重建二叉搜索树：
树的子结构 ：先序遍历树 A 中的每个节点 n，判断树 A 中 以 n 为根节点的子树 是否包含树 B
二叉搜索树的第k大节点 ：中序遍历，从小到大
平衡二叉树：任意节点的左右子树的深度相差不超过1，后序遍历 + 剪枝，或者从上到下，判断深度是否大于1
二叉树的最近公共祖先：后序遍历
链表
必须使用被用指针指向源链表再递归
链表和栈组合使用
从尾到头打印链表：采用栈后入先出的特点进行打印
链表翻转：分别交换指针和值
删除节点：指向next的next
链表中倒数第k个元素：双指针，当快指针到达终点时，慢指针所在的就是k的元素
合并两个排序的链表：判断值，创建新的链表时先创建一个值为0的链表，返回这个链表的next
两个链表的第一个公共链表。跑马场套圈的原理，当a=null时把b赋给a直到a=b
复杂链表的复制：采用hashmap存储节点，然后再遍历复制random
链表相交：跑马场
环形链表：hashMap判断，双指针两倍的速度判断
回文链表：两倍速度找到中间，然后翻转另一半
旋转链表：先闭合链表，然后旋转后再开环
排序链表：归并排序，分割链表，然后再合并
奇偶链表：将奇节点放在一个链表里，偶链表放在另一个链表里。然后把偶链表接在奇链表的尾部。
链表的中间节点：快慢指针
排序链表：分割 cut 环节： 找到当前链表中点，并从中点将链表断开（以便在下次递归 cut 时，链表片段拥有正确边界）；合并 merge 环节： 将两个排序链表合并，转化为一个排序链表
栈
一般会用到辅助栈
用辅助栈来确定最大最小值（辅助栈是一个递增递减的序列）保证pop后也能完整
用栈来实现队列：辅助栈来翻转
栈的压入和弹出序列先遍历，先push再判断是欧能够弹出至空
队列实现栈：双队列
汉诺塔：三个交换
实现一个基本的计算器：先把乘除法的值计算出来，最终将所有的运算简化成只有加法，将表达式转为后缀
队列
栈实现队列：两个队列，删除时候将两个队列顺序进行交换
数据流的中位数：优先队列（大小堆）返回堆顶的平均数
滑动窗口最大值：双端队列，控制删除，那么为了维持从大到小的原则，我必须让尾部元素弹出
队列最大值：定义max队列，递增的队列
二分查找
寻找峰值：如果小了就是峰值，否则是最后一个元素
二分左右区间写法
在排序数组中查找数字 I
0-n中缺失的数字：二分
旋转数组的最小数字
在排序数组中查找数字
插入排序
归并排序
快速排序
最大最小k个数：大顶椎、小顶椎，优先排序
数据流中的中位数 ：大顶椎、小顶椎，优先排序
字符串
字母异位词 排序或者通过数组存储减a后的数字，通过加减平衡
是否可以被拆分：集合存储拆分后的数据，遍历，然后判断
第一个不重复的字符串，通过HashMap，存储key和出现次数
字符串翻转：转成char数组，翻转数组
回文串验证：双指针
左旋转字符串：字符串切割拼接
翻转单词顺序：按空格分割字符串，然后倒序输出
最长不含重复字串：双指针+hash
把数字翻译成字符串：
替换空格：3倍字符char数组
字符串的排列方式：深度优先+交换
字符串转整数：线性判断情况
数据压缩：StringBuilder 线性
无重复子串最大长度：hash指针移动
最大上升子序列：额外创建数组存放字符串到当前位置最大值
正则表达式匹配：线性遍历，分成空正则和非空正则两种
表示数值的字符串 ：用hashmap存储9中状态的情况，然后遍历
逆波兰表达式是一种后缀表达式
数组
旋转数组：一个石另外开辟数组进行复制，另一个是多次旋转数组
调整数字顺序使奇数位于偶数前面：双指针，遇到奇数++，遇到偶数–，然后交换
数组中出现次数超过一半的数字 ：哈希，排序，摩尔投票法
连续子数组的最大和 ：动态规划，变成线性，然后求最大值
1～n整数中1出现的次数：进制判读，迭代
数字序列中某一位的数字：与上面相似
排序数组和为s的两个数字：双指针
数组交集：hash，排序
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集
波兰逆序表达式：数组栈使用
除自身以外数组的乘积：生成左右乘积列表
和为s的连续正数序列：滑动窗口，左右边界移动
滑动窗口的最大值 ：最小堆队列，每次替换
将数组中所有 0 移动到数组末尾：空间优化，第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]，所以第二次遍历把末尾的元素都赋为0即可
递增二维数组中的查找 ：双指针，定位到二维数组的右上角，然后横向竖向的判断大小，进行加加或者减减
顺时针打印矩阵：定义4个顶点的坐标位置left、right、top、bottom，到达边界时停止转换方向，遍历完毕后，四个顶点位置进行内缩
数组中的逆序对 ：递归、二分查找不断缩小左右边界，直至left = right
寻找峰值：线性扫描、递归二分查找、
找出最长连续序列的长度：方法一：哈希表、方法一：动态规划 + 滚动数组
异或数字进制
二进制中1的个数 n &= n - 1;
1～n整数中1出现的次数 ：10的计算
数字序列中某一位的数字 ： 迭代 + 求整 / 求余
把数组排成最小的数 ：本质上是一个排序问题，自定义排序，快排思想不占用空间
把数字翻译成字符串 ：本质上是25进制，可以把这两位连起来翻译
丑数：只包含质因子 2、3 和 5 的数称作丑数，算dp
数组中数字出现的次数：分组异或
圆圈中最后剩下的数字 ：约瑟夫环问题：总结一下反推的过程，就是 (当前index + m) % 上一轮剩余数字的个数。
求1+2+…+n ：return n == 0 ? 0 : n + sumNums(n - 1);
不用加减乘除做加法 int c = (a & b) << 1; // c = 进位 a ^= b; // a = 非进位和
构建乘积数组 b[i] = b[i - 1] * a[i - 1];
把字符串转换成整数 ： 三种情况，即 ‘+’−’’ , ‘’无符号” ；新建一个变量保存符号位，返回前判断正负即可。
四数相加：采用分为两组，HashMap存一组，另一组和HashMap进行比对。
颠倒给定的 32 位无符号整数的二进制位：解法1 取模求和、解法2 按位翻转、解法3:分治合并
动态规划
斐波那契数列：递归和动态规划
青蛙跳台阶问题 ：同斐波那契数列
剪绳子 ：最优3等分，次优，剩下个2。最差，剩下个1
深度优先搜索
矩阵中的路径 （不能回退）
广度优先搜索
机器人的运动范围 （不能碰触）
快速幂解析：分治思想（2的8次方等于 2的2次方 乘 2的2次方 乘 2的2次方 乘 2的2次方 ）
连续子数组的最大和：动态规划线性
礼物的最大价值：每次 向右 或者 向下 移动一格
最长不含重复字符的子字符串 ：动态+hash。dp 的更新
n个骰子的点数 ：找出状态转移方程，构造dp数组，一个骰子的点数概率数组显然是6个六分之一,不需要另设数组
扑克牌中的顺子5张：集合 Set + 遍历，排序，判断是否大于5
股票的最大利润 ：状态方程profit = Math.max(profit, price - cost);
凑零钱问题：不过是一个 N 叉树的遍历问题而已，其实很多动态规划问题就是在遍历一棵树，你如果对树的遍历操作烂熟于心，起码知道怎么把思路转化成代码，也知道如何提取别人解法的核心思路。
N 皇后问题：N 叉树的遍历框架
乘积最大子数组：遍历数组时计算当前最大值，不断更新
全排列问题：做选择、进入下一层决策树、取消选择