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);
}
}
}