数据结构之红黑树

理解红黑树的原理

简单的类比

想象你在盖一座形状奇特的摩天大楼。为了保证大楼不倒,建筑局(红黑树协议)做了下面的规定:

  • 黑色节点 = 承重钢梁:黑色节点是整座大楼的硬骨架。无论你走哪条楼梯,从顶楼到地面的黑色承重梁数量必须完全一样。
  • 红色节点 = 柔性连接件:红色节点是挂在承重钢架上的连接支架,两个红色支架决不能直接连在一起。因为红红不能相连,大楼最坏的情况也只是 “黑-红-黑-红”,这就保证了最长的那条路(红黑相间)顶多是短的那条路(全黑)的两倍。


LeetCode 热题(一)

两个数的和

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
import java.util.*;

public class Code001_TwoSumTarget {

public static void main(String[] args) {
int[] array = {2,2,3,4,5};
int[] result = twoSumTarget(array, 6);
System.out.println(Arrays.toString(result)); // [0, 3]

String[] ss = {"eat", "tea", "tan", "ate", "nat", "bat"};
Collection<List<String>> groupStrings = groupStrings(ss);
System.out.println(groupStrings); // [[eat, tea, ate], [bat], [tan, nat]]

int[] array2 = {10,4,20,3,1,2};
int[] result2 = findLongestConsecutiveSequence(array2);
System.out.println(Arrays.toString(result2)); // [1, 2, 3, 4]
}

/**
* 找出两个数的和为目标值的元素的下标
* 思路:使用哈希表
*/
public static int[] twoSumTarget(int[] array, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < array.length; i++) {
Integer index = map.get(target - array[i]);
if (index != null) {
return new int[] {index, i};
} else {
map.putIfAbsent(array[i], i); // 保证先出现的 2 的索引 0 被保留,后面的 2 不会覆盖它。
}
}
return null;
}

/**
* 根据字母异位词,对字符串进行分组
* eat tea tan ate nat bat -> [bat] [nat, tan] [ate, eat, tea]
* 思路:使用哈希表
*/
public static Collection<List<String>> groupStrings(String[] strings) {
Map<String, List<String>> map = new HashMap<>();

for (String str : strings) {
if (str == null) continue;
char[] chars = str.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.compute(key, (k,v) -> {
if (v == null) v = new LinkedList<>();
v.add(str);
return v;
});
}
return map.values();
}

/**
* 从数组中找出数字连续的最长序列
* [10,4,20,3,1,2] -> [1,2,3,4]
* 思路:使用 hashset
*/
public static int[] findLongestConsecutiveSequence(int[] array) {
if (array == null || array.length == 0) return new int[0];

Set<Integer> set = new HashSet<>();
for (int num : array) set.add(num);

int bestStart = array[0];
int bestLen = 0;
for (int num : array) {
// 起点就是 num - 1 不在集合里的数,只有 num 是序列的起点时才往下数
if (set.contains(num - 1)) continue;

int cur = num;
int len = 1;
while (set.contains(cur + 1)) {
cur++;
len++;
}
if (len > bestLen) {
bestLen = len;
bestStart = num;
}
}

// 组装结果
int[] result = new int[bestLen];
for (int i = 0; i < bestLen; i++) {
result[i] = bestStart + i;
}
return result;
}
}


移动所有0到末尾

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
26
27
28
29
import java.util.Arrays;

/**
* 将数组中的所有0移动到数组的末尾
* 想象一排人站成一队,有些人站着,有些人是空位(用 0 表示)。
* 你的任务:把所有站着的人挪到队伍前面,空位集中到后面。
*/
public class Code002_MoveZeroToLast {

public static void main(String[] args) {
//int[] array = {0,0,1};
int[] array = {0, 1, 0, 3, 2};
moveZeroToLast(array);
System.out.println(Arrays.toString(array)); // [1, 3, 2, 0, 0]
}

// insertIndex 是 "下一个非零元素该站的位置"。眼睛从左到右扫,看到非零的就放到那个位置,贴纸往后挪。扫完后贴纸后面的全是零。
private static void moveZeroToLast(int[] array) {
int insertIndex = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] != 0) {
array[insertIndex++] = array[i];
}
}
while (insertIndex < array.length) {
array[insertIndex++] = 0;
}
}
}


找链表的相交节点

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/**
* 返回两个单链表的相交节点
*
* 链表遍历结束后,从另一个单链表开始遍历。
*
* 如果存在相遇点,由它们走过的距离相同,所以一定会相遇。
* cur1 走:a1→a2→c1→c2→c3→null → 跳到 b1→b2→b3→c1 相遇
* cur2 走:b1→b2→b3→c1→c2→c3→null → 跳到 a1→a2→c1 相遇
*
* 如果不存在相遇点,那么它们都走过 list1+list2 的长度
*/
public class Code003_TwoLinkedListMeetNode {

public static void main(String[] args) {
Node a1 = new Node("a1");
Node a2 = new Node("a2");
Node b1 = new Node("b1");
Node b2 = new Node("b2");
Node b3 = new Node("b3");
Node c1 = new Node("c1");
Node c2 = new Node("c2");
Node c3 = new Node("c3");

a1.next = a2;
a2.next = c1;

b1.next = b2;
b2.next = b3;
b3.next = c1;

c1.next = c2;
c2.next = c3;

Node meetNode = getMeetNode(a1, b1);
System.out.println(meetNode); // c1
}

static class Node {
String e;
Node next;

public Node(String e, Node next) {
this.e = e;
this.next = next;
}

public Node(String e) {
this(e, null);
}

@Override
public String toString() {
return e;
}
}

public static Node getMeetNode(Node list1Head, Node list2Head) {
if (list1Head == null || list2Head == null) return null;

Node cur1 = list1Head;
Node cur2 = list2Head;
while (cur1 != cur2) {
cur1 = cur1 == null ? list2Head : cur1.next;
cur2 = cur2 == null ? list1Head : cur2.next;
}
return cur1; // 相交点 或 null(不相交)
}
}


