# 数组、链表、栈和队列相关的题目
# 数组
# 合并两个有序数组 LeetCode 88
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
解 1
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] arr = new int[m + n];
int j = 0;
int k = 0;
// nums1 没有数据
if (m == 0) {
for (int i = 0; i < nums1.length; i++) {
nums1[i] = nums2[i];
}
} else if (n == 0) { // nums2 没有数据
} else { // nums1 和 nums2 都有数据
for (int i = 0; i < arr.length; i++) {
// nums2 已经排完
if (k >= n) {
arr[i] = nums1[j];
j++;
} else if (j < m && nums1[j] < nums2[k]) { // 都没排好 或 nums1 已经排完
arr[i] = nums1[j]; // nums1 当前小
j++;
} else {
arr[i] = nums2[k]; // nums2 当前小
k++;
}
}
for (int i = 0; i < arr.length; i++) {
nums1[i] = arr[i];
}
}
}
}
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
解 2
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
for (int k = m + n - 1; k >= 0; k--) {
if (j < 0 || (i >= 0 && nums1[i] >= nums2[j])) { // nums2 已经排完 或 i > 0 时可以继续放 nums1（防止越界）
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 删除有序数组中的重复项 LeetCode 26
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
2
3
4
5
6
7
8
示例 1
输入：nums = [1,1,2]
输出：2, nums = [1,2]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
解 1
public int removeDuplicates(int[] nums) {
int index = 0;
// 双指针判断
// 外层循环固定指针 i
out:
for (int i = 0; i < nums.length; i++) {
// 内层循环固定指针 j
in:
for (int j = i + 1; j <nums.length; j++) { // 对于每一个 i, 从当前 i 的下一个开始和它比
if (nums [i] >= nums[j]) { // 如果当前 i >= 当前 j，表示当前 i 是经过覆盖的
if (j == nums.length - 1) { // j 遍历过剩下所有元素，都没有发现需要替换，说明已经寻找完毕
break out; // 退出外层循环
} else { // j 还没有遍历完毕剩下所有元素，继续遍历
continue;
}
} else if (nums[i] < nums[j]) { // 当前 i < 当前 j，说明找到了需要替换的元素
nums[i + 1] = nums [j]; // 将 j 覆盖当前 i 的下一个元素
index++; // 有序无重复序列 +1
continue out; // 继续外层循环，即与当前 i 相同所有元素已经判断完毕，i 进下一位
}
}
}
return index + 1; // 输出循环是 <, 所以手动 + 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
解 2
public int removeDuplicates(int[] nums) {
int n = 0;
for (int i = 0; i < nums.length; i++) {
if (i == 0 || nums[i] != nums [i - 1]) { // 只要和前一个不一样 或者是第一个元素，覆盖
nums[n] = nums[i]; // 覆盖到有序部分后面
n++; // 有序部分 +1
}
}
return n;
}
2
3
4
5
6
7
8
9
10
# 移动零 LeetCode 283
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
示例
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
解 1
public void moveZeroes(int[] nums) {
int temp = -1;
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (nums[j] == 0 && j + 1 < nums.length) {
temp = nums[j + 1];
nums[j] = temp;
nums[j + 1] = 0;
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
解 2
public void moveZeroes(int[] nums) {
int n = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) { // 非 0 项需要，覆盖到前非 0 段
nums[n] = nums[i];
n++;
}
}
// 补 0
while (n < nums.length) {
nums[n] = 0;
n++;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 链表
# 反转链表 LeetCode 206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2
输入：head = [1,2]
输出：[2,1]
示例 3
输入：head = []
输出：[]
解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode last = null;
while (head != null) {
ListNode nextHead = head.next; // 记录下一个结点
head.next = last; // 将当前结点指向上一个结点
last = head; // 将当前结点标记为 last
head = nextHead; // 继续处理下一个结点
}
return last;
}
}
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
也可以理解为将当前头拆下，赋值给新链表 last, 然后将新链表的头指定为当前结点。即头删旧链表；头插新链表
# K 个一组翻转链表 LeetCode 25
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
- 利用常数额外空间
- 使用实际的结点交换而不是内部值变化
示例 1
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]
示例 2
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]
示例 3
输入：head = [1,2,3,4,5], k = 1
输出：[1,2,3,4,5]
示例 4
输入：head = [1], k = 1
输出：[1]
解
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 建立保护结点防止为空
ListNode protect = new ListNode(0, head);
// 找到每组的开头和结尾，按组遍历反转
ListNode last = protect; // 上一组的结尾
while (head != null) {
ListNode end = getEnd(head, k); // 获取本组的结尾位置
// 边界处理
if (end == null) { // 到结尾不够一组
break;
}
// 反转链表
ListNode nextGroupHead = end.next; // 保存下一组的头，后续反转后会被修改防止丢失
reverseList(head, end); // 处理 head 到 end 中间的反转
last.next = end; // 上一组的 next 指向新头(前 end)
head.next = nextGroupHead; // 本组的新尾(前 head)指向下一组的头
// 分组遍历
last = head; // 将当前标记为 last
head = nextGroupHead; // 继续处理下一组
}
// 返回结果
return protect.next;
}
// 走 K 步后的位置（每组的结尾）
public ListNode getEnd(ListNode head, int k) {
while (head != null) {
k--;
if (k == 0) {
break;
}
head = head.next;
}
return head;
}
// 反转链表
public void reverseList(ListNode head, ListNode end) {
// 当步长为 1
if (head == end) {
return;
}
ListNode last = head; // 从 head 开始反转，直接将 last 标记为当前 head
head = head.next; // 只修改 n-1 个链接
while (head != end) {
ListNode nextHead = head.next;
head.next = last;
last = head;
head = nextHead;
}
// 手动修改本组结尾的指向
end.next = last;
}
}
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
# 环形链表 LeetCode 141
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
- 使用常量空间复杂度
示例 1
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
解
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
// 快慢指针
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next; // 快指针每次走两步
head = head.next; // 慢指针每次走一步
if (fast == head) { // 如果快指针有机会追上满指针说明有环
return true;
}
}
return false; // 如果快指针先遍历完且未与慢指针相遇说明无环
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 环形链表 II LeetCode 142
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
- 不允许修改给定的链表。
- 使用常量空间复杂度
示例 1
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
[分析]
设置快慢指针，快指针每次走两步，慢指针每次走一步
假定从头结点开始到入环结点距离为 l
从入环结点到环内相遇结点距离为 p
环长为 r
在环内，相遇点到入环点距离为 r-p
当两指针相遇时，有 2(l+p) = l+p+kr，其中 k 为绕环趟数
即慢指针走到相遇点共计 l+p 个结点，快指针共计 l+p+kr 个结点。因为快指针每次走两步，所以当慢指针走两倍时，两个指针走过的结点总数相等。
化简有 l = kr-p
提出一个 r 有 l = (k-1)r+r-p
理解为从头结点到入环结点的距离，等同于从相遇点到入环点的距离加上 k-1 圈环内循环。即 l 与 r-p 的关系是 k-1 倍
那么如果此时从头结点和相遇点分别设置一个慢指针，每次同时移动一次，它们必定相遇在入环处
# 栈和队列
# 有效的括号 LeetCode 20
解
class Solution {
public boolean isValid(String s) {
Stack stack = new Stack();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
stack.push(c);
} else {
if (stack.empty()) {
return false;
}
char tmp = (char) stack.pop();
switch (c) {
case ')':
if (tmp != '(') {
return false;
}
break;
case ']':
if (tmp != '[') {
return false;
}
break;
case '}':
if (tmp != '{') {
return false;
}
break;
}
}
}
return stack.empty();
}
}
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
# 逆波兰表达式求值 LeetCode 150
解
class Solution {
public int evalRPN(String[] tokens) {
Stack stack = new Stack();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
int optB = (int) stack.pop();
int optA = (int) stack.pop();
stack.push(calc(optA, optB, token));
} else {
stack.push(Integer.parseInt(token));
}
}
return (int) stack.pop();
}
public int calc (int optA, int optB, String token) {
if (token.equals("+")) return optA + optB;
if (token.equals("-")) return optA - optB;
if (token.equals("*")) return optA * optB;
if (token.equals("/")) return optA / optB;
return 0;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 基本计算器 LeetCode 224
解
class Solution {
public int calculate(String s) {
Stack opts = new Stack();
List<String> tokens = new ArrayList<String>();
boolean numStarted = false;
boolean needZero = true;
// 将字符串转为 Int
int value = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
value = value * 10 + c - '0';
numStarted = true;
continue;
} else if (numStarted) {
tokens.add(String.valueOf(value));
numStarted = false;
needZero = false;
value = 0;
}
if (c == ' ') continue;
// 处理运算符
if (c == '(') {
opts.push(c);
needZero = true;
continue;
}
if (c == ')') {
while ((char)opts.peek() != '(') {
tokens.add(String.valueOf((char)opts.pop()));
}
opts.pop();
needZero = false;
continue;
}
// 处理 +-*/
if (needZero) {
tokens.add("0");
}
while (!opts.empty() && getRank((char) opts.peek()) >= getRank(c)) {
tokens.add(String.valueOf((char) opts.pop()));
}
opts.push(c);
needZero = true;
}
if (numStarted) {
tokens.add(String.valueOf(value));
}
while (!opts.empty()) {
tokens.add(String.valueOf((char) opts.pop()));
}
return evalRPN(tokens.toArray(new String[tokens.size()]));
}
public int getRank(char c) {
if (c == '+' || c == '-') {
return 1;
}
if (c == '*' || c == '/') {
return 2;
}
return 0;
}
public int evalRPN(String[] tokens) {
Stack stack = new Stack();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
int optB = (int) stack.pop();
int optA = (int) stack.pop();
stack.push(calc(optA, optB, token));
} else { // 是数字
stack.push(Integer.parseInt(token));
}
}
return (int) stack.pop();
}
public int calc(int optA, int optB, String token) {
if (token.equals("+")) return optA + optB;
if (token.equals("-")) return optA - optB;
if (token.equals("*")) return optA * optB;
if (token.equals("/")) return optA / optB;
return 0;
}
}
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
← 最大子列和 数组、链表、栈和队列相关的题目 →