# 数据结构和算法
## 数据结构
## 数组
- 表现形式：
```java
int[] array = {15, 85, 55, 99, 26}
```
### 链表
- 表现形式：
```java
// 双向链表
private static class Node {
// 数据
E item;
// 后继节点
Node next;
// 前驱节点
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
// 单向链表
private static class Node {
// 数据
E item;
// 后继节点
Node next;
Node(E element, Node next) {
this.item = element;
this.next = next;
}
}
```
> 双向环形链表：最后一个节点的 next 指向 head 节点，head 节点的 prev 指向最后一个节点。
>
> 在实现上，又有带哨兵的双向环形链表和不带哨兵的双向环形链表。区别在于，带哨兵的双向环形链表，额外用一个哨兵节点表示 head，即链表头。
### 队列
queue 是以顺序的方式维护一组数据集合，在一端添加数据，从另一端移除数据。一般地，添加的一端称为**尾**，移除的一端称为**头**。（体现在先进先出）
- 表现形式：
对于链表、数组的实现，额外引入两个指针，头指针、尾指针，当添加元素时，尾指针移动，当移除元素时，头指针移动。
### 栈
只能在其一端添加和移除数据，一般地，添加数据的一端称为栈顶，另一端称为栈底。（体现在先进后出）
其实现方式有基于数组、链表。
### 堆
堆是一种基于树的数据结构，通常用**完全二叉树**实现。其特性如下：
- 最顶层的节点称为 root 根节点。
- 在大顶堆中，任意节点 C 与其父节点 P 符合 P.value >= C.value。
- 而小顶堆中，任意节点 C 与其父节点 P 符合 P.value 动态规划是一种数学规划的建模思想, 但本身却只蕴含了一个和暴力枚举差不多的基本算法.
#### 斐波那契
```java
/**
*
* 前两项的和等于第三项（利用额外的参数缓存前两项的和，避免了像递归重复计算）
* 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
*/
public int fibonacci(int n) {
if (n == 0) {
return n;
}
if (n == 1) {
return n;
}
int a = 0;
int b = 1;
for (int i = 2; i = item0.weight) {
dp[j] = item0.value;
}
}
for (int i = 1; i < items.length; i++) {
for (int j = capacity; j > 0; j--) {
// 装得下
if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
return dp[capacity];
}
/**物品*/
static class Item {
/**编号*/
private int index;
/**物品名称*/
private String name;
/**重量(g)*/
private int weight;
/**价值*/
private int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}
```
#### 完全背包问题
`完全背包问题` 和 `01背包问题` 两者大同小异，唯一的区别就是：
- `01背包问题` 每件物品只有一个，即只能取一次。
- 而 `完全背包问题` 每件物品可以重复取。
```java
/**
*
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 最大价值
*/
public int select(Item[] items, int capacity) {
int [] dp = new int[capacity + 1];
Item item0 = items[0];
// 特殊处理第0行数据
for (int j = 0; j < capacity + 1; j++) {
// 背包容量装得下第0行物品
if (j >= item0.weight) {
dp[j] = dp[j - item0.weight] + item0.value;
}
}
for (int i = 1; i < items.length; i++) {
for (int j = capacity; j > 0; j--) {
// 装得下
if (j >= items[i].weight) {
dp[j] = Integer.max(dp[j], items[i].value + dp[j - items[i].weight]);
}
}
}
return dp[capacity];
}
static class Item {
/**编号*/
private int index;
/**物品名称*/
private String name;
/**重量(g)*/
private int weight;
/**价值*/
private int value;
public Item(int index, String name, int weight, int value) {
this.index = index;
this.name = name;
this.weight = weight;
this.value = value;
}
}
```
#### 零钱兑换问题--最少组成
```java
/**
面值 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 最少组成总金额的硬币数量
*/
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 特殊处理第0行数据，可以用Arrays.fill进行优化，赋初始值
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j < amount + 1; j++) {
dp[j] = Integer.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] < amount ? dp[amount] : -1;
}
```
#### 零钱兑换问题--多少种组合
```java
/**
面值 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 多少种组合
*/
public int change(int[] coins, int amount) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int j = 1; j < amount + 1; j++) {
if (j >= coins[0]) {
dp[j] = dp[j - coins[0]];
}
}
for (int i = 1; i < coins.length; i++) {
for (int j = 1; j < amount + 1; j++) {
// 容量放得下
if (j >= coins[i]) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
}
return dp[amount];
}
```
#### 钢条切割问题
```java
/**
钢条切割问题：怎么个切法能够构成最大价值.
钢条长度： 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 最大价值
*/
public int cut(int[] values, int n) {
int[] dp = new int[n + 1];
for (int i = 1; i < values.length; i++) {
for (int j = 1; j < n + 1; j++) {
if (j >= i) {
dp[j] = Integer.max(dp[j], values[i] + dp[j - i]);
}
}
}
return dp[n];
}
```
#### 最长公共子串
```java
/**
最长公共字串：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 最长公共字串
*/
public int lcs(String a, String b) {
int[][] dp = new int[b.length()][a.length()];
int max = 0;
for (int i = 0; i < b.length(); i++) {
for (int j = 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;
}
}
}
return max;
}
```
#### 最长公共子序列