翻转链表

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/**
* 翻转链表
*/
public class Code004_ReverseLinkedList {

public static void main(String[] args) {
Node a1 = new Node("a1");
Node a2 = new Node("a2");
Node a3 = new Node("a3");
a1.next = a2;
a2.next = a3;

printLinkedList(a1); // a1->a2->a3->null
Node reversedList = reverse(a1);
printLinkedList(reversedList); // a3->a2->a1->null
}

static class Node {
String e;
Node next;

public Node(String e, Node next) {
this.e = e;
this.next = next;
}

public Node(String e) {
this(e, null);
}

@Override
public String toString() {
return e;
}
}

public static Node reverse(Node listHead) {
Node prev = null;
Node cur = listHead;
while (cur != null) {
Node nextTemp = cur.next; // 暂存下一个
cur.next = prev; // 翻转指针
prev = cur; // prev 往前走
cur = nextTemp; // cur 往前走
}
return prev;
}

private static void printLinkedList(Node listHead) {
Node cur = listHead;
while (cur != null) {
System.out.print(cur + "->");
cur = cur.next;
}
System.out.println("null");
}
}


判断是否回文链表

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
import java.util.Objects;

/**
* 判断一个链表是否是回文链表
*
* 第一步:快慢指针找中点
* 第二步:反转后半段
* 第三步:前后两段逐一比较
*/
public class Code005_PalindromeLinkedList {

public static void main(String[] args) {
Node a1 = new Node("a1");
Node a2 = new Node("a2");
Node a3 = new Node("a3");
Node a4 = new Node("a2");
Node a5 = new Node("a1");

a1.next = a2;
a2.next = a3;
a3.next = a4;
a4.next = a5;

System.out.println(isPalindromeList(a1)); // true
}

static class Node {
String e;
Node next;

public Node(String e, Node next) {
this.e = e;
this.next = next;
}

public Node(String e) {
this(e, null);
}

@Override
public String toString() {
return e;
}
}

private static void printLinkedList(Node listHead) {
Node cur = listHead;
while (cur != null) {
System.out.print(cur + "->");
cur = cur.next;
}
System.out.println("null");
}

// 1. 快慢指针找中点:奇数长度返回中间那个,偶数长度返回中间左边一个
private static Node findMiddleNode(Node listHead) {
// 1. 快慢指针找中点(前半段的尾)
Node slow = listHead;
Node fast = listHead;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

// 2. 反转链表
private static Node reverse(Node listHead) {
Node prev = null;
Node cur = listHead;
while (cur != null) {
Node nextTemp = cur.next;
cur.next = prev;
prev = cur;
cur = nextTemp;
}
return prev;
}

// 3. 判断是否局部相同
private static boolean isPartSame(Node firstFullHead, Node secondHalfHead) {
Node p1 = firstFullHead;
Node p2 = secondHalfHead;
while (p2 != null) {
if (!Objects.equals(p1.e, p2.e)) return false;
p1 = p1.next;
p2 = p2.next;
}
return true;
}

public static boolean isPalindromeList(Node listHead) {
if (listHead == null) return true;
Node middleNode = findMiddleNode(listHead);
Node secondHalfHead = reverse(middleNode.next);
return isPartSame(listHead, secondHalfHead);
}
}


判断链表是否有环

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
/**
* 判断链表是否有环(可以使用快慢指针)
*/
public class Code006_LinkedListHasCycle {

public static void main(String[] args) {
Node a1 = new Node("a1");
Node a2 = new Node("a2");
Node a3 = new Node("a3");
Node a4 = new Node("a4");
Node a5 = new Node("a5");

a1.next = a2;
a2.next = a3;
a3.next = a4;
a4.next = a5;
a5.next = a3;

System.out.println(linkedListHashCycle(a1)); // true
System.out.println(getFirstNodeWhenCycle(a1)); // a3
}

static class Node {
String e;
Node next;

public Node(String e, Node next) {
this.e = e;
this.next = next;
}

public Node(String e) {
this(e, null);
}

@Override
public String toString() {
return e;
}
}

/**
* 判断链表是否有环
* 快慢指针,一个有环的跑道上快的总会追上慢的。追上了就有环,到头了就没环。
*/
public static boolean linkedListHashCycle(Node listHead) {
if (listHead == null || listHead.next == null) return false;

Node slow = listHead;
Node fast = listHead;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;

if (slow == fast) {
return true; // 相遇了,有环
}
}
return false; // fast 走到 null 了,无环
}

/**
* 返回链表入环的第一个节点
* 快慢指针相遇后,一个从头走、一个从相遇点走,速度相同,相遇处就是入环口。
*
* [头节点] ---- a ----> [入环节点] ------ b -----> [相遇点]
* ^ |
* | |
* +------ L - b -------+
* S_slow = a + b
* S_fast = a + b + k*L
*
* 因为 S_fast = 2 * S_slow
* 所以 a = k*L - b,即 a = (k - 1)L + (L - b)
*
* 直观的物理过程:
* 当相遇时,让 p1 指向头节点,p2 留在相遇点。
* p1 走了 a 步到达入环节点;
* 与此同时,p2 也走了 a 步。因为 a 相当于 “在环里绕了 k-1 圈后,再走 L-b 步”,
* 所以 p2 走完 a 步后,正好也停在了入环节点。两者步调一致,因此它们第一次重合的点就是入环节点。
*/
public static Node getFirstNodeWhenCycle(Node listHead) {
if (listHead == null || listHead.next == null) return null;

// 1. 快慢指针找相遇点
Node slow = listHead;
Node fast = listHead;
boolean hasCycle = false;

while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
hasCycle = true;
break;
}
}
if (!hasCycle) return null; // 无环

// 2. 一个从头走,一个从相遇点走,相遇处就是入环口
Node p1 = listHead;
Node p2 = slow; // slow 就是相遇点
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1; // 入环的第一个节点
}


