54. 螺旋矩阵

通过定义上下左右四个边界(top、bottom、left、right),每次按顺序遍历一圈:先左→右,再上↓下,然后右→左,最后下↑上,遍历后收缩边界,直到所有元素被访问,避免使用额外空间,逻辑清晰高效。

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
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) return res;

int top = 0, bottom = matrix.length - 1;
int left = 0, right = matrix[0].length - 1;

while (top <= bottom && left <= right) {
// 左 → 右
for (int col = left; col <= right; col++) {
res.add(matrix[top][col]);
}
top++;

// 上 ↓ 下
for (int row = top; row <= bottom; row++) {
res.add(matrix[row][right]);
}
right--;

// 右 → 左(需要检查 top 和 bottom 是否交叉)
if (top <= bottom) {
for (int col = right; col >= left; col--) {
res.add(matrix[bottom][col]);
}
bottom--;
}

// 下 ↑ 上(需要检查 left 和 right 是否交叉)
if (left <= right) {
for (int row = bottom; row >= top; row--) {
res.add(matrix[row][left]);
}
left++;
}
}

return res;
}
}

48. 旋转图像

✅ 方法:先转置,再翻转

步骤 1:矩阵转置(Transpose)

  • 将行列互换,即 matrix[i][j] ↔ matrix[j][i](只交换对角线上的上三角部分)

步骤 2:水平翻转(Horizontal Reverse)

  • 每一行进行左右翻转,即 matrix[i][j] ↔ matrix[i][n - 1 - j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = tmp;
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}
}

240. 搜索二维矩阵 II

“从右上角开始查找,逐行逐列缩小搜索区域。”

为啥选右上角?

  • 如果 matrix[row][col] == target,找到了,返回 true
  • 如果 matrix[row][col] > target,说明当前列不可能包含目标值,往左移一列
  • 如果 matrix[row][col] < target,说明当前行不可能包含目标值,往下移一行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
int col = matrix[0].length - 1;

while (row < matrix.length && col >= 0) {
int val = matrix[row][col];
if (val == target) {
return true;
} else if (val > target) {
col--;
} else {
row++;
}
}

return false;
}
}

148. 排序链表

我使用归并排序来排序链表。通过快慢指针将链表分成两半,递归地分别排序后,再合并两个有序链表。合并过程每次都以线性方式完成,总时间复杂度是 O(n log n),空间是 O(log n) 用于递归调用栈,非常适合链表。

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
	class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;

ListNode slow = head, fast = head, prev = null;
// 1. 快慢指针找中点,断开链表
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;

// 2. 分别排序左右两部分
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);

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

private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), tail = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
tail.next = l1;
l1 = l1.next;
} else {
tail.next = l2;
l2 = l2.next;
}
tail = tail.next;
}
tail.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}

23. 合并 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
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) {
return null;
}

// 小根堆,比较节点值
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val);

for (ListNode node : lists) {
if (node != null) {
// 插入每个头节点
queue.offer(node);
}
}

ListNode dummy = new ListNode(0);
ListNode tail = dummy;

while (!queue.isEmpty()) {
ListNode top = queue.poll();
tail.next = top;
tail = tail.next;
// 插入链表的下一个节点
if (top.next != null) {
queue.offer(top.next);
}
}

return dummy.next;
}
}

34. 在排序数组中查找元素的第一个和最后一个位置

我们用两次二分查找:

  1. target左边界(第一个出现的位置)
  2. target右边界(最后一个出现的位置)
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
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = binarySearch(nums, target, true); // 找左边界
int right = binarySearch(nums, target, false) - 1; // 找右边界(注意要减1)

// 检查结果是否有效
if (left <= right && left < nums.length && nums[left] == target && nums[right] == target) {
return new int[]{left, right};
}

return new int[]{-1, -1};
}

// lower = true 找左边界,false 找右边界(即第一个 > target 的位置)
private int binarySearch(int[] nums, int target, boolean lower) {
int left = 0, right = nums.length - 1, ans = nums.length;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] > target || (lower && nums[mid] >= target)) {
right = mid - 1;
ans = mid;
} else {
left = mid + 1;
}
}
return ans;
}
}

33. 搜索旋转排序数组

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
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;

while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}

// 左半边有序
if (nums[left] <= nums[mid]) {
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1; // target 在左边
} else {
left = mid + 1; // target 在右边
}
}
// 右半边有序
else {
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1; // target 在右边
} else {
right = mid - 1; // target 在左边
}
}
}

return -1; // 没找到
}
}

75. 颜色分类

遍历 nums[mid]

  • 如果 nums[mid] == 0
    • 把它和 nums[low] 交换,low++mid++
  • 如果 nums[mid] == 1
    • 什么都不做,mid++
  • 如果 nums[mid] == 2
    • 把它和 nums[high] 交换,high--,但mid 不动(因为换过来的还没处理)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public void sortColors(int[] nums) {
int low = 0, mid = 0, high = nums.length - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums, low, mid);
low++;
mid++;
} else if (nums[mid] == 1) {
mid++;
} else {
swap(nums, mid, high);
high--;
}
}
}

private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}

31. 下一个排列

✅ 主要分三步:

  1. 从后往前找到第一个降序位置,记为 i

    如果找不到,说明是最大的排列,直接整体反转即可。

  2. 再从后往前找到一个比 nums[i] 大的最小的数,记为 j,然后 交换 i 和 j

  3. 最后反转 i+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
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
// 1. 找第一个下降点
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}

if (i >= 0) {
// 2. 找右边第一个比 nums[i] 大的数
int j = nums.length - 1;
while (j >= 0 && nums[j] <= nums[i]) {
j--;
}
swap(nums, i, j); // 交换
}

// 3. 反转后半部分
reverse(nums, i + 1);
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

private void reverse(int[] nums, int start) {
int end = nums.length - 1;
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}

295. 数据流的中位数

中位数的特性是:一半数比它小,一半数比它大

我们可以维护两个堆:

  • 大顶堆(maxHeap):存较小一半的数字
  • 小顶堆(minHeap):存较大一半的数字

并保持以下两个条件:

  1. maxHeap.size() == minHeap.size()maxHeap.size() 多 1
  2. 所有 maxHeap 中的数 ≤ 所有 minHeap 中的数
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
class MedianFinder {
private PriorityQueue<Integer> maxHeap;
private PriorityQueue<Integer> minHeap;

public MedianFinder() {
maxHeap = new PriorityQueue<>((a, b) -> b - a);
minHeap = new PriorityQueue<>();
}

public void addNum(int num) {
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
if (maxHeap.size() < minHeap.size()) {
maxHeap.offer(minHeap.poll());
}
}

public double findMedian() {
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) / 2.0;
} else {
return maxHeap.peek();
}
}
}

4. 寻找两个正序数组的中位数

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
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}

int m = nums1.length;
int n = nums2.length;
int left = 0, right = m;

while (left <= right) {
int i = left + (right - left) / 2;
int j = (m + n + 1) / 2 - i;

int nums1LeftMax = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
int nums2LeftMax = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
if ((m + n) % 2 == 0) {
return (Math.max(nums1LeftMax, nums2LeftMax) +
Math.min(nums1RightMin, nums2RightMin)) / 2.0;
} else {
return Math.max(nums1LeftMax, nums2LeftMax);
}
} else if (nums1LeftMax > nums2RightMin) {
right = i - 1;
} else {
left = i + 1;
}
}
return 0;
}
}