算法
1. 哈希表
2. 数组与字符串
2.1. 数组
2.2. 字符串
3. 链表
4. 队列
4.1. 广度优先搜索(BFS)
4.2. 单调队列
5. 栈
5.1. 深度优先搜索(DFS)
5.2. 单调栈
6. BFS 与 DFS
6.1. 拓扑排序
6.2. 并查集
7. 递归
7.1. 递归三要素
7.2. 递归的思想
8. 树
8.1. 二叉树
8.1.1. 树的遍历
8.1.2. 递归思想
8.1.3. 构造及修改二叉树问题
8.1.4. 公共祖先问题
8.2. 二叉搜索树
8.3. 算法
8.3.1. 树的遍历
8.3.2. 树的属性
8.3.3. 子树问题
8.3.4. 树的高度
8.3.5. 树的构建与修改
8.3.6. 树的基本操作
8.3.7. 公共祖先问题
9. 回溯
9.1. 伪代码模版
9.1.1. 回溯三部曲
9.1.2. startIndex使用
9.2. 问题场景
9.3. 重复问题
9.4. 组合问题
9.5. 切割问题
9.6. 排列问题
9.7. 子集问题
10. 贪心
10.1. 指针与区间局部最优
10.2. 区间问题
10.3. 其他
11. 动态规划
11.1. 基本思想
11.2. 相关问题
11.3. 字符串问题
11.3.1. 字符操作
11.3.2. 子序列问题
11.3.3. 子数组问题
11.3.4. 回文问题
11.4. 股票问题
11.5. 背包问题
11.5.1. 常见求解方式及疑难点
11.5.2. 典型背包问题
11.5.3. 背包场景问题
11.6. 扔鸡蛋问题
12. 二分法
13. 前缀树
14. 滑动窗口
15. TODO 二进制应用
16. 常用操作
16.1. Kanade 算法
哈希表的关键思想是使用哈希函数将键映射到存储桶。
HashMap常见操作
public class Solution{
public static void main(String[] args ) {
Map<Integer, Integer> hashmap = new HashMap<>();
// 2. insert a new (key, value) pair
//putIfAbsent()保存数据的时候，如果该链表中保存的有相同key的值，那么就不会对我们当前的value进行保存
hashmap.putIfAbsent(0, 0);
hashmap.putIfAbsent(2, 3);
hashmap.putIfAbsent(1,4);
hashmap.putIfAbsent(2,4);
int mer = hashmap.merge(1,6,(v1, v2) -> v1+v2);
//output 1 ->8
int value =12;
int key2 = map.computeIfAbsent(2,k -> value);
int key3 = map.computeIfAbsent(3,k -> value);
// output key2 = 4, key3 = 12
int res = map.computeIfPresent(3,(key, oldVal) -> oldVal-1);
//output res = 11
int result1 = map.compute(3,(key, oldValue) -> oldValue-10);
//output 10
int result = map.compute(4,(key, oldValue) -> oldValue-10);
//cause error nullPoint,key 4 not exist
map.put(1, count.getOrDefault(1, 0) + 1);
// 取1的值，如果存在则取value 否则默认为0、
}
}哈希接口判断元素存在：
使用哈希映射的场景：
利用哈希表O(1)特性查找：
公共前缀问题
分治法、二分法
回文问题（包含子串与子序列问题）
双指针问题
快慢指针：
-
移除数组
-
移动零
链表双指针：
虚拟节点：
经典问题：
栈、头插法、递归
反转链表递归写法:
public class Solution{
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;
}
}队列是典型的 FIFO 数据结构。
-
插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。
-
删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
广度优先搜索（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
}
}单调队列，即单调递减或单调递增的队列。 需要使用 双向队列 ，假设队列已经有若干元素：
- 当执行入队 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）是用于 在树/图中遍历/搜索 的另一种重要算法。也可以在更抽象的场景中使用。
正如树的遍历中所提到的，我们可以用 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 Solution {
public int[] dailyTemperatures(int[] T) {
Deque<Integer> stack = new LinkedList<>();
int len = T.length;
int[] res = new int[len];
// 从尾到头遍历
for (int i = len - 1; i >= 0; i--) {
while (!stack.isEmpty() && T[stack.peek()] <= T[i]) {
stack.pop();
}
// 判断位置差值
res[i] = stack.isEmpty() ? 0 : stack.peek() - i;
stack.push(i);
}
return res;
}
}单调栈类似思想
- *接雨水
单调栈解法，递减栈，每次计算增量
最大矩形计算，获取索引i的左右小于
height[i]的最高点索引
BFS与DFS相关的问题，经常都可以用两种方式求解，因此把相关问题放一起。
判断方法很特别，通过节点染色
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 题：水位上升的泳池中游泳（困难）。
每次写递归，都按照这三要素思考：
- 确定递归函数的参数和返回值
确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。 - 确定终止条件：
写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。 - 确定单层递归的逻辑：
确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
- 自顶而下：通过全局变量传递递归值
- 自底而上：带返回值的递归，依次叠加
前中后序遍历递归与迭代写法
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;
}
}以二叉树深度为例： 二叉树的深度
// 自顶而下 通过全局变量传递值
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;
}
}二叉搜索树的最近公共祖先(与树的公共祖先有区别) ：使用了二叉搜索树的特点
二叉搜索树构建：
二叉搜索树：
完全二叉树：
子树问题，为了避免重复的遍历判断是否同一子数可以使用序列化的方式解决
二叉搜索树：
回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的深度构成的树的深度。
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();
}
}
-
-
动态规划 + dfs + 回溯 或者 dfs + 回溯
-
public class Soluction {
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++) {
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;
}
}
}贪⼼的本质是选择每⼀阶段的局部最优，从⽽达到全局最优。
例如，有⼀堆钞票，你可以拿⾛⼗张，如果想达到最⼤的⾦额，你要怎么拿？
指定每次拿最⼤的，最终结果就是拿⾛最⼤数额的钱。
如何验证可不可以⽤贪⼼算法呢？
最好⽤的策略就是举反例，如果想不到反例，那么就试⼀试贪⼼吧。
贪⼼算法⼀般分为如下四步：
- 将问题分解为若⼲个⼦问题
- 找出适合的贪⼼策略
- 求解每⼀个⼦问题的最优解
- 将局部最优解堆叠成全局最优解
动态规划的⼀般流程优化三步：
- 暴⼒的递归解法 ->
- 带备忘录的 递归解法 ->
- 迭代的动态规划解法。
动态规划思想流程：
- 【状态】和【选择】，明确问题存在哪几种状态；问题场景如何做状态选择，进而转换状态。
- 确定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]
- 初始化
回文问题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后⾯！
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效率有一拼，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计
它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
计算1的个数
求余数常见操作
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;
}
}