/**
* 删除链表倒数第n个节点(前提是链表没有环!)
* 你想删倒数第 n 个节点,就让快指针先走 n 步,然后两个一起走。等快指针到终点时,慢指针刚好停在要删节点的前一个位置。
*/
public static Node removeNthFromEnd(Node listHead, int n) {
Node dummy = new Node(null); // 虚拟头节点,处理删第一个节点的边界
dummy.next = listHead;

Node fast = dummy;
Node slow = dummy;

// 1. fast 先走 n+1 步
for (int i = 0; i <= n; i++) {
fast = fast.next;
}

// 2. fast 和 slow 一起走,直到 fast 到末尾
while (fast != null) {
fast = fast.next;
slow = slow.next;
}

// 3. slow.next 就是要删的节点
slow.next = slow.next.next;
return dummy.next;
}
}


合并两个有序链表

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
* 合并两个有序链表(尾插法)
*/
public class Code007_MergeSortedLinkedList {

public static void main(String[] args) {
Node a1 = new Node(2);
Node a2 = new Node(5);
Node a3 = new Node(7);
a1.next = a2;
a2.next = a3;

Node b1 = new Node(3);
Node b2 = new Node(4);
Node b3 = new Node(8);
b1.next = b2;
b2.next = b3;

Node mergedList = mergeSortedLinkedList(a1, b1);
printLinkedList(mergedList); // 2->3->4->5->7->8->null
}

static class Node {
Integer e;
Node next;

public Node(Integer e, Node next) {
this.e = e;
this.next = next;
}

public Node(Integer e) {
this(e, null);
}

@Override
public String toString() {
return Integer.toString(e);
}
}

private static void printLinkedList(Node listHead) {
Node cur = listHead;
while (cur != null) {
System.out.print(cur + "->");
cur = cur.next;
}
System.out.println("null");
}

public static Node mergeSortedLinkedList(Node listHead1, Node listHead2) {
// 虚拟头节点,省去处理第一个节点的边界判断
Node dummy = new Node(0);
Node tail = dummy; // tail 始终指向结果链表的最后一个节点

Node p1 = listHead1;
Node p2 = listHead2;

while (p1 != null && p2 != null) {
if (p1.e < p2.e) {
tail.next = p1;
p1 = p1.next;
} else {
tail.next = p2;
p2 = p2.next;
}
tail = tail.next; // tail 往后挪
}

// 其中一个链表走完了,把另一个剩下的直接接上去
if (p1 != null) {
tail.next = p1;
} else {
tail.next = p2;
}
return dummy.next; // 跳过虚拟头节点
}
}


链表排序

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/**
* 对链表排序
*/
public class Code014_SortedLinkedList {

public static void main(String[] args) {
Node node1 = new Node(3);
Node node2 = new Node(1);
Node node3 = new Node(4);
Node node4 = new Node(2);
Node node5 = new Node(5);
Node node6 = new Node(4);

node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node6;
node1.printList(); // 3->1->4->2->5->4->null

Node newHead = mergeSortLinkedList(node1);
newHead.printList(); // 1->2->3->4->4->5->null
}

static class Node {
Integer e;
Node next;

public Node(Integer e, Node next) {
this.e = e;
this.next = next;
}
public Node(Integer e) {
this.e = e;
}

@Override
public String toString() {
return Integer.toString(e);
}

public void printList() {
Node cur = this;
while (cur != null) {
System.out.print(cur + "->");
cur = cur.next;
}
System.out.println("null");
}
}

private static Node mergeSortLinkedList(Node head) {
// 递归终止:0个或1个节点,天然有序
if (head == null || head.next == null) return head;

// 1. 找中点(快慢指针),把链表一分为二
Node mid = findMiddle(head);
Node rightHead = mid.next;
mid.next = null; // 断开

// 2. 递归排序左右两半
Node leftSorted = mergeSortLinkedList(head);
Node rightSorted = mergeSortLinkedList(rightHead);

// 3. 合并两个有序链表
return merge(leftSorted, rightSorted);
}

/**
* 快慢指针找中点(偶数时返回左半部分的尾节点)
*/
private static Node findMiddle(Node head) {
Node slow = head;
Node fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

/**
* 合并两个有序链表
*/
private static Node merge(Node l1, Node l2) {
Node dummy = new Node(0);
Node cur = dummy;

while (l1 != null && l2 != null) {
if (l1.e <= l2.e) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}

// 把剩下的直接接上
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}


判断括号是否有效

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
26
27
28
29
30
31
32
import java.util.Stack;

/**
* 判断括号是否有效
*/
public class Code010_ValidBracket {

public static void main(String[] args) {
String ss = "1 + ({4-2} + [6-5] * (8))";
System.out.println(validBracket(ss)); // true
}

private static boolean isMatch(char left, char right) {
return (left == '(' && right == ')')
|| (left == '[' && right == ']')
|| (left == '{' && right == '}');
}

private static boolean validBracket(String str) {
char[] chars = str.toCharArray();
Stack<Character> stack = new Stack<>();
for (char c : chars) {
if (c == '(' || c == '[' || c == '{') stack.push(c);
if (c == ')' || c == ']' || c == '}') {
if (stack.isEmpty()) return false; // ← 加这一行
Character popChar = stack.pop();
if (!isMatch(popChar, c)) return false;
}
}
return stack.isEmpty();
}
}


找特殊数字

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
import java.util.Arrays;

public class Code013_FindOnlyOnceNum {

public static void main(String[] args) {
int[] array1 = {1,1,2,2,3,4,4,5,5};
System.out.println(findOnlyOnceNumI(array1)); // 3

int[] array2 = {1,1,2,2,3,4,4,5};
System.out.println(Arrays.toString(findOnlyOnceNumII(array2))); // [5, 3]

int[] array3 = {1,1,1,2,2,2,3,4,4,4,5,5,5};
System.out.println(findOnlyOnceNumIII(array3)); // 3

int[] array4 = {2,2,2,2,2,3,4,4,4,5};
System.out.println(findNumIV(array4)); // 2
}

/**
* 一个数字除外(非零),其余数字都是成对存在,找出这个出现一次的数字。
* 思路:所有数字进行异或,最后结果就是所求
*/
private static int findOnlyOnceNumI(int[] array) {
if (array == null || array.length == 0) return 0;
int result = 0;
for (int num : array) {
result ^= num;
}
return result;
}

/**
* 两个数字除外,其余数字都是成对存在,找出这两个出现一次的数字。
* 思路:
*/
private static int[] findOnlyOnceNumII(int[] array) {
// 第一步:全部异或,得到 a ^ b
int xor = 0;
for (int num : array) {
xor ^= num;
}

// 第二步:找到 xor 中最低位的 1(说明 a 和 b 在这一位上不同)
int mask = xor & (-xor);

// 第三步:按这一位把数组分成两组,分别异或
int a = 0, b = 0;
for (int num : array) {
if ((num & mask) == 0) {
a ^= num; // 这一位是 0 的
} else {
b ^= num; // 这一位是 1 的
}
}

return new int[]{a, b};
}

/**
* 一个数字除外,其余数字都出现三次,找出这个出现一次的数字(该算法对正负数皆适用)。
* 思路:位计数法(通用、好理解)
*/
public static int findOnlyOnceNumIII(int[] array) {
int result = 0;
// 对每一位(0~31)分别统计
for (int i = 0; i < 32; i++) {
int count = 0;
for (int num : array) {
// 统计这一位上 1 的总数
count += (num >> i) & 1;
}
// 如果这一位上 1 的个数不是 3 的倍数,说明落单的数在这一位上是 1
// 可以扩展到任意次数k,只需要这里的条件改成 sum % k != 0 即可。
if (count % 3 != 0) {
result |= (1 << i);
}
}
return result;
}

/**
* 数组中,有个数字出现次数不少于(达到或者超过)数组中元素个数的一半,找出这个数字
* 思路:多数派投票法
*/
public static int findNumIV(int[] array) {
int candidate = 0;
int count = 0;
for (int num : array) {
if (count == 0) {
candidate = num; // 当前没人占坑,新数字上位
}
if (num == candidate) {
count++; // 自己人,+1
} else {
count--; // 对手,抵消 -1
}
}
return candidate;
}
}


岛屿的数量

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
* 计算岛屿的数量:
* 最优解:DFS 淹没法
*
* 你坐飞机巡视,看到一块陆地('1'),就知道发现了一个新岛屿。然后你派潜水员从这块陆地出发,
* 把所有和它相连的陆地全部标记为海洋(淹没/访问过)。这样下次再飞到这块区域时,就不会重复计数了。
*
* 1 1 0 0 0
* 1 1 0 0 0
* 0 0 1 0 0
* 0 0 0 1 1
*/
public class Code015_CountIslands {

public static void main(String[] args) {
char[][] grid = {
{'1', '1', '0', '0', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '1', '0', '0'},
{'0', '0', '0', '1', '1'}
};
int count = numIslands(grid);
System.out.println(count); // 3
}

public static int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;

int count = 0;
int rows = grid.length;
int cols = grid[0].length;

for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '1') {
count++; // 发现新岛屿
dfs(grid, i, j); // 把整个岛屿"淹没"
}
}
}
return count;
}

