Skip to content

DataStructureAndAlgorithms.md

Latest commit

History

History
583 lines (486 loc) · 14.9 KB

DataStructureAndAlgorithms.md

File metadata and controls

583 lines (486 loc) · 14.9 KB
Raw

数据结构和算法

数据结构

数组

  • 表现形式：

int[] array = {15, 85, 55, 99, 26}

链表

  • 表现形式：

// 双向链表privatestaticclassNode<E> {
// 数据Eitem;
// 后继节点Node<E> next;
// 前驱节点Node<E> prev;
Node(Node<E> prev, Eelement, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 单向链表privatestaticclassNode<E> {
// 数据Eitem;
// 后继节点Node<E> next;
Node(Eelement, Node<E> next) {
this.item = element;
this.next = next;
}
}

双向环形链表：最后一个节点的 next 指向 head 节点，head 节点的 prev 指向最后一个节点。

在实现上，又有带哨兵的双向环形链表和不带哨兵的双向环形链表。区别在于，带哨兵的双向环形链表，额外用一个哨兵节点表示 head，即链表头。

队列

queue 是以顺序的方式维护一组数据集合，在一端添加数据，从另一端移除数据。一般地，添加的一端称为尾，移除的一端称为头。（体现在先进先出）

  • 表现形式：

对于链表、数组的实现，额外引入两个指针，头指针、尾指针，当添加元素时，尾指针移动，当移除元素时，头指针移动。

栈

只能在其一端添加和移除数据，一般地，添加数据的一端称为栈顶，另一端称为栈底。（体现在先进后出）

其实现方式有基于数组、链表。

堆

堆是一种基于树的数据结构，通常用完全二叉树实现。其特性如下：

  • 最顶层的节点称为 root 根节点。

  • 在大顶堆中，任意节点 C 与其父节点 P 符合 P.value >= C.value。

  • 而小顶堆中，任意节点 C 与其父节点 P 符合 P.value <= C.value。

二叉树

二叉搜索树

AVI树

红黑树

B树

哈希表

图

算法

动态规划

从已知子问题的解，推导出当前问题的解，且推导过程可以表达为一个数学公式。

找出递推公式，将当前问题分解成子问题，分阶段进行求解。求解过程中缓存子问题的解，避免重复计算。

动态规划是一种数学规划的建模思想, 但本身却只蕴含了一个和暴力枚举差不多的基本算法.

斐波那契

/** * <pre> * 前两项的和等于第三项（利用额外的参数缓存前两项的和，避免了像递归重复计算） * F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 * 0 1 1 2 3 5 8 13 21 34 55 89 144 233 * @param n 项 * @return */publicintfibonacci(intn) {
if (n == 0) {
returnn;
}
if (n == 1) {
returnn;
}
inta = 0;
intb = 1;
for (inti = 2; i <= n; i++) {
intc = a + b;
a = b;
b = c;
}
returnb;
}

最短路径

/** * <pre> * 从起点到任一点的最短距离 * * 初始化时： * 当 v == 起点时，f(v) = 0 * 当 v != 起点时，f(v) = ∞ * * 计算两两点之间最短距离的递归公式： * 新最短距离 旧最短距离 v到任一点的距离 * f(to) = min(f(to), f(from) + from.weight) * * dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight) * * 假定有 v1、v2、v3、v4、v5、v6 6个节点，循环节点-1次即可 * @return 起点到任一点的最短距离数组 */publicint[] optimalPath() {
List<Edge> edges = Arrays.asList(
newEdge(6, 5, 9),
newEdge(4, 5, 6),
newEdge(1, 6, 14),
newEdge(3, 6, 2),
newEdge(3, 4, 11),
newEdge(2, 4, 15),
newEdge(1, 3, 9),
newEdge(1, 2, 7)
);
int[] dp = newint[7];
for (inti = 2; i < dp.length; i++) {
dp[i] = Integer.MAX_VALUE;
}
for (inti = 0; i < 5; i++) {
for (Edgee : edges) {
if (dp[e.from] != Integer.MAX_VALUE) {
dp[e.to] = Integer.min(dp[e.to], dp[e.from] + e.weight);
}
}
}
returndp;
}
staticclassEdge {
publicEdge(Integerfrom, Integerto, Integerweight) {
this.from = from;
this.to = to;
this.weight = weight;
}
/**当前边的起点*/privatefinalIntegerfrom;
/**当前边的终点*/privatefinalIntegerto;
/**当前边的起点到该边终点的距离*/privatefinalIntegerweight;
}

不同路径

/** * <pre> * 假定3行7列：从 dp[0][0] 到 dp[2][6] 的路线共有多少种走法，只允许向右和向下。起点和终点用'▲'标识 * * ▲ 0 0 0 0 0 0 * 0 0 0 0 0 0 0 * 0 0 0 0 0 0 ▲ * * 第一行和第一列的路径都是1 * ▲ 1 1 1 1 1 1 * 1 0 0 0 0 0 0 * 1 0 0 0 0 0 ▲ * * 而规律就是路径之和 = 上边和左边的路径之和 * ▲ 1 1 1 1 1 1 * 1 2 3 4 5 6 7 * 1 3 6 10 15 21 ▲(28) * * @param line 行 * @param column 列 * @return */publicintuniquePaths(intline, intcolumn) {
int[] dp = newint[column];
for (inti = 0; i < column; i++) {
dp[i] = 1;
}
for (inti = 1; i < line; i++) {
for (intj = 1; j < column; j++) {
dp[j] = dp[j] + dp[j - 1];
}
}
returndp[column - 1];
}

01背包问题

/** * <pre> 1. 假定背包容量为10g，要求取走不超过背包容量的物品 2. 每次可以不拿或全拿，但是每件物品只能拿一次，问最高价值是多少? 编号 重量(g) 价值(元) 1 4 1600 黄金(A) 2 8 2400 红宝石(R) 3 5 30 白银(S) 4 1 10000 钻石(D) 0 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 A A A A A A A 黄金 2 0 0 0 0 A A A A R R R 红宝石 3 0 0 0 0 A A A A R R R 白银 4 0 D D D D DA DA DA DA DR DR 钻石 其递推公式为： if (装不下) { dp[i][j] = dp[i-1][j] } else { 装得下 // 当前背包最大价值 = max(上一次最大价值, 当前物品价值 + 放入当前物品之前的背包容量最大价值) dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight]) } * * @param items 物品数组 * @param capacity 容量 * @return 最大价值 */publicintselect(Item[] items, intcapacity) {
int [] dp = newint[capacity + 1];
Itemitem0 = items[0];
// 特殊处理第0行数据for (intj = 0; j < capacity + 1; j++) {
// 背包容量装得下第0行物品if (j >= item0.weight) {
dp[j] = item0.value;
}
}
for (inti = 1; i < items.length; i++) {
for (intj = capacity; j > 0; j--) {
// 装得下if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
returndp[capacity];
}
/**物品*/staticclassItem {
/**编号*/privateintindex;
/**物品名称*/privateStringname;
/**重量(g)*/privateintweight;
/**价值*/privateintvalue;
publicItem(intindex, Stringname, intweight, intvalue) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}

完全背包问题

完全背包问题 和 01背包问题 两者大同小异，唯一的区别就是：

  • 01背包问题 每件物品只有一个，即只能取一次。

  • 而 完全背包问题 每件物品可以重复取。

/** * <pre> 1. 假定背包容量为10g，要求取走不超过背包容量的物品 2. 每次可以不拿或全拿，每件物品可以重复取，问最高价值是多少? 编号 重量(g) 价值(元) 1 2 3 青铜(c) 2 3 4 白银(s) 3 4 5 黄金(a) 0 1 2 3 4 5 6 1 0 0 c c cc cc ccc 青铜 2 0 0 c s s sc ss 白银 3 0 0 c s a a ac 黄金 其递推公式为： if (装不下) { dp[i][j] = dp[i-1][j] } else { 装得下 // 当前背包最大价值 = max(上一次最大价值, 当前物品价值 + 放入当前物品之前的背包容量最大价值) dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight]) } * * @param items 物品数组 * @param capacity 容量 * @return 最大价值 */publicintselect(Item[] items, intcapacity) {
int [] dp = newint[capacity + 1];
Itemitem0 = items[0];
// 特殊处理第0行数据for (intj = 0; j < capacity + 1; j++) {
// 背包容量装得下第0行物品if (j >= item0.weight) {
dp[j] = dp[j - item0.weight] + item0.value;
}
}
for (inti = 1; i < items.length; i++) {
for (intj = capacity; j > 0; j--) {
// 装得下if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
returndp[capacity];
}
staticclassItem {
/**编号*/privateintindex;
/**物品名称*/privateStringname;
/**重量(g)*/privateintweight;
/**价值*/privateintvalue;
publicItem(intindex, Stringname, intweight, intvalue) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}

零钱兑换问题--最少组成

/**<pre> 面值 0 1 2 3 4 5 1 0 1 11 111 1111 11111 2 0 1 2 21 22 221 5 0 1 2 21 22 1 总金额 - 类比为背包容量 硬币面值 - 类比为物品重量 硬币个数 - 类比为物品价值，固定为1，（因为是求最少组成总金额的硬币数量） 递推公式如下： if (装得下) { 上次硬币组成个数, 剩余容量能装下的最小个数+1 （个数固定为1） dp[j] = Integer.min(dp[j], dp[j - coins[i]] + 1); // dp[i][j] = max(dp[i-1][j], dp[i-1][j-item.weight] + 1) } else { 保留上次个数不变 dp[i][j] = dp[i-1][j] } * @param coins 面值种类 * @param amount 总金额 * @return 最少组成总金额的硬币数量 */publicintcoinChange(int[] coins, intamount) {
int[] dp = newint[amount + 1];
// 特殊处理第0行数据，可以用Arrays.fill进行优化，赋初始值Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (intcoin : coins) {
for (intj = coin; j < amount + 1; j++) {
dp[j] = Integer.min(dp[j], dp[j - coin] + 1);
}
}
returndp[amount] < amount ? dp[amount] : -1;
}

