算法
1. 链表
1.1. 问题分类
1.2. 常见func
2. 树
2.1. 二叉树
2.1.1. 树的遍历
2.1.2. Morris遍历
2.1.3. 递归思想
2.1.4. 构造及修改二叉树问题
2.1.5. 公共祖先问题
2.2. 二叉搜索树
2.3. 红黑二叉查找树
2.4. 高频算法
2.4.1. 树的遍历
2.4.2. 树的属性
2.4.3. 子树问题
2.4.4. 树的高度
2.4.5. 树的构建与修改
2.4.6. 树的基本操作
2.4.7. 公共祖先问题
3. 哈希表
4. 数组与字符串
4.1. 数组
4.2. 字符串
5. 双指针
5.1. 快慢指针
5.2. 二分法
5.2.1. 代码模版
5.2.1.1. 常见模版
5.2.1.2. 左边界问题
5.2.1.3. 右边界问题
5.2.2. 经典问题
5.3. 左右指针
5.4. 滑动窗口
5.4.1. 指针移动缩小窗口
5.4.2. 指针不动窗口平滑
6. 队列
6.1. 相关算法
6.2. 单调队列
7. 栈
7.1. 相关算法
7.2. 单调栈
8. 图
8.1. DFS
8.2. BFS
8.3. DSF与BSF相关算法
8.4. 拓扑排序
9. 递归
9.1. 递归三要素
9.2. 递归的思想
10. 回溯
10.1. 伪代码模版
10.1.1. 回溯三部曲
10.1.2. startIndex使用
10.2. 问题场景
10.3. 重复问题
10.4. 组合问题
10.5. 切割问题
10.6. 排列问题
10.7. 子集问题
10.8. 去重问题横向对比
10.9. 其他
11. 贪心
11.1. 指针与区间局部最优
11.2. 区间问题
11.3. 其他
12. 动态规划
12.1. 基本思想
12.2. 相关问题
12.3. 字符串问题
12.3.1. 字符操作
12.3.2. 子序列问题
12.3.3. 子数组问题
12.3.4. 回文问题
12.4. 股票问题
12.5. 背包问题
12.5.1. 常见求解方式及疑难点
12.5.2. 典型背包问题
12.5.3. 背包场景问题
12.6. 扔鸡蛋问题
13. 前缀树
14. 并查集
15. 二进制
16. KMP
17. 其他
17.1. 前缀和
17.2. 素数
17.3. 求余数常见操作
17.4. Kanade 算法
17.5. 约瑟夫环问题
17.6. 拒绝采样
17.7. 字典序
17.8. 超精度的判断
大O表示法：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。面试中说道算法的时间复杂度是多少指的都是一般情况。
链表双指针：
虚拟节点：
经典问题：
- 剑指 Offer 24. 反转链表 :栈、头插法、递归
- 合并两有序链表
- 回文链表
- 合并K个升序链表
反转链表:
public class Solution {
/**
* 反转链表递归写法
* @param head
* @return
*/
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode res = reverseList(head.next);
head.next.next = head;
head.next = null;
return res;
}
/**
* 反转链表迭代归写法
* @param head
* @return
*/
public ListNode reverseList1(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode prefixHead = new ListNode(-1);
while(head !=null) {
ListNode next = head.next;
head.next = prefixHead.next;
prefixHead.next = head;
head = next;
}
return prefixHead.next;
}
}双指针
class Solution {
/**
* 查找链表中点
* @param head
* @return
*/
public ListNode findMid(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode fast = head.next;
ListNode slow = head;
while(fast != null && fast.next !=null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
/**
* 查找倒数第N个节点
* @param head
* @param n
* @return
*/
public ListNode findLastN(ListNode head, int n) {
ListNode fast = head;
while(fast != null && n >0) {
fast = fast.next;
n--;
}
if (fast == null) {
return null;
}
ListNode slow = head;
while(fast !=null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}前中后序遍历递归与迭代写法
public class Solution {
//前序遍历 迭代写法
public List<Integer> preorderTraversal1(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
//每次获得第一个元素，理解成 栈的pop就行。
TreeNode node = stack.pollLast();
output.add(node.val);
// 由于栈的属性 右节点先入栈
if (node.right != null) {
stack.add(node.right);
}
if (node.left != null) {
stack.add(node.left);
}
}
return output;
}
/**
* 基于迭代的中序遍历
* 1. 根据根节点把所有的左节点全部入栈，
* 2. 出栈后的节点均为左节点，因此中序的下一个节点为右节点的左节点，继续找右节点的左节点入栈
* @param root
* @return
*/
public List<Integer> inorderTraversal2(TreeNode root) {
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode curr = root;
while (curr != null || !stack.isEmpty()) {
while (curr != null) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
res.add(curr.val);
curr = curr.right;
}
return res;
}
// 后序遍历
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> stack = new LinkedList<>();
LinkedList<Integer> output = new LinkedList<>();
if (root == null) {
return output;
}
stack.add(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pollLast();
// 关键点 每次添加都添加到输出的第一个
output.addFirst(node.val);
// 关键点2 左节点先入栈
if (node.left != null) {
stack.add(node.left);
}
if (node.right != null) {
stack.add(node.right);
}
}
return output;
}
}Morris 遍历算法是遍历二叉树的方法，它能将非递归的中序遍历空间复杂度降为O(1)。
中序遍历
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> result = new LinkedList<>();
// 定义访问指针
TreeNode pos = root;
TreeNode rightMost;
while (pos != null) {
if (pos.left != null) {
rightMost = pos.left;
while (rightMost.right != null && rightMost.right != pos) {
rightMost = rightMost.right;
}
if (rightMost.right == null) {
// 建立rightMost与pos的线索连接
// 继续递归子节点，建立线索
rightMost.right = pos;
pos = pos.left;
} else {
// rightMost已经被访问，断开线索连接
// 访问线索节点pos
// 左子树均被访问，指针指向右侧节点
rightMost.right = null;
result.add(pos.val);
pos = pos.right;
}
} else {
// 如果没有左孩子，则直接访问节点，并将指针指向右节点
// 情况1：节点无建立线索，指针指向右节点
// 情况2：节点已建立线索，指针指向线索节点
result.add(pos.val);
pos = pos.right;
}
}
return result;
}
}先序遍历
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new LinkedList<>();
if (root == null) {
return result;
}
TreeNode pos = root;
TreeNode rightMost;
while (pos != null) {
if (pos.left != null) {
rightMost = pos.left;
while (rightMost.right != null && rightMost.right != pos) {
rightMost = rightMost.right;
}
if (rightMost.right == null) {
// 此处先访问节点
result.add(pos.val);
rightMost.right = pos;
pos = pos.left;
} else {
rightMost.right = null;
pos = pos.right;
}
} else {
result.add(0, pos.val);
pos = pos.right;
}
}
return result;
}
}把二叉搜索树转换为累加树 - Morris遍历
将中序遍历过程直接反过来变成，右-中-左
class Solution {
public TreeNode convertBST(TreeNode root) {
if (root == null) {
return root;
}
TreeNode pos = root;
TreeNode leftMost;
int perSum = 0;
while (pos != null) {
if (pos.right != null) {
leftMost = pos.right;
while (leftMost.left != null && leftMost.left != pos) {
leftMost = leftMost.left;
}
if (leftMost.left == null) {
leftMost.left = pos;
pos = pos.right;
} else {
// 节点访问操作
perSum += pos.val;
pos.val = perSum;
leftMost.left = null;
pos = pos.left;
}
} else {
// 节点访问操作
perSum += pos.val;
pos.val = perSum;
pos = pos.left;
}
}
return root;
}
}以二叉树深度为例： 二叉树的深度
public class Solution {
// 自顶而下 通过全局变量传递值、或者方法返回值
private int answer;
private void maximum_depth(TreeNode root, int depth) {
if (root == null) {
return;
}
if (root.left == null && root.right == null) {
answer = Math.max(answer, depth);
}
maximum_depth(root.left, depth + 1);
maximum_depth(root.right, depth + 1);
}
// 自底而上
private int maximum_depth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return 1 + Math.max(maximum_depth(root.left), maximum_depth(root.right));
}
}涉及到⼆叉树的构造，⽆论普通⼆叉树还是⼆叉搜索树⼀定前序，都是先构造中节点。
理解TreeNode作为返回值的递归方法的含义，问题可以拆解成小问题到下层递归中。
常用的修改二叉树递归代码模版：
public class Solution {
public TreeNode solution(TreeNode node) {
if (root == null) {
return null;
}
// .... 修改逻辑，修改的子节点返回
root.left = solution(node.left);
root.right = solution(node.right);
// 第一层程序循环,会返回根结点
return root;
}
}常用的构造二叉树模版：
public class Solution {
public TreeNode solution(int[] nums, int left, int right) {
if (left > right) {
return null;
}
TreeNode node = new TreeNode(); // 构建符合节点
// 子节点构造
node.left = solution(nums, xx, xx);
node.right = solution(nums, xx, xx);
// 返回构造节点
return node;
}
}
相关问题：
层序遍历构建二叉树思路： 根节点区分两个区间，获取中序左区间内的Set。遍历层序数组，第一个节点即为根节点。
ori:
in[] = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};
20
/ \
/ \
{4,8,10,12,14} {22}
next:
In[] = {4, 8, 10, 12, 14}
level[] = {8, 4, 12, 10, 14}
公共祖先问题，如何判断一个节点是公共祖先，如果该节点的左子树及右子树均找到要寻找的节点，那么该节点为公共祖先。
二叉树的最近公共祖先
二叉搜索树相关问题核心思想：
- 中序遍历（利用其二叉搜索树的结构）
- 递归利用二叉搜索树属性进行处理。
二叉搜索树的树结构修改：
删除二叉搜索树中的节点
- 如果目标节点没有子节点，我们可以直接移除该目标节点。
- 如果目标节只有一个子节点，我们可以用其子节点作为替换。
- 如果目标节点有两个子节点，我们需要用其中序后继节点或者前驱节点来替换，再删除该目标节点。
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) root.left = deleteNode(root.left, key);
else if (root.val < key) root.right = deleteNode(root.right, key);
else {
if (root.left == null && root.right == null) {
root = null;
} else if (root.right != null) {
root.val = successor(root);
root.right = deleteNode(root.right, root.val);
} else {
root.val = predecessor(root);
root.left = deleteNode(root.left, root.val);
}
}
return root;
}
private int successor(TreeNode root) {
root = root.right;
while (root.left != null) root = root.left;
return root.val;
}
private int predecessor(TreeNode root) {
root = root.left;
while (root.right != null) root = root.right;
return root.val;
}
}二叉搜索树的最近公共祖先(与树的公共祖先有区别) ：使用了二叉搜索树的特点
二叉搜索树的最近公共祖先
二叉搜索树构建： 将有序数组转换为二叉搜索树
红黑二叉查找树背后的思想是用标准的二叉查找树和一些二外的信息来表示2-3树。
2-3树需要维护两种不同类型的节点，将被查询的键和节点中的每个键进行比较，还有链接复制、节点类型转换等工作，实现需要大量的代码，所产生的额外开销可能比标准的二叉查找树更慢
红黑树另一种等价定义是满足以下条件的二叉查找树：
- 红链接均为左链接
- 没有一个节点同时和两个红链接项链
- 该树是完全黑色平衡的，即任意空链接到根节点的路径上的黑色链接数量相同。 满足这样定义的红黑树和相应的2-3树是一一对应的。
红黑树可以保证最坏情况下的性能，且它能够支持的操作更多(如排名、选择、排序和范围查找)。根据经验法则，第一选择通常是hash表(散列表)，其他因素更重要的时候，才会选择红黑树。
二叉搜索树：
完全二叉树：
子树问题，为了避免重复的遍历判断是否同一子数可以使用序列化的方式解决
二叉搜索树：
哈希表的关键思想是使用哈希函数将键映射到存储桶。
哈希接口判断元素存在：
使用哈希映射的场景：
- 同构字符串
- 存在重复元素
- 剑指 Offer 50. 第一个只出现一次的字符
- 寻找重复的子树 : 树与Hash表结合
利用哈希表O(1)特性查找：
数组问题常见的解题关键字: 指针、搜索、hash表
公共前缀问题
- 最长公共前缀 : 分治法、二分法
回文问题（包含子串与子序列问题）
- 判断链表有环
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
}- 查找环形链表起点
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
ListNode p1 = head;
while (p1 != fast) {
p1 = p1.next;
fast = fast.next;
}
return p1;
}
}
return null;
}
}- 寻找链表的中点
public class Solution {
public ListNode findMid(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}// slow 就在中间位置 return slow;
return slow;
}
}相关问题：
- 移除元素 : 类似于快排的变种
- 移动零
- 删除链表的倒数第 N 个结点
- 下一个排列: 查找的方法比较巧妙，递减区间的利用
- 下一个更大元素 III: 与上述类似
- 删除有序数组中的重复项 II: 快慢指针，慢指针为确定的区间
「⼆分」的本质是⼆段性，并⾮单调性。只要⼀段满⾜某个性质，另外⼀段不满⾜某个性质，就可以⽤「⼆分」
public class Solution {
/**
* 闭区间
* int left = 0, right = nums.length - 1; 且 left <= right
* 通用的二分法模板
*
* @param nums
* @param target
* @return
*/
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
/**
* 开区间变形
* int left = 0, right = nums.length; 且 left < right
*
* @param nums
* @param target
* @return
*/
public int search2(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int left = 0, right = nums.length;
while (left < right) {
int mid = (left + right) >>> 1;
if (nums[mid] == target) return mid;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
return -1;
}
}public class BinarySearchLeft {
/**
* left <= right 且 int left = 0, right = nums.length - 1;
* 寻找第一个等于或大于的target左边界
*
* {1,2,2,3,4,5,5,7} 寻找0(左越界) -> left: 0 第一个大于的数 result:-1
* {1,2,2,3,4,5,5,7} 寻找2(存在) -> left: 1 第一个相等 result:1
* {1,2,2,3,4,5,5,7} 寻找8(右越界) -> left: 8 越界 result:-1
* {1,2,2,3,4,5,5,7} 寻找6(范围内但值不存在) -> left: 7 第一个大于的数 result:-1
*
* <p>
*
* @param nums
* @param target
* @return
*/
public static int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1; // 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) { // 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
System.out.print("left ->" + left + " ");
/**
* 出界检查: 若搜索区间无目标元素 会出现越界情况 如{1,2,2,4,4,5,5,7} target:8
* 使用left判断的原因： 若存在目标元素往左收缩，最后跳出循坏的结果肯定是：{x, x, right, left, x, x}
*/
if (left != nums.length && nums[left] == target) {
return left;
}
return -1;
}
/**
* 查找第一个等于或者小于key的元素
*
* {1,2,2,3,4,5,5,7} 寻找0(左越界) -> right: -1 越界 result:-1
* {1,2,2,3,4,5,5,7} 寻找2(存在) -> right: 0 第一个小于 result:0
* {1,2,2,3,4,5,5,7} 寻找8(右越界) -> right: 7 第一个小于 result:7
* {1,2,2,3,4,5,5,7} 寻找6(范围内但值不存在) -> right: 6 第一个小于 result:6
*
* @param nums
* @param target
* @return
*/
public static int findFirstSmaller(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
System.out.print("right ->" + right + " ");
if (right < 0) {
return -1;
}
return right;
}
}public class BinarySearchRight {
/**
* left <= right 且 int left = 0, right = nums.length - 1;
* 寻找等于或小于 的target右边界的二分
* 注意：结果左侧越界
*
* <p>
* {1,2,2,3,4,5,5,7} 寻找0(左越界) -> right: -1 越界 result:-1
* {1,2,2,3,4,5,5,7} 寻找2(存在) -> right: 2 最后一个相等 result:2
* {1,2,2,3,4,5,5,7} 寻找8(右越界) -> right: 7 第一个小于 result:7
* {1,2,2,3,4,5,5,7} 寻找6(范围内但值不存在) -> right: 6 第一个小于 result:8
*
* <p>
*
* @param nums
* @param target
* @return
*/
public static int right_bound(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) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
System.out.print("right ->" + right + " ");
// 为啥用right判断? 若存在重复target元素，循坏跳出的条件肯定是想右收缩过程中 left+1 导致的break
if (right < 0) {
return -1;
}
return right;
}
/**
* 查找第一个等于或大于key的元素
* 注意：结果右侧越界
*
* <p>
* {1,2,2,3,4,5,5,7} 寻找0(左越界) -> left: 0 第一个大于 result:0
* {1,2,2,3,4,5,5,7} 寻找2(存在) -> left: 3 第一个大于 result:3
* {1,2,2,3,4,5,5,7} 寻找8(右越界) -> left: 8 越界 result:-1
* {1,2,2,3,4,5,5,7} 寻找6(范围内但值不存在) -> left: 7 第一个大于 result:7
*
* @param nums
* @param target
* @return
*/
public static int findFirstLarger(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
}
}
System.out.print("left ->" + left + " ");
// 为什么用left，因为left是循环跳出的地方默认在right的右边
if (left >= nums.length) {
return -1;
}
return left;
}
}二分查找问题
- 确定target目标，如果题目无target，需自己确定。如山峰问题的
num[mid]<nums[mid+1] - 确定判断搜索区间。根据target进行查找。
-
搜索旋转排序数组: 通过左右边界确定序列是否为递增
-
有序矩阵中第 K 小的元素: 猜数字
平方根问题
非模版二分问题：
「⼆分」的本质是⼆段性，并⾮单调性。只要⼀段满⾜某个性质，另外⼀段不满⾜某个性质，就可以⽤「⼆分」
-
寻找旋转排序数组中的最小值: 以右边界为目标点，寻找左边界，与常规的边界问题不同。
-
寻找重复数: 二分区间判定，结果值获取
双指针问题
- 验证回文串
- 反转字符串
- 两数之和 II - 输入有序数组: 双指针基础问题
- 三数之和: 难点在于转换为双指针的变换
- 最接近的三数之和
- 四数之和
- 盛最多水的容器:
- 接雨水: 典型困难问题
- 颜色分类: 三路快排变种问题
- 反转单词顺序
参考资料：我写了套框架，把滑动窗口算法变成了默写题
常规算法模版：
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
/*** debug 输出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
- 无重复字符的最长子串: 快慢指针+hash表结合
- 最小覆盖子串
- 找到字符串中所有字母异位词
- 长度最小的子数组
滑动窗口的一种变种为，窗口保持在一定的size。
- 第一种为size是题目要求的，如k长的窗口最大值
- 第二种为size是当前满足的最优接。left位置不匹配，则平滑窗口。result即为
right-left
队列是典型的 FIFO 数据结构：
-
插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。
-
删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
单调队列，即单调递减或单调递增的队列。
需要使用 双向队列 ，假设队列已经有若干元素：
- 当执行入队 push_back() 时： 若入队一个比队列某些元素更大的数字 xx ，则为了保持此列表递减，需要将双向队列 尾部所有小于 xx 的元素 弹出。
- 当执行出队 pop_front() 时： 若出队的元素是最大元素，则 双向队列 需要同时 将首元素出队 ，以保持队列和双向队列的元素一致性。
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList<>();
deque = new LinkedList<>();
}
public int max_value() {
return deque.isEmpty() ? -1 : deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
// 元素入队逻辑，队尾小元素处队。新的大元素入队尾
while (!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
deque.offerLast(value);
}
public int pop_front() {
if (queue.isEmpty()) return -1;
// 元素出队逻辑，出队元素为队头则需要出队。
if (queue.peek().equals(deque.peekFirst())) {
deque.pollFirst();
}
return queue.poll();
}
}栈具有记忆的功能，由其数据的特殊性可以用来DFS搜索
单调栈：单调栈实际上就是栈，只是利⽤了⼀些巧妙的逻辑，使得每次新元素⼊栈后，栈内的元素都保持有序(单调递增或单调递减)。
单调栈相关问题tag，获取下一个、求最近最大或最小的值、下标
class Solution {
public int[] template(int[] T) {
// 单调递增栈
Deque<Integer> incStack = new LinkedList<>();
int len = T.length;
int[] res = new int[len];
// 从头到尾遍历或从尾到头遍历
for (int i = len - 1; i >= 0; i--) {
while (!incStack.isEmpty() && T[incStack.peek()] <= T[i]) {
// 判断是否对pop元素进行处理
// i为 pop元素 最近小于i的位置
incStack.pop();
}
// 当前stack.peek()元素为小于i对最近的位置，是否进行处理
incStack.push(i);
}
return res;
}
public int[] template2(int[] T) {
// 单调递增栈
Deque<Integer> descStack = new LinkedList<>();
int len = T.length;
int[] res = new int[len];
// 从头到尾遍历或从尾到头遍历
for (int i = len - 1; i >= 0; i--) {
while (!descStack.isEmpty() && T[descStack.peek()] >= T[i]) {
// 判断是否对pop元素进行处理
// i为 pop元素 最近大于的位置
descStack.pop();
}
// 当前stack.peek()元素为 大于i对最近的位置，是否进行处理
descStack.push(i);
}
return res;
}
}- 最小栈
- 每日温度
- 下一个更大元素 I: hash与单调栈结合
- 下一个更大元素 II
- 最短无序连续子数组: 单调栈类似思想
贪心 + 单调栈：满足条件的
以下三个为类似问题：
-
接雨水: 单调栈解法，递减栈，每次计算增量
-
柱状图中最大的矩形: review
-
最大矩形: 理解为主，如何转化问题，变成最大矩形计算。获取索引i的左右小于
height[i]的最高点索引 -
最多能完成排序的块: 单调栈的变形
DFS即Depth First Search，深度优先搜素算法其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。在访问一个节点时
- 将它标记成访问
- 递归的访问他的所有没有被标记的邻居节点
可以解决单点连通性、单点路径、双色问题(二分图)、检测环
深度优先搜索（DFS）是用于 在树/图中遍历/搜索 的另一种重要算法。
如树的遍历中所提到的，我们可以用 DFS 进行 前序遍历，中序遍历 和 后序遍历。在这三个遍历顺序中有一个共同的特性：除非我们到达最深的结点，否则我们永远不会回溯 。
这也是 DFS 和 BFS 之间最大的区别，BFS永远不会深入探索，除非它已经在当前层级访问了所有结点。
通常，我们使用递归实现 DFS。栈在递归中起着重要的作用。
递归遍历： 当我们递归地实现 DFS 时，似乎不需要使用任何栈。但实际上，我们使用的是由系统提供的隐式栈，也称为调用栈（Call Stack）。
public class Solution {
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(Node cur, Node target, Set<Node> visited) {
if (cur == target) {
return true;
}
for (Node each : cur.neighbor) {
if (!visited.contains(each)) {
visted.add(each);
boolean result = DFS(next, target, visited);
if (result) {
return true;
}
}
}
return false;
}
}对于图论，若使用DFS递归搜索时，在遇到数据量过大的情况。则要注意堆栈溢出的情况。因为递归使用的是系统的隐式栈.
此时就可以使用栈来模拟系统隐式栈的调用过程，避免出现堆栈溢出。
public class Solution {
/*
* Return true if there is a path from cur to target.
*/
boolean DFS(Node root, int target) {
Set<Node> visited;
Stack<Node> s;
s.push(root);
while (!s.isEmpty()) {
Node cur = s.pop();
if (cur == target) {
return true;
}
for (Node next : cur.neighbors) {
if (!visited.contains(next)) {
s.add(next);
visited.add(next);
}
}
}
return false;
}
}双色问题(二分图)
class DFSTwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColor = true;
public DFSTwoColor(Graph G) {
marked = new boolean[G.V()];
color = new boolean[G.V()];
for (int i = 0; i < G.V(); i++) {
if (!marked[i]) {
}
}
}
private void dfs(Graph G, int v) {
marked[v] = true;
for (Integer w : G.adj(v)) {
if (!marked[w]) {
color[w] = !color[v];
dfs(G, w);
} else if (color[w] == color[v]) {
// 节点已经访问过，但是颜色与连通节点颜色相同，说明不是二分图
this.isTwoColor = false;
}
}
}
}检测环:
class DFSCycle {
private boolean[] marked;
private boolean hasCycle;
public DFSCycle(Graph G) {
this.marked = new boolean[G.V()];
}
/**
* dfs 判断是否存在环
* @param G
* @param v
* @param u
*/
private void dfs(Graph G, int v, int u) {
marked[v] = true;
for (int w: G.adj(v)) {
if (!marked[w]) {
dfs(G, w, v);
} else {
if (w != u) {
this.hasCycle = true;
}
}
}
}
}BFS，其英文全称是Breadth First Search，广度优先搜索算法，使用了一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。先将起点加入队列，然后重复以下步骤直到队列为空:
- 取队列的下一个顶点并标记
- 将与v相邻的所有未被标记的顶点加入队列。
广度优先搜索（BFS）的一个常见应用是找出从根结点到目标结点的最短路径。 注意点：
树的遍历代码模版：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left != null) {
queue.add(node.left);
}
}
}
}
}图遍历代码模板：
public class Solution {
int BFS2(Node root, Node target) {
Queue<Node> queue = new LinkedList<>(); // store all nodes which are waiting to be processed
Set<Node> used = new HashSet<>(); // store all the used nodes
int step = 0; // number of steps neeeded from root to current node
// initialize
queue.add(root);
used.add(root);
// BFS
while (!queue.isEmpty()) {
step = step + 1;
// iterate the nodes which are already in the queue
int size = queue.size();
for (int i = 0; i < size; ++i) {
Node cur = queue.poll();
if (cur == target) {
return step;
}
for (Node next : cur.neighbors) {
if (!used.contains(next)) {
queue.add(root);
used.add(root);
}
}
}
}
return -1; // there is no path from root to target
}
}BFS与DFS相关的问题，经常都可以用两种方式求解，因此把相关问题放一起。
单点最短路径常常选择BFS，连通性、检测环、二分性常常使用DFS
- 剑指 Offer 13. 机器人的运动范围
- 岛屿的周长
- 01 矩阵
- 朋友圈
- 岛屿数量
- 省份数量
- 岛屿的最大面积
- 打开转盘锁（经典问题）
- 太平洋大西洋水流问题
- 二进制矩阵中的最短路径
- 被围绕的区域
- 钥匙和房间
二分图：
拓扑排序，给定一幅有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。
编写递归代码时最重要的有以下三点：
- 递归总有一个最简单的情况 — 方法的第一条语句总是一个包含return的条件语句。
- 递归调用总是去尝试解决一个规模更小的子问题，这样递归才能收敛到最简单的情况。如下代码第三、四参数的差值一直在缩小。
- 递归调用的父问题和尝试解决的子问题之间不应该有交集。
class Solution {
public static int rank(int key, int[] a) {
return rank(key, a, 0, a.length - 1);
}
public static int rank(int key, int[] a ,int lo, int hi){
// 如果key存在于数组中，它的索引不会小于lo且不会大于hi
if(lo>hi) return -1;
int mid = lo + (hi -lo)/2;
if (key<a[mid]) return rank(key, a, lo, mid -1);
else if(key>a[mid]) return rank(key, a, mid+1, hi);
else return mid;
}
}每次写递归，都按照这三要素思考：
- 确定递归函数的参数和返回值
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 - 确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。 - 确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
- 自顶而下：通过全局变量传递递归值
- 自底而上：带返回值的递归，依次叠加
回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的深度构成的树的深度。
void backtracking(参数) {
if (终⽌条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
- 回溯函数模板返回值以及参数。回溯算法中函数返回值⼀般为void。
void backtracking(参数)
- 回溯函数终⽌条件。
if (终⽌条件) {
存放结果;
return;
}
- 回溯搜索的遍历过程。
for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
- 如果是⼀个集合来求组合的话，就需要startIndex
- 如果是多个集合取组合，各个集合之间相互不影响，那么就不⽤startIndex，例如：回溯算法：电话号 码的字⺟组合
对于排列问题：
- 每层都是从0开始搜索⽽不是startIndex
- 需要used数组记录path⾥都放了哪些元素了
回溯算法能解决如下问题：
- 组合问题：N个数⾥⾯按⼀定规则找出k个数的集合
- 排列问题：N个数按⼀定规则全排列，有⼏种排列⽅式
- 切割问题：⼀个字符串按⼀定规则有⼏种切割⽅式
- ⼦集问题：⼀个N个数的集合⾥有多少符合条件的⼦集
- 棋盘问题：N皇后，解数独等等
“树枝去重”和“树层去重”
组合问题可以抽象为树形结构，那么“使⽤过”在这个树形结构上是有两个维度的，⼀个维度是同⼀树枝上“使⽤过”，⼀个维度是同⼀树层上“使⽤过”。
常规使用树层去重，树枝去重会导致过多无谓的查找，而树层去重对于无用的查找可以及时的中断break
树层去重
- 数据无序
public void backTracking() {
HashSet<Integer> set = new HashSet<>();
for(int i = startIndex ;i< end;i ++){
if(set.contains(i)){
continue;
}
// 回溯逻辑
set.add(i);
backTracking();
set.remove(i);
}
}
- 数据有序
public void backTracking() {
for(int i = startIndex ;i< end;i ++){
//回溯中常常使用的避免重复解的条件
if(i>startIndex && nums[i-1]=nums[i]) {
continue;
}
// 回溯逻辑
backTracking();
}
}
- 排列问题中的树层去重
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
dfs(nums, new ArrayList<>(), used, res);
return res;
}
public void dfs(int[]nums, List<Integer>path,boolean[] used, List<List<Integer>> res ){
if(path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// nums[i] == nums[i-1] && used[i-1] == false
// 因为排列是从0～n进行的，说明上次已经使用nums[i]进行过排列，为了防重复直接skip
if (used[i]|| i>0&& nums[i] == nums[i-1] && !used[i-1]) continue;
path.add(nums[i]);
used[i] = true;
dfs(nums,path,used,res);
path.remove(path.size()-1);
used[i] = false;
}
}
}变形：
- 括号生成（review） - > 动态规划 + dfs + 回溯 或者 dfs + 回溯
- 解数独
- 单词搜索
- 二叉树路径
- 重新安排行程
- 组合总和 II:
排序后树层去重
if(i>index && candidates[i]== candidates[i-1]) - 全排列 II:
排序后树层去重
if(i>0 && nums[i] == nums[i-1] && used[i-1] == false) - 子集 II: 树层去重
if (i != index && nums[i] == nums[i-1]) - 递增子序列: 无序元素树层去重
if(used.contains(nums[i]))
- 划分为k个相等的子集: review
- 剑指 Offer 12. 矩阵中的路径
贪⼼的本质是选择每⼀阶段的局部最优，从⽽达到全局最优。
例如，有⼀堆钞票，你可以拿⾛⼗张，如果想达到最⼤的⾦额，你要怎么拿？
指定每次拿最⼤的，最终结果就是拿⾛最⼤数额的钱。
如何验证可不可以⽤贪⼼算法呢？
最好⽤的策略就是举反例，如果想不到反例，那么就试⼀试贪⼼吧。
贪⼼算法⼀般分为如下四步：
- 将问题分解为若⼲个⼦问题
- 找出适合的贪⼼策略
- 求解每⼀个⼦问题的最优解
- 将局部最优解堆叠成全局最优解
动态规划的⼀般流程优化三步：
- 暴⼒的递归解法
- 带备忘录的 递归解法
- 迭代的动态规划解法。
动态规划思想流程：
- 【状态】和【选择】，明确问题存在哪几种状态。问题场景如何做状态选择，进而转换状态。
- 确定dp数组以及下标的含义
- 根据【选择】的过程，确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组，进行问题模拟
- 出错的情况，将dp数组打印出来，保证程序处理流程如设想运行。
如果能写出暴力的递归方法，就回发现在递归过程中，进行了太多重复计算，此时可以使用备忘录的方法进行优化。
斐波那契数列备忘录优化：
class Solution {
Map<Integer, Integer> map = new HashMap<>();
public int fib(int n) {
if (n < 2) {
return n;
}
if (map.containsKey(n)) {
return map.get(n);
}
int result = fib(n - 1) + fib(n - 2);
map.put(n, result);
return result;
}
}动态规划思想优化：
class Solution {
public int fib(int n) {
if (n < 2) {
return n;
}
int prv = 1;
int pprv = 0;
int result = 0;
for (int i = 2; i <= n; i++) {
result = prv + pprv;
pprv = prv;
prv = result;
}
return result;
}
}第⼀种思路模板是⼀个⼀维的 dp 数组
第二个思路模版是建立一个二维的dp数组
- 定义dp：两字符串的动态规划问题，经常的就是以字符串1与字符串2的长度组成二维数组。
- 定义下标及含义：dp的含义经常就是求解的结果，下标为从0～i、j的两字符串的子问题
- 状态转移公式：主要考虑以下三个的状态转移
dp[i-1][j-1]: 匹配条件的，结果顺推。如子数组匹配问题dp[i-1][j]dp[i][j-1]
- 初始化
- 最长递增子序列
- 最长连续递增序列
- 剑指 Offer II 095. 最长公共子序列
- 不相交的线
- 判断子序列
- 环形子数组的最大和
- 不同的子序列: review
- 最长递增子序列的个数: review
- 最长的斐波那契子序列的长度: 子序列状态变形
回文问题demo：
class Solution {
public int countSubstrings(String s) {
int len = s.length();
boolean[][] dp = new boolean[len][len];
int result = 0;
// 初始化0值
for (int i = 0; i < len; i++) {
dp[i][i] = true;
result++;
}
// 自底而上，自左而右，遍历右上部分三角区域
for (int i = len - 2; i >= 0; i--) {
for (int j = i + 1; j < len; j++) {
// 状态转移
if (s.charAt(i) == s.charAt(j)) {
// i与j相邻情形
if (j - i == 1) {
dp[i][j] = true;
result++;
// 判断子内容是否为回文
} else if (dp[i + 1][j - 1]) {
dp[i][j] = true;
result++;
}
}
}
}
return result;
}
}public class StockTrading {
public static void main(String[] args) {
// int[] prices = new int[]{3,3,5,0,0,3,1,4};
int[] prices = new int[]{1, 2, 3, 4, 5};
StockTrading st = new StockTrading();
System.out.println(st.maxProfit(2, prices));
}
/**
* 1. 定义dp及下标
* dp[i][j][k]含义为第i天所能获取的最大利润
* 下标i：天数
* 下标j：第j次交易
* 下标k：0买入、1卖出
*
* 2. 初始化，由于dp代表的是第i天所能获取的最大利润，第0天卖出均要初始化成-price[0]。(可以理解为与次数不挂钩，仅进行一次交易)
*
* 3. 状态转移：
* dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
* dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
* @param prices
* @return
*/
public int maxProfit(int k, int[] prices) {
int len = prices.length;
int[][][] dp = new int[prices.length][k + 1][2];
// 若交易数超过天数一半，转化为不限交易次数问题
if (k > len / 2) return maxProfitNoLimit(prices);
for (int i = 1; i <= k; i++) {
dp[0][i][1] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[len - 1][k][0];
}
public int maxProfitNoLimit(int[] prices) {
int n = prices.length;
int buy = -prices[0];
int empty = 0;
for (int i = 1; i < n; i++) {
int curEmpty = Math.max(empty, buy + prices[i]);
int curBuy = Math.max(buy, empty - prices[i]);
empty = curEmpty;
buy = curBuy;
}
return empty;
}
}股票问题中，需要区分的一个点是，代表卖出买入的 dp[i][0] 与 dp[i][1]的状态转移问题
- 若买入
dp[i][1]从 卖出dp[i-1][0]转移而来说明，可以多次交易 - 若买入
dp[i][1]仅从dp[i-1][1]转移而来，说明仅能进行一次交易
对于含冷冻期的股票，也可以表示为一个状态
对于限制次数的股票交易，在k数值较小的情况，可以将交易次数k打平，如用数字4表示第二次的卖出
01背包问题
public class ZeroOnePackage {
public static void main(String[] args) {
ZeroOnePackage zeroOnePackage = new ZeroOnePackage();
int[] v = {1, 2, 3, 4};
int[] val = {2, 4, 4, 5};
System.out.println(zeroOnePackage.getMaxValueOfPackage2(4, 5, v, val));
}
/**
* 二维矩阵 01 背包
* n个物品 m的体积的背包
* 先遍历物品再遍历背包，测试每个物品放进背包与不放进背包的最大价值
*
* f[n][m] = max( f[n-1][m], f[n-1][m-v[i]] + val[i] )
*
* @param m
* @param n
* @param v
* @param val
* @return
*/
public int getMaxValueOfPackage(int n, int m, int[] v, int[] val) {
// 这边定义为n+1 与 m+1 个二维矩阵，表示i个物品的j体积的最大价值。下面注意 数组-1问题
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
// 默认第i个物品不放进背包
dp[i][j] = dp[i - 1][j];
// 第i个物品放进背包， 前提条件体积j大于物品i的体积，取最大价值
if (j >= v[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i - 1]] + val[i - 1]);
}
}
}
return dp[n][m];
}
/**
* 01 背包一维数组的解法
* 注意需要逆序处理，因为原先的二维压缩成一维，在开始第i个物品的遍历时，dp存储的为i-1个物品的最大价值。
* 若使用顺序遍历，则i-1个物品的最大价值会被覆盖，每次放进物品取 dp[j-v[i-1]] 的数据是往前取，因此需要逆序遍历
* f[j] = max(f[j], f[j-v[i]])
* @param n
* @param m
* @param v
* @param val
* @return
*/
public int getMaxValueOfPackage2(int n, int m, int[] v, int[] val) {
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
//优化使用j>=v[i-1], 仅需要查看 v[i-1] ~ m 这个体积区间的最大价值是否需要更新
for (int j = m; j >= v[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + val[i - 1]);
}
}
return dp[m];
}
}完全背包问题
public class FullPackage {
public static void main(String[] args) {
FullPackage fullPackage = new FullPackage();
int[] v = {1, 2, 3, 4};
int[] val = {2, 4, 4, 5};
System.out.println(fullPackage.getMaxPackageValue2(4, 5, v, val));
}
/**
* 二维数组完全背包
* 按硬币和体积的顺序二维遍历，每次物品只有放与不放两种情况，第i个物品不放则总价值与i-1个物品一致
* 第i个物品放进背包，则价值为 f[i][j-v[i]]+ val[i] 注意这边同样为第i行，因为物品可以放多次。
* f[i][j] = max( f[i-1][j] + f[i][j-v[i]+ val[i])
* @param n
* @param m
* @param v
* @param val
* @return
*/
public int getMaxPackageValue(int n, int m, int[] v, int[] val) {
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 默认第i个物品不放进背包
dp[i][j] = dp[i - 1][j];
// 第i个物品放进背包，前提条件体积j大于物品i的体积，取最大价值
if (j >= v[i - 1]) {
dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i - 1]] + val[i - 1]);
}
}
}
return dp[n][m];
}
/**
* 一维压缩 完全背包
* 此处不需要从大到小遍历，因为物品可以多次放入背包，因此取得状态为第i个物品遍历体积的前序状态。
* @param n
* @param m
* @param v
* @param val
* @return
*/
public int getMaxPackageValue2(int n, int m, int[] v, int[] val) {
int[] dp = new int[m + 1];
for (int i = 1; i <= n; i++) {
for (int j = v[i - 1]; j <= m; j++) {
dp[j] = Math.max(dp[j], dp[j - v[i - 1]] + val[i - 1]);
}
}
return dp[m];
}
}除了上述背包问题的常见解法，还需区分先遍历物品再遍历背包，与先遍历背包再遍历物品的区别。
在完全背包的前提下，即物品可放多次，区分遍历顺序，结果会有如下不同：
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。组合不强调顺序，如(1,5)和(5,1)是同⼀个组合。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。排列强调顺序，如(1,5)和(5,1)是两个不同的排列。
如果把遍历nums（物品）放在外循环，遍历target的作为内循环的话，举⼀个例⼦：计算
dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，物品遍历已经确定3只能出现在1后⾯！ 而遍历target的作为外循环的，遍历nums（物品）放在内循环的话，举⼀个例⼦：计算dp[4]的时候，结果集会有 {1,3},{3,1} 这样的集合，分别从dp[1]、dp[3]转移过来！
for(int i =1; i< 物品.length;i++) {
for(int j = 1;j< 背包.length;j++) {
}
}
for(int i =1; i< 背包.length;i++) {
for(int j = 1;j< 物品.length;j++) {
}
}
01背包：
完全背包：
该问题理解的关键为：因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第 i 层楼碎没碎，最后搜索的取决于那种情况的结果更⼤。
class Solution {
Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
public int superEggDrop(int k, int n) {
return dp(k, n);
}
public int dp(int k, int n) {
if (!memo.containsKey(n * 100 + k)) {
int ans = Integer.MAX_VALUE;
// 层数为0，不需要尝试
if (n == 0) {
ans = 0;
// 只剩一个鸡蛋，最坏得试n次
} else if (k == 1) {
ans = n;
} else {
int lo = 1, hi = n;
while (lo <= hi) {
int x = (hi - lo) / 2 + lo;
// 鸡蛋丢坏的区域搜索
int t1 = dp(k - 1, x - 1);
// 鸡蛋未对坏的区域搜索
int t2 = dp(k, n - x);
// 鸡蛋丢坏的次数与鸡蛋未丢坏的次数对比，搜索次数多的区域，表示搜索最坏情况要丢多少次
if (t1 <= t2) {
lo = x + 1;
ans = Math.min(ans, t2 + 1);
} else {
hi = x - 1;
ans = Math.min(ans, t1 + 1);
}
}
}
// 备忘录
memo.put(n * 100 + k, ans);
}
return memo.get(n * 100 + k);
}
}前缀树又名字典树，单词查找树，Trie树，是一种多路树形结构，是哈希树的变种，和hash效率有一拼，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
class UnionFindSet {
int[] rank;
int[] parent;
public UnionFindSet(int n) {
rank = new int[n];
parent = new int[n];
}
public int find(int x) {
if (parent[x] == 0) return x;
return parent[x] = find(parent[x]); // Path compression by halving.
}
public boolean union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return true;
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootX] = rootY;
rank[rootY]++;
}
return false;
}
}「力扣」第 1319 题：连通网络的操作次数（中等）；
「力扣」第 1631 题：最小体力消耗路径（中等）；
「力扣」第 959 题：由斜杠划分区域（中等）；
「力扣」第 1202 题：交换字符串中的元素（中等）；
「力扣」第 947 题：移除最多的同行或同列石头（中等）；
「力扣」第 721 题：账户合并（中等）；
「力扣」第 803 题：打砖块（困难）；
「力扣」第 1579 题：保证图可完全遍历（困难）;
「力扣」第 778 题：水位上升的泳池中游泳（困难）。
常用操作：
判断负数，快速的判断又避免精度溢出问题
private static void assertNumberMinus() {
int num1 = 1231;
int num2 = -12;
System.out.println("(1231 ^ -12) < 0 :" + ((num1 ^ num2) < 0));
}
数字字符处理操作: 统一转小写、统一转大写、大小写交换
统一转小写
('A' | ' ') = 'a';
('a' | ' ') = 'a';
统一转大写
('b' & '_') = 'B'
('B' & '_') = 'B'
大小写交换
('d' ^ ' ') = 'D'
('D' ^ ' ') = 'd'
消除数字 n 的⼆进制表⽰中的最后⼀个1：n&(n-1)
- 计算一个数字转二进制后1的个数
- 判断一个数是否为2的指数
private static void countBit() {
int res = 0;
int num = 1002930;
int n = num;
while (n != 0) {
n = n & (n - 1);
res++;
}
System.out.println("num:" + num + ",count one number:" + res);
}
private static boolean isPowerOfTwo(int n) {
if (n <= 0) return false;
return (n & (n - 1)) == 0;
}
- 位1的个数
- Pow(x, n) :快速幂，位运算与运算转换
- 剑指 Offer 56 - I. 数组中数字出现的次数
前缀和是一种重要的预处理，能大大降低查询的时间复杂度。两个位置的前缀和差值，能快速确定这段区间的sumup
相关关键词：连续子数组
如何确定一个数是素数
public class Solution {
public static boolean isPrime(int n) {
if (n < 0) {
return false;
}
int k = (int) Math.sqrt(n);
for (int i = 2; i <= k; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime(int N) {
if (N < 2) {
return false;
}
for (int i = 2; i * i <= N; i++) {
if (N % i == 0) {
return false;
}
}
return true;
}
}public class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
// 余数
int d = n % 10;
// 整除进位
n = n / 10;
// 余数操作
totalSum += d * d;
}
return totalSum;
}
}对于一个给定数组 A，Kadane 算法可以用来找到 A 的最大子段和。
class Solution {
public int maxSubArray(int[] nums) {
int dp = 0, res = Integer.MIN_VALUE;
for(int num : nums) {
dp = num + Math.max(dp, 0);
res = Math.max(dp, res);
}
return res;
}
}以找出游戏的获胜者该题为例：
我们第一轮会删掉第k个人，问题就变为对n−1个人进行这个游戏。
假设我们知道f(n−1,k)最终剩下的人的编号, 由于我们删了第k个人，n-1个人的游戏是从原来第k+1个人开始的，
也就是说原来的编号和新的编号有一个偏差k。
以坐标从0到n-1来看的话(去掉1的偏差减少计算量,最终加一次1即可)，有公式:
f(n,k) = (f(n - 1, k) + k) % n
当只剩一个人时，他必然活下来， 即f(1,k) = 0
我们从f(1,k)推出f(2,k)一直到f(n,k)即可。
相关问题：
针对于整数，超过精度的时候，经常会导致答案有误
针对于字符串转数字场景下，常用的超精读判断如下：
public class Solution{
public int convert(String str, boolean isMinus) {
int res = 0;
int sign = isMinus? -1 : 1;
int len = str.length();
for(int i = 0;i<len;i++) {
char ch = str.charAt(i);
int num = ch - '0';
// 针对于正数，提前判断是否超过最大值
if (res > Integer.MAX_VALUE / 10
|| (res == Integer.MAX_VALUE / 10 && num > Integer.MAX_VALUE % 10)) {
return Integer.MAX_VALUE;
}
// 针对于负数，提前判断是否超过最小值
if (res < Integer.MIN_VALUE / 10
|| (res == Integer.MIN_VALUE / 10 && num > -(Integer.MIN_VALUE % 10))) {
return Integer.MIN_VALUE;
}
res = res*10 + num * sign;
}
}
}