private static void dfs(char[][] grid, int i, int j) {
int rows = grid.length;
int cols = grid[0].length;

// 越界或是水,直接返回
if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == '0') {
return;
}

grid[i][j] = '0'; // 淹没当前陆地(标记为已访问)

// 向四个方向扩散
dfs(grid, i + 1, j);
dfs(grid, i - 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}


找和为 x 的所有元素

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
* 给定一个不含有重复元素的数组,找出和为 target 的所有元素
*/
public class Code018_CombinationSum {

public static void main(String[] args) {
int[] array = {2, 3, 6, 7};
int target = 7;

List<List<Integer>> resultI = combinationSumI(array, target);
System.out.println(resultI); // [[2, 2, 3], [7]]

List<List<Integer>> resultII = combinationSumII(array, target);
System.out.println(resultII); // [[7]]
}

/**
* 元素可以重复使用,决策树:
*
* 开始(还差7)
* / | | \
* 选2 选3 选6 选7
* 还差5 还差4 还差1 还差0→OK[7]
* / | \
* 选2 选3 选6
* 还差3 还差2 (超了)
* / | \
* 选2 选3 选6
* 还差1 还差0 (超了)
* OK[2,2,3]
*/
public static List<List<Integer>> combinationSumI(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>(); // 装最终答案
dfsI(candidates, 0, target, new ArrayList<>(), result); // 从索引0开始
return result;
}

/**
* 递归函数:从 candidates[index] 开始选,凑出 target
* @param candidates 候选数组
* @param index 当前考虑的位置
* @param remain 还差多少钱才能凑到 target
* @param path 当前已经选了的数字
* @param result 最终结果
*/
private static void dfsI(int[] candidates, int index, int remain,
List<Integer> path, List<List<Integer>> result) {

// 情况1:刚好凑够
if (remain == 0) {
result.add(new ArrayList<>(path)); // 拷贝,加入结果
return;
}

// 情况2:超了,直接剪枝
if (remain < 0) {
return;
}

// 从 index 开始,依次尝试每个候选数字
for (int i = index; i < candidates.length; i++) {

// 做选择:选 candidates[i]
path.add(candidates[i]);

// 递归:可以重复选同一个数字,所以传 i 而不是 i+1
// remain 减去选中的数字
dfsI(candidates, i, remain - candidates[i], path, result);

// 回溯:撤销选择,试试下一个数字
path.remove(path.size() - 1);
}
}


/**
* 元素不可以重复使用
*/
public static List<List<Integer>> combinationSumII(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 必须先排序,才能在同一层跳过重复值
dfsII(candidates, 0, target, new ArrayList<>(), result);
return result;
}

private static void dfsII(int[] candidates, int index, int remain,
List<Integer> path, List<List<Integer>> result) {
if (remain == 0) {
result.add(new ArrayList<>(path));
return;
}

if (remain < 0) {
return;
}

for (int i = index; i < candidates.length; i++) {

// 关键:同一层跳过重复值。i > index 说明不是本层第一个,且和前一个值一样 → 跳过
if (i > index && candidates[i] == candidates[i - 1]) {
continue;
}

path.add(candidates[i]);
dfsII(candidates, i + 1, remain - candidates[i], path, result);
path.remove(path.size() - 1);
}
}
}

