背包九讲读书笔记

0-1 背包问题

基本题目套路

有 N 件物品和一个容量为 V 的背包，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使总价值总和最大。

基本题目思路

• 特点：每件物品只有一个，选择：放 or 不放。
• 子问题：F[i, v]： 前 i 件物品恰好放入容量 v 的背包，可以获得的最大价值
• 状态转移：F[i, v] = max{F[i-1, v], F[i-1, v-Ci] + Wi}
• 当前的价值，只和之前的价值有关，因此两个选择下的价值为：
• 如果 i 不选，价值：前 i-1 件，放入容量 v 的背包（F[i-1, v]）
• 如果 i 选择，价值：前 i-1 件，放入容量（v-Ci）的背包（确保 i 能放下去，得减去 i 占用的容量）+ 放入 i 的价值 Wi

伪代码

1
2
3
4

F[0, 0..V] <- 0
for i <- 1 to N
    for v <- Ci to V
        F[i, v] <- max{F[i-1, v], F[i-1, v-Ci] + Wi}

优化

时间复杂度：O(VN)
空间复杂度：滚动数组（逆序计算 F[v]，才能保证正确的顺序）

1
2
3
4

F[0..V] <- 0
for i <- 1 to N
    for v <- V to Ci
        F[v] <- max{F[v], F[v-Ci] + Wi}

1
2
3

def ZeroOnePack(F,C,W)
    for v <- V to C
        F[v] <- max(F[v], F[C-v] + W)

1
2
3

F[0..V] <- 0
    for i <- 1 to N
        ZeroOnePack(F,Ci,Wi)

完全背包问题

题目基本套路

N 种物品和容量为 V 的背包，每种物品都有无限件可以用，放入第 i 件物品消耗的费用是 Ci， 得到的价值是 Wi。 求解将哪些物品装入背包，可使物品总消耗费用不超过背包容量，且价值总和最大。

基本套路

• 每种物品无限件，因此每个物品的策略不是：选和不选。而是选几件
• 状态转移：F[i, v] = max{F[i-1, v-kCi] + kWi | 0 ≤ kCi ≤ v}

简单有效的优化

• 若两件物品i, j 满足 Ci ≤ Cj 且 Wi ≥ Wj，则可以将 j 直接去掉，不用考虑 (任何情况下，都可以将价值小费用高的 j 换成物美价廉的 i)
• 或者 将费用大于 V 的物品去掉

转换为 0-1 背包问题

• 第 i 种物品最多选：V/Ci 种，把第 i 种物品转化为 V/Ci 件费用及价值不变的物品。 （将一种物品转化为多件只能选 0 或者 1 件的 0-1 背包问题）
• 二进制：第 i 种物品拆成费用为 Ci2^k，价值为 Wi2^k 的若干件物品。 k 满足 Ci2^k ≤ V 的非负整数。

起因

今天做了一道题，LeetCode 560. Subarray Sum Equals K，有点蒙蔽，看了答案发现比较简单，记录一下

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

1
2
3
4
5
6
7
8

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :

数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

链表总结

1
2
3
4
5

struct ListNode{
    int value;
    ListNode* next;
    ListNode(int v) : value(v), next(nullptr) { }
};

二叉树总结

1
2
3
4
5
6

struct TreeNode{
    int value;
    TreeNode *left;
    TreeNode *right
    TreeNode(int v): value(v),left(nullptr), right(nullptr) {}
};

题目

Find the Duplicated Number
Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

1
2

Input: [1,3,4,2,2]
Output: 2

Example 2:

1
2

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

动态规划套路

有一个 m*n 大小的矩阵迷宫，每次移动只能向右或者向下，文聪左上角到右下角有多少种不同的走法

暴力解法

• 从(1,1)->(m,n)的不同路径中有大量的重复，比如(1,1)->(i,j)有 k 条不同的路径，那么对于任何一条固定的路线(i,j)->(m,n)的路径，都需要走 k 遍来模拟。
• 不关心具体的走法，只关心状态，也就是走法的数量
• 同理，如果知道(i,j)->(m,n)有 k 条不同的路径，那么(1,1)->(i,j)->(m,n)的不同路径总数是k*s

动态规划

• 令(i,j)表示从(1,1)->(i,j)的不同路径数量，f(i,j) = f(i-1,j) + f(i,j-1)
• 如果要求出 f(i,j) 只需要上一个结果即可， 也就是求解f(i,j) 需要求出子问题f(i',j')

动态规划适用前提

无后效性

• 一旦确定f(i,j)，就不用关心如何计算出f(i,j)
• 想要确定f(i,j)，只要知道f(i-1,j)和f(i,j-1)

最优子结构

• f(i,j)的定义已经蕴含最优
• 大问题的最优解可以由若干小问题的最优解推出(min, max, sum)

  DP 适用的问题：可以将大问题拆成几个小问题，且无后效性，具有最优子结构的性质

记忆化递归

• 可以使用递归求解
• 有重复子问题，overlaping subproblem

题目

Majority Element
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

1
2

Input: [3,2,3]
Output: 3

Example 2:

1
2

Input: [2,2,1,1,1,2,2]
Output: 2

题目

Single Number II
Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

1
2

Input: [2,2,3,2]
Output: 3

Example 2:

1
2

Input: [0,1,0,1,0,1,99]
Output: 99

题目

Construct Binary Tree from Preorder and Postorder Traversal
Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example 1:

1
2

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note:

1
2
3

1 <= pre.length == post.length <= 30
pre[] and post[] are both permutations of 1, 2, ..., pre.length.
It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

来自维基百科

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

/*
        The purpose of this function is to convert an unsigned
        binary number to reflected binary Gray code.

        The operator >> is shift right. The operator ^ is exclusive or.
*/
unsigned int binaryToGray(unsigned int num)
{
        return (num >> 1) ^ num;
}

/*
        The purpose of this function is to convert a reflected binary
        Gray code number to a binary number.
*/
unsigned int grayToBinary(unsigned int num)
{
    unsigned int mask;
    for (mask = num >> 1; mask != 0; mask = mask >> 1)
    {
        num = num ^ mask;
    }
    return num;
}