其实是数据结构课程设计交的作业
-
冒泡排序 O(n^2)
-
选择排序 O(n^2)
-
插入排序 O(n^2) — 对于基本有序的数列效率最高
-
希尔排序 O(nlogn) — 插入排序的优化
-
归并排序 O(nlogn) — 需要额外的空间存储
-
快速排序 O(nlogn ~ n^2) — 最常用,但对有序数列严重退化
-
堆排序 O(nlogn) — 璐神讲过,是否再讲?—— 还是讲了-_-||
-
基数排序 — 简单了解即可,不常用
求逆序对数:
给一列数a1,a2......an,求它的 逆序对数,即有多少个有序对 (i,j),使得i < j 但 ai > aj
第k小数:
输入n个整数和一个正整数k(1 <= k <= n), 输出这些整数从小到大排序后的第k个
f(n) = f(n-1) + f(n-2)
普通写法:递归
动态规划写法:自底向上,空间换时间
有时空间也可以省
for i : 0 -> n
for j : 0 -> min(i, k)
if j = 0 or j = i
c[i][j] = 1
else c[i][j] = c[i-1][j-1] + c[i-1][j]
https://oj.leetcode.com/problems/triangle/
d(i, j) = a(i, j) + min{d(i+1, j), d(i+1, j+1)}
d(j) = a(i, j) + min{d(j), d(j+1)}
—重叠子问题的记忆化搜索 — 画图更能直观理解(树)
https://oj.leetcode.com/problems/maximum-subarray/
if A[i] > A[i] + A[i-1] A[i] = A[i]
else A[i] = A[i] + A[i-1]
https://oj.leetcode.com/problems/decode-ways/
边界条件的考虑!!!
if s[i] == 0 and s[i-1] != 1 and s[i-1] != 2 : return 0
else if s[i] == 0 : dp[i] = dp[i-2]
else if s[i-1] == 1 || s[i-1] == 2 && s[i] = 1~6 : dp[i] = dp[i-1] + dp[i-2]
else dp[i] = dp[i-1]
有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。 f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值
0-1背包:
f[i][v] = max(f[i-1][v], f[i-1][v-c[i]] + w[i])
优化空间复杂度:
for i 0 -> N
for v V -> 0
f[v] = max(f[v], f[v-c[i]] + w[i])
初始化的细节:
-
背包恰好装满:f[0] = 0, f[1 ~ V] = -oo
-
不要求背包装满:全部初始化为0
如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好 装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是−∞了。如果 背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0, 所以初始时状态的值也就全部为0了
完全背包:
令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值
f[i][v] = max{f[i-1][v], f[i − 1][v − k × c[i]] + k × w[i]} 0 < k × c[i] < v
一个很简单有效的优化,是这样的:若两件物品i、j满 足c[i] < c[j]且w[i] > w[j],则将物品j去掉,不用考虑
for i 0 -> N
for v 0 -> V
f[v] = max(f[v], f[v-c[i]] + w[i])
混合背包: k 的取值在其给定的范围内即可
http://acm.hdu.edu.cn/showproblem.php?pid=2602 http://acm.hdu.edu.cn/showproblem.php?pid=1114 http://acm.hdu.edu.cn/showproblem.php?pid=2191
- 优势:避免了对同一个子问题多次求解
- 劣势:可能会对一些不必要的子问题求解
- 最优化
- 无后效性
- 有重叠子问题
- 划分阶段
- 确定状态和状态变量 — 必须满足无后效性
- 状态转移方程
- 寻找边界条件
核心:状态转移方程 注意:边界条件