数据结构之AVL自平衡二叉树

AVL的起源

AVL 并不是一个缩写词,而是取自它的两位前苏联发明者:G.M. Adelson-Velsky 和 E.M. Landis。他们在 1962 年的论文中首次提出了这种结构。这是历史上第一种自平衡二叉搜索树。在那个内存以 KB 计算的年代,如何高效利用存储空间和计算周期是生死攸关的大事。


一些典型的动态规划问题

斐波那契数列

0 1 1 2 3 5…【f(0) = 0, f(1) = 1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 基本的递归解法:
* 比如计算 fib(5),递归树如下,我们发现有很多重复的计算!
* 递归方程:f(n) = f(n-1) + f(n-2), f(1)=1,f(0)=0
*
* f5
* f4 f3
* f3 f2 f2 f1
* f2 f1 f1 f0 f1 f0
* f1 f0
*
* 时间复杂度 O(2ⁿ)
* 空间复杂度 O(n)
*/
private static int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n-1) + fib(n-2);
}

使用记忆化搜索进行优化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* 记忆化搜索的优化思路:
* 自然地,能想到的优化的方法是,暂时存放元素机计算过的 fib(i),这时候递归树变成了:
*
* f5
* f4
* f3
* f2
* f1 f0
*
* 时间复杂度:O(n)
* 空间复杂度:O(n)
*/
private static int fib(int n, int[] memo) {
if (n == 0 || n == 1) return n;

if (memo[n] != 0) return memo[n];
memo[n] = fib(n-1, memo) + fib(n-2, memo);

return memo[n];
}

延伸到动态规划问题:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 动态规划思路:动态规划本质就是加了一个递归备忘录
* 动态规划状态转移方程:dp[i] = dp[i-1] + dp[i-2]
*/
private static int fib(int n) {
if (n == 0 || n == 1) return n;

// dp table
int[] dp = new int[n+1];
// base case
dp[0] = 0;
dp[1] = 1;
// 状态转移
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}

对上面动态规划的简化:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* 通过观察我们发现,只需要维护 dpn_1 和 dpn_2 两个状态即可,不必存储全部的 dp 表
*
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
public static int fib(int n) {
if (n == 0 || n == 1) return n;

int dp1 = 1, dp2 = 0;
int cur = 0;
for (int i = 2; i <= n; i++) {
cur = dp1 + dp2;
dp2 = dp1;
dp1 = cur;
}
return cur;
}

斐波那契数列问题的变种 - 爬楼梯问题:每次爬一个或者两个台阶,爬n个台阶共有多少种爬法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* 你站在楼梯底下,每次可以迈 1 阶 或 2 阶。
* 核心直觉是,到达第 n 阶,只有两种可能:
* 从第 n-1 阶迈 1 步上来
* 从第 n-2 阶迈 2 步上来
* 所以,到第 n 阶的方法数 = 到第 n-1 阶的方法数 + 到第 n-2 阶的方法数,这就是斐波那契数列。
*/
public static int countClimbTheStairs(int n) {
if (n <= 2) return n;

int prevII = 1; // n=1 时的爬法
int prevI = 2; // n=2 时的爬法

for (int i = 3; i <= n; i++) {
int cur = prevI + prevII; // 当前 = 前一步 + 前两步
prevII = prevI;
prevI = cur;
}
return prevI;
}


卡丹算法

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
26
/**
* 给定整数数组 nums(含负数),找连续子数(至少含 1 个元素),使其元素和最大,返回该最大和。
* 示例:[-2,1,-3,4,-1,2,1,-5,4] → 最大和为 6(对应子数组 [4,-1,2,1])
*
* 以当前元素结尾的最大子数组和:dp[i] = max(dp[i-1] + a[i], a[i])
* 而最大的全局子数组和还需要和前一个最大子数组和进行比较
* 即 dp[0] = a[0], globalMax = max(dp[i], globalMax)
*/
public class KadaneTest {

public static void main(String[] args) {
int[] array = {-2,1,-3,4,-1,2,1,-5,4};
System.out.println(maxSubArray(array)); // 输出 6,对应的最大子数组 [4,-1,2,1]
}

public static int maxSubArray(int[] nums) {
int dp = nums[0]; // dp[i-1]:以 i-1 结尾的最大子数组和
int globalMax = nums[0]; // 全局最大

for (int i = 1; i < nums.length; i++) {
dp = Math.max(dp + nums[i], nums[i]); // dp[i]
globalMax = Math.max(globalMax, dp);
}
return globalMax;
}
}


最长公共子序列

不连续的情况

最长公共子序列(LCS,Longest Common Subsequence):给定两个字符串(或序列)text1 和 text2,找出它们的最长公共子序列的长度。注意是子序列,不要求连续,但要求相对顺序一致。例如:

1
2
3
4
5
6
7
8
9
text1 = "abcde"
text2 = "ace"
↑ ↑ ↑
LCS = "ace",长度 = 3


text1 = "abc"
text2 = "def"
LCS = "",长度 = 0

这是一个典型的二维 DP 问题,因为状态同时依赖两个序列的位置——需要一张二维表来记录 “看到 text1 的前 i 个字符、text2 的前 j 个字符时,LCS 有多长”。

状态定义

这里 i、j 从 1 开始,对应字符串下标 i-1、j-1

1
dp[i][j] = text1 的前 i 个字符 与 text2 的前 j 个字符 的 LCS 长度

状态转移方程

1
2
3
4
5
6
7
# 字符相等 → 两个都往前退一格,LCS 长度 +1
字符相等:text1[i-1] == text2[j-1]
转移方程:dp[i][j] = dp[i-1][j-1] + 1