零钱兑换问题--多少种组合

/** <pre> 面值 0 1 2 3 4 5 （总金额 - 类比为背包容量） 1 1 1 11 111 1111 11111 2 1 1 11 111 1111 11111 2 21 211 2111 22 221 5 1 1 11 111 1111 11111 2 21 211 2111 22 221 5 i: 币种，j: 列（总金额） 上一次组合种类：1 + 剩余容量的组合种类 eg: 总金额为3，面值有1、2，共有多少种组合： dp[i][j] = dp[i-1][j] + dp[i][j-coin] if (放得下) { dp[i][j] = dp[i-1][j] + dp[i][j-coin] } else { 放不下 dp[i][j] = dp[i-1][j] } * @param coins 面值种类 * @param amount 总金额 * @return 多少种组合 */publicintchange(int[] coins, intamount) {
int[] dp = newint[amount + 1];
dp[0] = 1;
for (intj = 1; j < amount + 1; j++) {
if (j >= coins[0]) {
dp[j] = dp[j - coins[0]];
}
}
for (inti = 1; i < coins.length; i++) {
for (intj = 1; j < amount + 1; j++) {
// 容量放得下if (j >= coins[i]) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
}
returndp[amount];
}

钢条切割问题

/** <pre> 钢条切割问题：怎么个切法能够构成最大价值. 钢条长度： 0 1 2 3 4 5 6 7 8 9 10 钢条价值： 0 1 5 8 9 10 17 17 20 24 30 假定钢条长3m： 0 1 2 3 4 1 1 11 111 1111 价值： 1 2 3 4 2 1 11 111 1111 2 21 211 22 价值： 1 5 6 10 3 1 11 111 1111 2 21 211 3 22 31 ... ... if (放得下) { 上一次最大价值 , 当前物品价值 + 剩余容量能装下的最大价值 dp[i][j] = max(dp[i-1][j], 当前物品价值 + dp[i][j-物品重量]) } else { 放不下 dp[i][j] = dp[i-1][j] } * @param values 价值数组 - 钢条长度(物品重量) * 钢条长度： 0 1 2 3 4 5 6 7 8 9 10 （索引） * 钢条价值： 0 1 5 8 9 10 17 17 20 24 30 * @param n 钢条长度 * @return 最大价值 */publicintcut(int[] values, intn) {
int[] dp = newint[n + 1];
for (inti = 1; i < values.length; i++) {
for (intj = 1; j < n + 1; j++) {
if (j >= i) {
dp[j] = Integer.max(dp[j], values[i] + dp[j - i]);
}
}
}
returndp[n];
}

最长公共子串

/** 最长公共字串：abcdeoma opcdeima 则两个字符串的最长公共字串为3，（连续的子串） b c d e i m a c 0 1 0 0 0 0 0 d 0 0 2 0 0 0 0 e 0 0 0 3 0 0 0 o 0 0 0 0 0 0 0 m 0 0 0 0 0 1 0 a 0 0 0 0 0 0 2 if (字符相同) { dp[i][j] = dp[i-1][j-1] + 1 } else { dp[i][j] = 0 } * @param a 串A * @param b 串B * @return 最长公共字串 */publicintlcs(Stringa, Stringb) {
int[][] dp = newint[b.length()][a.length()];
intmax = 0;
for (inti = 0; i < b.length(); i++) {
for (intj = 0; j < a.length(); j++) {
if (a.charAt(j) == b.charAt(i)) {
// 特殊处理0行或0列，如果为0行或0列，则dp[i - 1][j - 1] 索引为负数if (i == 0 || j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
max = Integer.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
returnmax;
}

最长公共子序列