链表
1 | // 单链表节点的结构 |
链表反转
1. 递归反转整个链表
明确递归函数的定义： 输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
1 | ListNode reverse(ListNode head) { |
2. 反转链表前N个节点
1 | // 将链表的前 n 个节点反转（n <= 链表长度） |
3. 反转链表的一部分
1 | ListNode reverseBetween(ListNode head, int m, int n) { |
// 反转以 a 为头结点的链表
ListNode reverse(ListNode a) {
ListNode pre, cur, nxt;
pre = null; cur = a; nxt = a;
while (cur != null) {
nxt = cur.next;
// 逐个节点反转
cur.next = pre;
// 更新指针位置
pre = cur; // 最后的值为最后的节点
cur = nxt; // 最后的值为NULL
}
// 返回反转后的头节点
return pre;
}
/** 反转区间 [a, b) 的元素，注意是左闭右开 */
ListNode reverse(ListNode a, ListNode b) {
ListNode pre, cur, nxt;
pre = null; cur = a, nxt = a;
while (cur != b) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
1 |
|
ListNode reverseKGroup(ListNode head, int k) {
if (head == null) return null;
// 区间 [a, b) 包含 k 个待反转元素
ListNode a, b;
a = b = head;
for (int i = 0 ; i < k ; i++) {
// 不足k个， 不需要反转， base case
if (b == null)
return head;
b = b.next;
}
// 反转前k个元素
ListNode newHead = reverse(a, b);
// 递归反转后续链表并连接起来
a.next = reverseKGroup(b, k);
return newHead;
}
1 |
|
boolean isPalindrome(String s) {
int left = 0, right = s.length - 1;
while (left < right) {
if (s[left] != s[right])
return false;
left++;
right–;
}
return true;
}
1 |
|
boolean isPalindrome(ListNode head) {
}
1 |
|
void traverse(TreeNode root) {
// 前序遍历代码
traverse(root.left)
// 中序遍历代码
traverse(root.right)
// 后序遍历代码
}
1 |
|
void traverse(ListNode head) {
// 前序遍历代码
traverse(head.next);
// 后序遍历代码
}
1 |
|
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// 后序遍历代码
print(head.val);
}
模仿双指针实现回文判断的功能：
ListNode left;
boolean isPalindrome(ListNode head) {
left = head;
return traverse(head);
}
boolean traverse(ListNode right) {
if (right == null) return true;
boolean res = traverse(right.next);
// 后序遍历代码
res = res && (right.val == left.val);
left = left.next;
return res;
}
####优化空间复杂度
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
if (fast != null)
slow = slow.next;
ListNode left = head;
ListNode right = reverse(slow);
while (right != null) {
}
二叉树遍历框架
/* 二叉树遍历框架 */
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
快速排序
void quicksort(int[] nums, int lo, int hi) {
/****** 前序遍历位置 ******/
// 通过交换元素构建分界点 p
int p = partition(nums, lo, hi);
/*****************/
quicksort(nums, lo, p-1);
quicksort(nums, p+1, hi);
}
归并排序
void sort(int[] nums, int lo, int hi) {
int mid = (lo + hi) / 2;
sort(nums, lo, mid);
sort(nums, mid, hi);
/****** 后序遍历位置 ******/
// 合并两个排好序的子数组
merge(nums, lo, mid, hi);
}
只要涉及到递归，都可以抽象成二叉树的问题
写递归算法的关键是要明确函数的「定义」是什么，然后相信这个定义，利用这个定义推导最终结果，绝不要跳入递归的细节。
计算一棵二叉树共有几个节点：
// 定义：count(root) 返回以 root 为根的树有多少节点
int count(TreeNode root) {
// base case
if (root == null) return 0;
// 自己加上子树的节点数就是整棵树的节点数
return 1 + count(root.left) + count(root.right);
}
# 226.翻转二叉树（简单）
我们发现只要把二叉树上的每一个节点的左右子节点进行交换，
最后的结果就是完全翻转之后的二叉树。
TreeNode invertTree(TreeNode root) {
// base case
if (root == null)
return null;
/*****前序遍历位置***********/
// root 节点需要交换它的左右子节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 让左右子节点继续翻转它们的子节点
invertTree(root.left);
invertTree(root.right);
return root;
}
# 116.填充每个节点的下一个右侧节点指针（中等）
// Node connect(Node root) {
// if (root == null || root.left == null) {
// return root;
// }
// root.left.next = root.right; // 连接每个节点的左右子节点
// connect(root.left);
// connect(root.right);
// return root;
// }
// 主函数
Node connect(Node root) {
if (root == null)
return null;
connectTwoNode(root.left, root.right);
return root;
}
// 辅助函数
void connectTwoNode(Node node1. Node node2) {
if (node1 == null || node2 == null) {
return;
}
/***前序遍历位置 ******/
// 将传入的两个节点连接
node1.next = node2;
// 连接相同父节点的两个子节点
connectTwoNode(node1.left, node1.right);
connectTwoNode(node2.left, node2.right);
// 连接跨越父节点的两个子节点
connectTwoNode(node1.right, node2.left);
}
# 114.二叉树展开为链表（中等）
// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
// base case
if (root == null) return;
// 将 root 的左子树和右子树拉平。
flatten(root.left);
flatten(root.right);
/******后序遍历位置******/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将 root 的右子树接到左子树(当前右子树)下方，然后将整个左子树作为右子树。
TreeNode p = root;
while (p.right != null) {
p = p.right;
}
p.right = right; // 将 root 的右子树接到左子树
}
#654.最大二叉树（中等）
int[] nums = [3,2,1,6,0,5];
reeNode constructMaximumBinaryTree(int[] nums) {
return build(nums, 0, nums.length-1);
}
// 构造二叉树
TreeNode build(int[] nums, int lo, int hi) {
// base case
if (lo > hi) {
return null;
}
// 找出数组中的最大值和对应的索引
int maxVal = Integer.MIN_VALUE;
int index = -1;
for (int i=lo; i<=hi; i++) {
if(nums[i] > maxVal) {
maxVal = nums[i];
index = i;
}
}
// 构造根节点
TreeNode root = new TreeNode(maxVal);
// 递归调用构造左右子树
root.left = build(nums, lo, index-1);
root.right = build(nums, index+1, hi);
return root;
}
#105.从前序与中序遍历序列构造二叉树（中等）
// 1. 从前序遍历结果中找到root
// 2. 根据root的值，在中序遍历结果找到root的索引index
// 3. 根据索引index, 把中序数组分为左右两部分left, right
// 4. 在左右两部分递归 1，2，3
/* 主函数 */
TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
/*
若前序遍历数组为 preorder[preStart..preEnd]，
后续遍历数组为 postorder[postStart..postEnd]，
构造二叉树，返回该二叉树的根节点
*/
TreeNode build(int[] preorder, int preStart, int preEnd,
int[] inorder, int inStart, int inEnd) {
if (preStart > preEnd) {
return null;
}
// root 节点对应的值就是前序遍历数组的第一个元素
int rootVal = preorder[preStart];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
int leftSize = index - instart;
TreeNode root = new TreeNode(rootVal);
// 递归构造左右子树
root.left = build(preorder, preStart+1, preStart+leftsize,
inorder, instart, index-1);
root.right = build(preorder, preStart+leftSize+1, preEnd,
inorder, index+1, inEnd);
return root;
}
#106.从中序与后序遍历序列构造二叉树（中等）
TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.lenght - 1);
}
TreeNode build(int[] inorder, int inStart, int inEnd,
int[] postorder, int postStart, int postEnd) {
// root 节点对应的值就是后序遍历数组的最后一个元素
int rootVal = postorder[postEnd];
// rootVal 在中序遍历数组中的索引
int index = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == rootVal) {
index = i;
break;
}
}
TreeNode root = new TreeNode(rootVal);
int leftSize = index - inStart; // 左半部分的大小
// 递归构造左右子树
root.left = build(inorder, inStart, index-1,
postorder, postStart, postStart+leftsize-1);
root.right = build(inorder, index+1, inEnd,
postorder, postStart+leftSize, postEnd-1);
return root;
}
做二叉树的问题，关键是把题目的要求细化，搞清楚根节点应该做什么，
然后剩下的事情抛给前/中/后序的遍历框架就行了。
#652.寻找重复的子树（中等）
重复子树：具有相同的结构以及相同的节点值
// 记录所有子树
HashSet<String> memo = new HashSet<>();
// 记录重复的子树根节点 使用Hashset的话 res的结果会重复
LinkedList<TreeNode> res = new LinkedList<>();
// 通过拼接字符串的方式把二叉树序列化
String traverse(TreeNode root) {
// 对于空节点，可以用一个特殊字符表示
if (root == null) {
return '#';
}
// 将左右子树序列化成字符串
String left = traverse(root.left);
String right = traverse(root.right);
/* 后序遍历代码位置 */
// 左右子树加上自己，就是以自己为根的二叉树序列化结果
String subTree = left + ","+ root.val + "," + right;
if (memo.contains(subTree)) {
res.add(root);
} else {
memo.add(subTree);
}
return subTree;
}
List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
// 当前节点该做什么？
// 当前节点子树的结构 // 树序列化
// 与其他节点子树进行比较
return res;
}
// 记录所有子树以及出现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录重复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();
/* 主函数 */
List<TreeNode> findDuplicatedSubtrees(TreeNode root) {
traverse(root);
return res;
}
/* 辅助函数 */
String traverse(TreeNode root) {
// 对于空节点，可以用一个特殊字符表示
if (root == null) {
return '#';
}
// 将左右子树序列化成字符串
String left = traverse(root.left);
String right = traverse(root.right);
/* 后序遍历代码位置 */
// 左右子树加上自己，就是以自己为根的二叉树序列化结果
String subTree = left + ","+ root.val + "," + right;
int freq = memo.getOrDefault(subTree, 0);
// 多次重复也只会被加入结果集一次
if (freq == 1) {
res.add(root);
}
// 给子树对应的出现次数加1
memo.put(subTree, freq + 1);
return subTree;
}
二叉搜索树 BST
AVL树 红黑树 B+树 线段树
中序遍历是有序的
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历位置
print(root.val);
traverse(root.right);
}
#230 二叉搜索树中第k小的元素
int kthSmallest(TreeNode root, int k) {
// 利用BST的中序遍历特性
inorder(root, k);
return res;
}
// 记录结果
int res = 0;
// 记录当前元素的排名
int rank = 0;
void inorder(TreeNode root, int k) {
if (root == null) {
return;
}
inorder(root.left, k);
/* 中序遍历代码位置 */
rank++; // 真正访问根节点的时候 rank+1
if (k == rank) {
// 找到第k小的元素
res = root.val;
return;
}
inorder(root.right, k);
}
已知节点数的二叉搜索树节点
class TreeNode {
int val;
int size; // 以该节点为根的树节点总数
TreeNode left;
TreeNode right;
}
#538 二叉搜索树转换为累加树
降序打印节点的值
void postorder(TreeNode root) {
if (root == null) return;
// 先递归遍历右子树
postorder(root.right);
print(root.val);
// 后递归遍历左子树
postorder(root.left);
}
TreeNode convert(TreeNode root) {
postorder(root);
return root;
}
int sum = 0; // 记录累加和
void postorder(TreeNode root) {
if (root == null) return;
postorder(root.right);
sum += root.val;
// 将BST转化成累加树
root.val = sum;
postorder(root.left);
}
BST 相关的问题，要么利用 BST 左小右大的特性提升算法效率，
要么利用中序遍历的特性满足题目的要求，也就这么些事儿吧。
#98.验证二叉搜索树（中等）
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若root.val不符合min max的限制，说明不是合法BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是root.val, 右子树的最小值是root.val
return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
}
#700.二叉搜索树中的搜索（简单）
boolean isInBST(TreeNode root, int target) {
if (root == null) return false;
if (target == root.val)
return true;
else if (target < root.val) {
return isInBST(root.left, target);
} else {
return isInBST(root.right, target);
}
}
// BST 的遍历框架
void BST(TreeNode root, int target) {
if (target == root.val)
// do something
else if (target < root.val) {
BST(root.left, target);
} else {
BST(root.right, target);
}
}
#701.二叉搜索树中的插入操作（中等）
遍历（找） + 访问（改）
找插入位置 插入
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, int val);
} else if (val > root.val) {
root.right = insertIntoBST(roor.right, int val);
} else {
// pass
}
return root;
}
#450.删除二叉搜索树中的节点（中等）
先找再改
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// 找到了， 进行删除
if (root.left == null && root.right == null)
return null;
else if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
else {
// 找到左子树最大的节点，或右子树最小的节点
TreeNode minNode = getMin(root.right);
// 把root 改成 minNode
root.val = minNode.val;
// 转而去右子树删除 minNode
root.right = deleteNode(root.right, minNode.val);
}
} else if (key < root.val) {
// 去左子树找
root.left = deleteNode(root.left, key);
} else {
root.right = deleteNode(root.right, key);
}
return root;
}
TreeNode getMin(TreeNode node) {
// BST 最左边的就是最小的
while (node.left != null) node = node.left;
return node;
}
#297.二叉树的序列化和反序列化（困难）
public class Codec {
// 把一棵二叉树序列化成字符串
public String serialize(TreeNode root) {}
// 把字符串反序列化成二叉树
public TreeNode deserialize(String data) {}
}
# 序列化
// 代表分隔符的字符
String SEP = ",";
// 代表null空指针的字符
String NULL = "#";
/* 主函数，将二叉树序列化为字符串 */
String serialize(TreeNode root) {
// 用于拼接字符串
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
# 前序
/* 辅助函数，将二叉树存入 StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
/****** 前序遍历位置 ******/
sb.append(root.val).append(SEP);
/***********************/
serialize(root.left, sb);
serialize(root.right, sb);
}
# 后序
void serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
serialize(root.left, sb);
serialize(root.right, sb);
/****** 后序遍历位置 ******/
sb.append(root.val).append(SEP);
/***********************/
}
字符串转列表
String data = "1,2,#,4,#,#,3,#,#,";
String[] nodes = data.split(",");
nodes: 1 -> 2 -> # -> 4 -> # -> # -> 3 -> # -> #
# 反序列化
/* 主函数，将字符串反序列化为二叉树结构 */
TreeNode deserialize(String data) {
// 将字符串转换成列表
LinkedList<String> nodes = new LinkedList<>();
for (String s : data.split(SEP)) {
nodes.addLast(s);
}
return deserialize(nodes);
}
# 前序
/* 辅助函数，通过 nodes 列表构造二叉树 */
TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty())
return null;
/****** 前序遍历位置 ******/
// 列表最左侧就是根节点
String first = nodes.removeFirst();
if (first.equals(NULL))
return null;
// 字符串解析为整型
TreeNode root = new TreeNode(Integer.parseInt(first));
root.left = deserialize(nodes);
root.right = deserialize(nodes);
return root;
}
# 后序
/* 辅助函数，通过 nodes 列表构造二叉树 */
TreeNode deserialize(LinkedList<String> nodes) {
if (nodes.isEmpty())
return null;
// 从后往前取出元素
String last = nodes.removeLast();
if (last.equals(NULL))
return null;
TreeNode root = new TreeNode(Integer.parseInt(last));
// 先构造右子树，后构造左子树
root.right = deserialize(nodes);
root.left = deserialize(nodes);
return root;
}
# 层序遍历二叉树
void traverse(TreeNode root) {
if (root == null)
return;
// 初始化队列， 将root加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root); // 将root加入根节点
while (!q.isEmpty()) {
TreeNode cur = q.poll(); // 获取并移除队首元素
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}
# 反序列化过程需要记录空指针null
void traverse(TreeNode root) {
if (root == null)
return null;
// 初始化队列， 将root加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
TreeNode cur = q.poll(); // 获取当前队首元素
/* 层级遍历代码位置 */
if (cur == null)
continue; //提前结束本次循环 直接继续执行下次循环
System.out.println(cur.val);
q.offer(cur.left);
q.offer(cur.right);
}
}
# 层序序列化
String SEP = ",";
String NULL = "#";
/* 将二叉树序列化为字符串 */
String serialize(TreeNode root) {
if (root == null)
return "";
StringBuilder sb = new StringBuilder();
// 初始化列表，将root加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while(!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
if (cur == null) {
sb.append(NULL).append(SEP);
continue;
}
sb.append(cur.val).append(SEP);
q.offer(cur.left);
q.offer(cur.right);
}
return sb.toString();
}
1 2 3 # 4 # # # #
/* 将字符串反序列化为二叉树结构 */
TreeNode deserialize(String data) {
if (data.isEmpty())
return null;
String[] nodes = data.split(SEP);
// 第一个元素就是root的值
TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
// 队列q记录父节点，将root加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
for (int i=1; i<nodes.length; ) {
// 队列中存的都是父节点
TreeNode parent = q.poll();
// 父节点对应的左侧子节点的值
String left = nodes[i++];
if (!left.equals(NULL)) {
parent.left = new TreeNode(Integer.parseInt(left));
q.offer(parent.left);
} else {
parent.left = null;
}
// 父节点对应的右侧子节点的值
String right = nodes[i++];
if (!right.equals(NULL)) {
parent.right = new TreeNode(Integer.parseInt(right));
q.offer(parent.right);
} else {
parent.right = null;
}
}
return root;
}
# 341.扁平化嵌套列表迭代器（中等）
public class NestedInteger {
// 如果其中存的是一个整数，则返回 true，否则返回 false
public boolean isInteger();
// 如果其中存的是一个整数，则返回这个整数，否则返回 null
public Integer getInteger();
// 如果其中存的是一个列表，则返回这个列表，否则返回 null
public List<NestedInteger> getList();
}
public class NestedIterator implements Iterator<Integer> {
// 构造器输入一个 NestedInteger 列表
public NestedInteger(List<NestedInteger> nestedList) {}
// 返回下一个整数
public Integer next() {}
// 是否还有下一个元素
public boolean hasNext() {}
}
N叉树遍历框架
void traverse(TreeNode root) {
for (TreeNode child : root.children)
traverse(child);
}
class NestedIterator implements Iterator<Integer> {
private Iterator<Integer> it;
public NestedIterator(List<NestedInteger> nestedList) {
// 存放将nestedList 打平的结果
List<Integer> result = new LinkedList<>();
for (NestedInteger node: nestedList) {
// 以每个节点为根遍历
traverse(node, result);
}
// 得到result列表的迭代器
this.it = result.iterator();
}
public Integer next() {
return it.next();
}
public boolean hasNext() {
return it.hasNext();
}
// 遍历以 root 为根的多叉树，将叶子节点的值加入 result 列表
private void traverse(NestedInteger root, List<Integer> result) {
if (root.isInteger()) {
// 到达叶子节点
result.add(root.getInteger());
return;
}
// 遍历框架
for (NestedInteger child : root.getList()) {
traverse(child, result);
}
}
}
public class NestedIterator implements Iterator<Integer> {
private LinkedList<NestedInteger> list;
public NestedIterator(List<NestedInteger> nestedList) {
list = new LinkedList<>(nestedList);
}
public Integer next() {
// hasNext 方法保证了第一个元素一定是整数类型
return list.remove(0).getInteger();
}
public boolean hasNext() {
// 循环拆分列表元素，直到列表第一个元素是整数类型
while (!list.isEmpty() && !list.get(0).isInteger()) {
// 当列表开头第一个元素是列表类型时，进入循环
List<NestedInteger> first = list.remove(0).getList();
// 将第一个列表打平并按顺序添加到开头
for (int i = first.size() - 1; i >= 0; i--) {
list.addFirst(first.get(i));
}
}
return !list.isEmpty();
}
}
#236 二叉树的最近公共祖先
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
if (root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left != null && right != null) {
return root;
}
if (left == null && right == null)
return null;
return left == null ? right : left;
}
#222.完全二叉树的节点个数（中等）
节点个数 = 前n-1层 + 最后一层
2^(n-1) - 1 + ?
普通二叉树
public int countNodes(TreeNode root) {
if (root == null)
return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
满二叉树
public int countNodes(TreeNode root) {
int h = 0;
// 计算树高
while (root != null) {
root = root.left;
h++;
}
// 节点总数
return (int)Math.pow(2, h) - 1;
}
完全二叉树
public int countNodes(TreeNode root) {
TreeNode l = root, r = root;
// 记录左右子树的高度
int hl = 0, hr = 0;
while (l != null) {
l = l.left;
hl++;
}
while (r != null) {
r = r.right;
hr++;
}
// 如果左右子树的高度相同，则是一棵满二叉树
if (hl == hr) {
return (int) Math.pow(2, hl) - 1;
}
// 如果左右高度不同，则按照普通二叉树的逻辑计算
return 1 + countNodes(root.left) + countNodes(root.right);
}
// 复杂度分析
动态规划 运筹学的一种最优化方法
一般形式 ：求最值
核心问题 ：穷举
重叠子问题 暴力穷举效率低下 所以需要备忘录或者DP table来优化穷举过程 避免不必要的计算
动态规划具备最优子结构
只有列出正确的状态转移方程才能正确的穷举
明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。
# 重叠子问题 -> 斐波那契数列
int fib(int N) {
if (N < 1)
return 0;
// 备忘录全初始化为0
vector<int> memo(N+1, 0);
// 进行带备忘录的递归
return helper(memo, N);
}
# 自顶向下
int helper(vector<int>& memo, int n) {
// base case
if (n == 1 || n == 2)
return 1;
// 如果已经计算过 直接返回
if (memo[n] != 0) {
return memo[n];
}
// 否则递归计算
memo[n] = helper(memo, n-1) + helper(memo, n-2);
return memo[n];
}
# 动态规划 自底向上 循环迭代
int fib(int N) {
if (N < 1)
return 0;
if (N == 1 || N == 2)
return 1;
vector<int> dp(N+1, 0);
// base case
dp[1] = dp[2] = 1;
for (int i=3; i<=N; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[N];
}
# 优化空间复杂度 dp table
int fib(int n) {
if (n < 1)
return 0;
if (n == 1 || n == 2)
return 1;
int prev = 1, curr = 1;
for (int i=3; i<=n; i++) {
int sum = prev + curr;
prev = curr;
curr = sum;
}
return curr;
}
# 凑零钱问题
1. 确定base case
2. 确定状态 问题中会变化的量
3. 确定选择
4. 明确dp数组的定义
# 暴力递归
def coinChange(coins: List[int], amout: int):
def dp(n):
# base case
if n == 0: return 0;
if n < 0: return -1;
# 求最小值，所以初始化为正无穷
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
# 子问题无解，跳过
if subproblem == -1:
continue
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
return dp(amount)
# 带备忘录的递归
def coinChange(coins: List[int], amount: int):
# 备忘录
memo = dict()
def dp(n):
# 查备忘录, 避免重复计算
if n in memo:
return memo[n]
# base case
if n == 0:
return 0
if n < 0:
return -1
res = float('INF')
for coin in coins:
subproblem = dp(n - coin)
if subproblem == -1:
continue
res = min(res, 1 + subproblem)
# 记入备忘录
memo[n] = res if res != float('INF') else -1
return memo[n]
return dp(amount)
# dp数组的迭代解法
int coinChange(vector<int>& coins, int amount) {
// 数组大小为 amount + 1，初始值也为 amount + 1
vector<int> dp(amount+1, amount+1);
// base case
dp[0] = 0;
// 外层 for 循环遍历所有状态的所有取值
for (int i=0; i<dp.size(); i++) {
// 内层 for 循环在求所有选择的最小值
for(int coin: coins) {
// 子问题无解，跳过
if (i - coin < 0)
continue
// 选或不选
dp[i] = min(dp[i], 1 + dp[i-coin]);
}
}
return (dp[amount] == amount+1) ? -1 : dp[amount];
}
# 最优子结构 子问题之间必须相互独立
动态规划 = 最优子结构 + 重叠子问题
暴力递归解 -> 优化（备忘录） -> dp数组迭代
dp数组
1. 明确dp数组的含义
2. 定义base case
3. 找状态转移方程
遍历dp数组
1、遍历的过程中，所需的状态必须是已经计算出来的。
2、遍历的终点必须是存储结果的那个位置。
# 最长公共子序列
1. dp[i][j]的含义是：对于s1[1..i]和s2[1..j]，它们的LCS长度是dp[i][j]
2. base case 索引为0的行或列表示空串
3. 找状态转移方程
# 暴力递归
def longestCommonSubsequence(str1, str2) -> int:
def dp(i, j):
# 空串的base case
if i == -1 or j == -1:
return 0;
if str1[i] == str2[j]:
# 找到一个lcs元素，继续往前找
return dp(i-1, j-1) + 1
else: # 当前不是lcs元素
# 谁能让lcs最长，就听谁的
return max(dp(i-1, j), dp(i, j-1))
# i和j初始化为最后一个索引
return dp(len(str1)-1, len(str2)-1)
# dp table 自底向上迭代
def longestCommonSubsequence(str1, str2) -> int:
m, n = len(str1), len(str2)
# 构建DP table 和 base case
dp = [[0] * (n+1) for _ in range(m+1)]
# 进行状态转移
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[j-1]:
dp[i][j] = 1 + dp[i-1][j-1]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# 编辑距离
DNA相似度
horse -> ros
intention -> execution
rad -> apple
s1 -> s2
if s1[i] == s2[j]:
skip
i,j同时向前移动
else:
3选1
insert
delete
replace
def minDistance(s1, s2) -> int:
# 返回s1[0..i] 和 s2[0..j]的最小编辑距离
def dp(i, j):
# base case是i走完s1, j走完s2, 直接返回另一个字符串剩下的长度
if i == -1: return j+1
if j == -1: return i+1
if s1[i] == s2[j]:
return dp(i-1, j-1) # skip
else:
return min(
dp(i, j-1) + 1, # 插入
dp(i-1, j) + 1, # 删除
dp(i-1, j-1) + 1, # 替换
)
# i,j 初始化指向最后一个索引
return dp(len(s1)-1, len(s2)-1)
dp[i-1][j-1]存储s1和s2的最小编辑距离
int minDistance(String s1, String s2) {
int m = s1.length, n = s2.length();
int[][] dp = new int[m+1][n+1];
// base case
for (int i=1; i<m; i++) {
dp[i][0] = i;
}
for (int j=1; j<n; j++) {
dp[0][j] = j;
}
// 自底向上求解
for (int i=1; i<=m; i++) {
for (int j=1; j<=n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else
dp[i][j] = min(
dp[i-1][j] + 1,
dp[i][j-1] + 1,
dp[i-1][j-1] + 1
);
}
}
return dp[m][n];
}
int min(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
# 数学归纳法
最长递增子序列 1维
dp[i] 表示以nums[i]这个数结尾的最长递增子序列的长度
public int lengthOfLTS(int[] nums) {
int[] dp = new int[nums.length];
// dp数组全都初始化为1
Arrays.fill(dp, 1);
for (int i=1; i<nums.length; i++) {
for (int j=0; j<i; j++) {
if (nums[j] < nums[i])
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
int res = 0;
for (int i=0; i<dp.length; i++) {
res = Math.max(res, dp[i]);
}
return res;
}
# 最长回文子串
String palindrome(String s, int l, int r) {
// 防止索引越界
while(l >=0 && r < s.size() && s[l] == s[r]) {
// 向两边展开
l--;
r++;
}
return s.substr(l+1, r-l-1);
}
String longestPalindrome(String s) {
String res;
for (int i=0; i<s.size(); i++) {
// 以s[i]为中心的最长回文子串
String s1 = palindrome(s, i, i);
// 以s[i] 和 s[i+1] 为中心的最长回文子串
String s2 = palindrome(s, i, i+1);
res = res.size() > s1.size()? res : s1;
res = res.size() > s2.size()? res : s2;
}
return res;
}
# 最长回文子序列 2维
dp数组的定义 : 在子串s[i..j]中，最长回文子序列的长度为dp[i][j]
要求的是dp[0][n-1]
int longestpalindromeSubseq(string s) {
int n = s.size();
// dp 数组全部初始化为0
vector<vector<int>> dp(n, vector<int>(n,0));
// base case
for (int i=0; i<n; i++) {
dp[i][i] = 1;
}
// 反着遍历保证正确的状态转移
for (int i=n-2; i>=0; i--) {
for (int j=i+1; j<n; j++) {
// 状态转移方程
if (s[i] == s[j])
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
}
}
// 整个s的最长回文子串长度
return dp[0][n-1];
}