# 字符不等 → 要么退 text1 的一个字符,要么退 text2 的一个字符,取两者中较大的
字符不等:text1[i-1] != text2[j-1]
转移方程:dp[i][j] = max(dp[i-1][j], dp[i][j-1])

用示例走一遍:(text1 = “abcde”,text2 = “ace”),右下角 dp[5][3] = 3

∅ a c e
∅ 0 0 0 0
a 0 1 1 1
b 0 1 1 1
c 0 1 2 2
d 0 1 2 2
e 0 1 2 3

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void main(String[] args) {
String text1 = "abcde";
String text2 = "ace";
int result = lcs(text1, text2);
System.out.println(result); // 3
}

public static int lcs(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}

如果要输出具体的 LCS 字符串:

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
26
27
28
29
30
31
32
33
34
/**
* 当前位置 (i, j):
* 如果 text1[i-1] == text2[j-1] → 字符属于 LCS,i--, j--
* 否则如果 dp[i-1][j] > dp[i][j-1] → i--
* 否则 → j--
* 直到 i==0 或 j==0 停止
*/
public static String lcsString(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];

// 填表
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1.charAt(i - 1) == text2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

// 回溯
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--; j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}


连续的情况

子串和子序列的唯一区别就是:子串要求连续。这个”连续”的约束,直接让 DP 的转移方程变简单了。

状态转移方程:

1
2
text1[i-1] == text2[j-1]  →  dp[i][j] = dp[i-1][j-1] + 1
text1[i-1] != text2[j-1] → dp[i][j] = 0 ← 断了!归零!

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int lcs2(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
maxLen = Math.max(maxLen, dp[i][j]);
}
// 不等时 dp[i][j] 默认为 0,不用写
}
}
return maxLen;
}

如果要输出具体子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static String lcsString2(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
int maxLen = 0;
int endIndex = 0; // text1 中公共子串的结束位置

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i - 1;
}
}
}
}
return text1.substring(endIndex - maxLen + 1, endIndex + 1);
}


零钱兑换问题

给定不同面额的硬币 coins 和一个总金额 amount,计算凑成总金额所需的最少硬币个数。如果无法凑成,返回 -1。每种硬币可以无限次使用(完全背包)。比如:

1
2
3
4
5
coins = [1, 2, 5], amount = 11
→ 最少需要 3 枚硬币:11 = 5 + 5 + 1

coins = [2], amount = 3
→ 无法凑成,返回 -1

为什么用 DP?这是因为 “凑 amount 最少需要几枚硬币”——这个最优解可以拆成子问题:凑 amount 的最优解 = 选一枚硬币 coin,然后凑 amount - coin 的最优解 + 1,而凑 amount - coin 的最优解,和凑 amount 的结构完全一样——这是典型的最优子结构 + 重叠子问题。

状态定义

1
dp[i] = 凑成金额 i 所需的最少硬币数

状态转移方程

1
2
# 含义:凑金额 i,我选一枚 coin,剩下的 i - coin 用之前算好的最优方案凑。
dp[i] = min( dp[i - coin] + 1 ) 对所有 coin <= i

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];

// 初始化为 amount+1(比理论最大值还大,表示"不可达")
Arrays.fill(dp, amount + 1);
dp[0] = 0;

// 从 1 元开始,一步步算到目标金额,每一步都尝试用所有硬币,选最省的方案
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}

return dp[amount] > amount ? -1 : dp[amount];
}


背包问题

背包问题是动态规划里最大、最系统的一个家族。什么是背包问题呢?就是给你一堆物品,每个物品有重量和价值。给你一个容量有限的背包。问:怎么选物品,使得总重量不超过背包容量,且总价值最大?不同变体区别就在于:每个物品能选几次。


0/1 背包

问题描述:

  • n 个物品,每个物品只能选一次(选或不选)
  • 重量数组 weight[],价值数组 value[]
  • 背包容量 W
  • 求最大价值

具体示例:

1
2
3
4
weight = [1, 3, 4]
value = [15, 20, 30]
W = 4
→ 选物品0(重1,值15) + 物品1(重3,值20) = 重4, 值35

状态定义:

1
dp[i][j] = 考虑前 i 个物品,背包容量为 j 时,能获得的最大价值

状态转移方程:

1
2
3
4
# 对第 i 个物品(重量 weight[i-1]、价值 value[i-1]),两种选择:
# 不选 dp[i-1][j]
# 选(要求 j >= weight[i-1]) dp[i-1][j-weight[i-1]] + value[i-1]
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1])

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int knapsack01(int[] weight, int[] value, int W) {
int n = weight.length;
int[][] dp = new int[n + 1][W + 1];

for (int i = 1; i <= n; i++) {
for (int j = 0; j <= W; j++) {
if (j >= weight[i - 1]) {
dp[i][j] = Math.max(
dp[i - 1][j],
dp[i - 1][j - weight[i - 1]] + value[i - 1]
);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][W];
}

空间优化:滚动数组 O(W)。dp[i] 只依赖 dp[i-1],而且只用到了更小的容量(j 往小的方向看),所以可以用一维数组 + 从后往前遍历。为什么从后往前? 因为从前往后会覆盖 dp[j - weight[i]] 的值,导致同一个物品被选了多次(变成完全背包了)。

1
2
3
4
5
6
7
8
9
10
public static int knapsack01(int[] weight, int[] value, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
for (int j = W; j >= weight[i]; j--) { // ← 从后往前!
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}


完全背包

和 0/1 背包一样,但每个物品可以选无限次。

1
2
3
4
weight = [1, 3, 4]
value = [15, 20, 30]
W = 4
→ 选 4 个物品0 = 重4, 值60 (每个物品无限用)

转移方程

1
2
# 注意!选了之后还是 dp[i](不是 dp[i-1]),因为可以再选。
dp[i][j] = max(dp[i-1][j], dp[i][j-weight[i-1]] + value[i-1])

代码实现(一维优化版)

1
2
3
4
5
6
7
8
9
10
public static int unboundedKnapsack(int[] weight, int[] value, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= W; j++) { // ← 从前往后!
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
return dp[W];
}


多重背包

和 0/1 背包一样,但每个物品不是只能选 1 次,也不是无限次,而是有数量上限 count[i]。问怎么选总价值最大?

1
2
3
物品0:重量 2,价值 3,数量 2 件
物品1:重量 3,价值 4,数量 3 件
背包容量 W = 10

最直觉的解法:直接拆成 0/1 背包,每个物品有几件,就当成几个独立物品丢进 0/1 背包:

1
2
物品0 有 2 件 → 当成 2 个"重量2、价值3"的独立物品
物品1 有 3 件 → 当成 3 个"重量3、价值4"的独立物品

总共 5 个物品,直接跑 0/1 背包。

1
2
3
4
5
6
7
8
// 暴力拆分
for (int i = 0; i < n; i++) {
for (int k = 0; k < count[i]; k++) {
for (int j = W; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
}
}

能跑通,但太慢了。时间复杂度:O(W × 所有物品数量之和)。如果某个物品有 10000 件,就傻了。怎么优化呢?可以使用二进制优化的思想,不需要把 13 件物品拆成 13 个独立的,只需要拆成 4 个”打包好的组”,就能组合出 0~13 件的任何选择。任何数字都可以用二进制位表示。比如 13:

1
13 = 8 + 4 + 1    ← 但 1+2+4+8 = 15 > 13,不行

正确拆法:1, 2, 4, 6

1
2
3
4
5
6
7
8
9
10
11
12
13
1 = 1
2 = 2
3 = 1+2
4 = 4
5 = 1+4
6 = 2+4
7 = 1+2+4
8 = 2+6
9 = 1+2+6
10 = 4+6
11 = 1+4+6
12 = 2+4+6
13 = 1+2+4+6

0~13 的任意数量都能用这几个”包”的组合凑出来!具体的拆法就是不断取 2 的幂,直到剩下的不够下一个幂:

1
2
3
4
5
6
count = 13
取 1 → 剩 12
取 2 → 剩 10
取 4 → 剩 6
取 8?不行(8 > 6),把剩下的 6 作为一个包
→ 拆成:1, 2, 4, 6

每个包的重量和价值乘以对应的倍数:

1
2
3
4
5
6
原物品:重量 w,价值 v,数量 13
拆成:
包1:重量 1*w,价值 1*v
包2:重量 2*w,价值 2*v
包3:重量 4*w,价值 4*v
包4:重量 6*w,价值 6*v

然后把这 4 个包当成 0/1 背包里的 4 个独立物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int multipleKnapsack(int[] weight, int[] value, int[] count, int W) {
int[] dp = new int[W + 1];

for (int i = 0; i < weight.length; i++) {
int w = weight[i], v = value[i], c = count[i];

// 二进制拆分
for (int k = 1; c > 0; k *= 2) {
int take = Math.min(k, c); // 这一包的大小
c -= take; // 剩余数量

int packW = take * w; // 这一包的重量
int packV = take * v; // 这一包的价值

// 当成 0/1 背包的一个物品
for (int j = W; j >= packW; j--) {
dp[j] = Math.max(dp[j], dp[j - packW] + packV);
}
}
}
return dp[W];
}


分组背包

如果说前面的背包问题是在“数量”上做文章(1个、无限个、有限个),那么分组背包则是改变了物品之间的互斥关系。有 N​ 组物品和一个容量为 W 的背包。第 ​i 组中包含若干个物品,这些物品相互之间是互斥的(即每组里面最多只能选择一个物品装入背包)。 每件物品有自己的重量 weight 和价值 value​。求在不超过背包容量的情况下,能装入的最大总价值。

状态定义,设 $dp[i][j]$ 表示:从前 $i$ 组物品中选择,在容量限制为 $j$ 的背包下所能获得的最大价值。

状态转移方程,当我们面对第 $i$ 组物品时,我们的决策分成两部分:

  • 不选第 $i$ 组的任何物品:价值继承自前 $i-1$ 组,即 $dp[i-1][j]$。
  • 选择第 $i$ 组中的某一个物品 $k$:既然选了第 $i$ 组的物品 $k$(其重量为 $w_k$,价值为 $v_k$),那么背包容量要扣除 $w_k$,且不能再选该组其他物品,其价值为 $dp[i-1][j - w_k] + v_k$。因此,状态转移方程为:$dp[i][j] = \max\left( dp[i-1][j], \ \max_{k \in \text{group } i} (dp[i-1][j - weight[k]] + value[k]) \right)$

和前面的背包类似,二维数组可以压缩为一维数组 $dp[j]$。但分组背包的循环嵌套顺序至关重要,稍微写错就会导致逻辑崩塌。

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
26
27
28
29
public class GroupedKnapsack {

static class Item {
int weight;
int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}

public static int groupKnapsack(int W, List<List<Item>> groups) {
int[] dp = new int[W + 1];

// 1. 遍历每一组
for (List<Item> group : groups) {
// 2. 倒序遍历背包容量
for (int j = W; j >= 0; j--) {
// 3. 遍历组内每个物品,看选哪个收益最高
for (Item item : group) {
if (j >= item.weight) {
dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
}
}
}
}
return dp[W];
}
}


股票买卖模型

I 型:交易一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 买卖股票的最佳时机 (Best Time to Buy and Sell Stock)
* 题目描述:
* 给定股票价格数组,计算一次交易的最大利润。
* 示例:
* 输入:[7,1,5,3,6,4]
* 输出:5(1买6卖)
* 最优解思路:
* 遍历价格数组,维护历史最低价 min_price 和最大利润 max_profit。
* 时间复杂度:O(n)
* 空间复杂度:O(1)
*/
public int maxProfitI(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // 更新历史最低价
} else {
maxProfit = Math.max(maxProfit, price - minPrice); // 尝试卖出
}
}
return maxProfit;
}

II 型:多次交易

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
* 买卖股票 II
* 可以多次交易,贪心,只要涨就卖
*/
public int maxProfitII(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}

III 型:最多 k 次交易

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
26
27
28
29
30
31
32
33
34
35
36
/**
* 买卖股票
* 最多 k 次交易,求最大利润。这是股票系列的 "终极 DP 版"。
*
* 状态定义
* buy[j] = 完成 j 次交易(处于买入状态)的最大利润
* sell[j] = 完成 j 次交易(处于卖出状态)的最大利润
* 为什么需要"买入状态"和"卖出状态"分开?因为一次交易 = 一次买 + 一次卖,必须按顺序来。
*
* 状态转移方程
* buy[j] = max(buy[j], sell[j-1] - price) // 第 j 次买入
* sell[j] = max(sell[j], buy[j] + price) // 第 j 次卖出
* 要第 j 次买入,必须先有 j-1 次卖出;要第 j 次卖出,必须先有 j 次买入。
*/
public int maxProfitIII(int k, int[] prices) {
if (prices.length == 0) return 0;

// 优化:k 足够大时,等价于可以无限次交易,用贪心
if (k >= prices.length / 2) {
return maxProfitII(prices);
}

int[] buy = new int[k + 1];
int[] sell = new int[k + 1];

Arrays.fill(buy, Integer.MIN_VALUE); // 买入状态初始为负无穷(还没买入)
// sell 初始为 0(一次都没卖,利润 0)

for (int price : prices) {
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - price);
sell[j] = Math.max(sell[j], buy[j] + price);
}
}
return sell[k];
}


附.完整代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
import java.util.Arrays;
import java.util.List;

public class DpTest {

// ---- 斐波那契数列 ----
public static int fib(int n) {
if (n == 0 || n == 1) return n;

int dp1 = 1, dp2 = 0;
int dp = 0;
for (int i = 2; i <= n; i++) {
dp = dp1 + dp2;
dp2 = dp1;
dp1 = dp;
}
return dp;
}


// ---- 找出最大的那个连续子序列的和 ----
public static int maxSubArraySum(int[] array) {
int dp = array[0];
int globalMax = array[0];

for (int i = 1; i < array.length; i++) {
dp = Math.max(dp + array[i], array[i]);
globalMax = Math.max(dp, globalMax);
}
return globalMax;
}


// ---- 最长的公共字串 I(不连续情况)----
public static String lcsString01(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];

// 填表
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
if (text1.charAt(i - 1) == text2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

// 回溯
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
sb.append(text1.charAt(i - 1));
i--; j--;
} else if (dp[i - 1][j] > dp[i][j - 1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}

// 最长的公共字串 II(连续情况)
public static String lcsString02(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m+1][n+1];
int maxLen = 0;
int endIndex = 0;

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i-1) == text2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i-1;
}
}
}
}
return text1.substring(endIndex-maxLen+1, endIndex+1);
}


// ---- 零钱兑换问题 ----
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;

for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (i >= coin) {
dp[i] = Math.min(dp[i], dp[i-coin] + 1);
}
}
}

return dp[amount] > amount ? -1 : dp[amount];
}


// ---- 背包问题 I(0-1 背包)----
public static int knapsack01(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
for (int j = capacity; j >= weight[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[capacity];
}

// 背包问题 II(完全背包)
public static int knapsack02(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
for (int j = weight[i]; j <= capacity; j++) {
dp[j] = Math.max(dp[j], dp[j-weight[i]] + value[i]);
}
}
return dp[capacity];
}

// 背包问题 III(多重背包)
public static int knapsack03(int[] weight, int[] value, int[] count, int capacity) {
int[] dp = new int[capacity+1];
for (int i = 0; i < weight.length; i++) {
int w = weight[i], v = value[i], c = count[i];
for (int k = 1; c > 0; k*=2) {
int take = Math.min(k, c);
c -= take;

int packW = take * w;
int packV = take * v;

for (int j = capacity; j >= packW; j--) {
dp[j] = Math.max(dp[j], dp[j-packW] + packV);
}
}
}
return dp[capacity];
}

// 背包问题 IV(分组背包)
static class Item {
int weight;
int value;
public Item(int weight, int value) {
this.weight = weight;
this.value = value;
}
}
public static int knapsack04(List<List<Item>> groups, int capacity) {
int[] dp = new int[capacity + 1];
for (List<Item> group : groups) {
for (int j = capacity; j >= 0; j--) {
for (Item item : group) {
if (j >= item.weight) {
dp[j] = Math.max(dp[j], dp[j - item.weight] + item.value);
}
}
}
}
return dp[capacity];
}


// ---- 股票最大收益 I(交易一次)----
public int maxProfitI(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
if (price < minPrice) {
minPrice = price; // 更新历史最低价
} else {
maxProfit = Math.max(maxProfit, price - minPrice); // 尝试卖出
}
}
return maxProfit;
}

// 股票最大收益 II(交易多次)
public int maxProfitII(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}

// 股票最大收益 III(最多 k 次交易)
public int maxProfitIII(int k, int[] prices) {
if (prices.length == 0) return 0;

// 优化:k 足够大时,等价于可以无限次交易,用贪心
if (k >= prices.length / 2) {
return maxProfitII(prices);
}

int[] buy = new int[k + 1];
int[] sell = new int[k + 1];

Arrays.fill(buy, Integer.MIN_VALUE); // 买入状态初始为负无穷(还没买入)
// sell 初始为 0(一次都没卖,利润 0)

for (int price : prices) {
for (int j = 1; j <= k; j++) {
buy[j] = Math.max(buy[j], sell[j - 1] - price);
sell[j] = Math.max(sell[j], buy[j] + price);
}
}
return sell[k];
}
}

RESTful 简介以及基于 SSM 的完整案例

什么是 RESTful

对于 RESTful(Representational State Transfer 表征状态转移),很多教科书把它讲得很玄乎。但其实我们可以把 RESTful 看作是 Web 开发中的一套 “行为准则” 或 “普通话标准”。它的本质就是:用最标准的 HTTP 动作,去操作服务器上的 “资源”。