• 完成了几道数组的 mid
• 依旧看后端

合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi]  请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间

思路解析

为了方便合并区间，我们将数组以左端点从小到大排序 排序后，第一个区间 intervals[0] 是第一个正在合并的大区间。 它的左端点是固定在 intervals[0][0] 不动的，但它的右端点 intervals[0][1] 只是暂时的 接下来继续向右遍历 以 [1,3],[2,6],[8,10],[15,18] 区间为例，实现具体算法：

1. 将 intervals[0] 添加至 ans
2. 遍历到 intervals[1] = [2,6] 我们发现左端点 2 < 当前合并区间的右端点3，意味着可以合并。且 右端点 3 < 6 ，更新当前合并区间的右端点为 6
3. 继续遍历到intervals[2] = [8,10]显然，左端点 8 > 当前合并区间右端点 6，无法合并，两个区间也没有相交，于是当前合并区间[1,6]就固定了
4. 重复上述操作，更新答案

代码实现

class Solution {
	public int[] merge(int[][] intervals) {
		Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
		List<int[]> ans = new ArrayList<>();
		for (int[] p : intervals) {
			int m = ans.size();
			if (m > 0 && p[0] <= ans.get(m - 1)[1]) { // 可以合并条件
				ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]); // 更新右端点
			} else {        // 不相交
				ans.add(p); // 添加合并区间
			}
		}
		return ans.toArray(new int[ans.size()][])
	}
}

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

思路解析

使用额外数组思路

我们用一个例子来辅助理解： 假设数组里的数字是一排人，现在游戏规则是：每个人都要往右边移动 k 个座位。

但这排座位不是无限长的，只有 n 个座位（下标从 0 到 n-1）。 如果坐在最后面的人还要往右移，没座位了怎么办？ 规则规定：掉出最右边的人，要从最左边重新排进来（形成一个圆环）

于是我们就能理解 公式中 (i + k) % n 的含义了： 我们把它拆开：

1. i：这是这个人现在的座位号。

2. i + k：这是他理想中想去的座位号（也就是往右走 k 步）。

3. % n（取模运算）：这是“时空穿梭机”**。

   • 如果 i + k 没有超过总座位数 n，取模后还是 i + k，直接坐下。
   • 如果 i + k 超过了总座位数（走到了外面），取余数的操作就能让他完美地**“绕回起点”**。

最终时间复杂度和空间复杂度都是 O(n)

代码实现

class Solution {
	public void rotate(int[] nums, int k) {
		int n = nums.length;
		int[] newArr = new int[n];
		for (int i = 0; i < n; ++i) {
			newArr[(i + k) % n] = nums[i];
		}
		System.arraycopy(newArr, 0, nums, 0, n); // 将 newArr 数组复制回 nums 里
	}
}

翻转数组

步骤分解：

动作分解

假设数组是一排数字：nums = [1, 2, 3, 4, 5, 6, 7]，我们要向右轮转 k = 3 步。

我们的最终目标是：[5, 6, 7, 1, 2, 3, 4]。

只需要做三个动作：

1. 第一次翻转：把整个数组全部翻转

   • 原数组：[1, 2, 3, 4, 5, 6, 7]
   • 翻转后：[7, 6, 5, 4, 3, 2, 1]
   • （此时你会发现，想要的 5, 6, 7 已经跑到前面去了，想要的 1, 2, 3, 4 也跑到后面去了，只是它们内部的顺序反了）

2. 第二次翻转：只翻转前 k 个元素

   • 当前数组：[7, 6, 5, 4, 3, 2, 1]
   • 翻转前 3 个：[5, 6, 7, 4, 3, 2, 1]
   • （前半部分的顺序被修正了）

3. 第三次翻转：只翻转剩下的 $n-k$ 个元素

   • 当前数组：[5, 6, 7, 4, 3, 2, 1]
   • 翻转后 4 个：[5, 6, 7, 1, 2, 3, 4]

论证

假设原数组是由两部分组成的：$A$ 和 $B$。

• $A$：代表前面的 $n-k$ 个元素（比如 1, 2, 3, 4）
• $B$：代表后面的 $k$ 个元素（比如 5, 6, 7）

原始的数组长这样：$AB$ 题目要求我们向右轮转 $k$ 步，本质上就是把 $B$ 这一块完整的切下来，挪到 $A$ 的前面 所以最终目标状态是：$BA$

我们用数学上的“求逆/翻转”符号 $^R$ 来推导：

1. 第一步（整体翻转）：将 $AB$ 整体翻转。根据规则，整体翻转不仅会把每一块内部翻转，还会把两块的位置对调。

   $$(AB)^R = B^R A^R$$

   现在，原本在后面的 $B$ 跑到前面来了，变成了 $B^R$。

2. 第二步（翻转前半部分）：只对现在的前半部分（也就是 $B^R$）进行翻转。负负得正：

   $$(B^R)^R = B$$

   现在的状态变成了：$B A^R$。前半部分已经完美复原成 $B$。

3. 第三步（翻转后半部分）：只对后半部分（也就是 $A^R$）进行翻转。

   $$(A^R)^R = A$$

   最终状态完美变成：$BA$。

代码实现

public void rotate(int[] nums, int k) {
    int n = nums.length;
    k = k % n; // 防止 k 大于数组长度
    
    reverse(nums, 0, n - 1); // 1. 整体翻转 (A B -> B^R A^R)
    reverse(nums, 0, k - 1); // 2. 翻转前 k 个 (B^R -> B)
    reverse(nums, k, n - 1); // 3. 翻转剩下的 (A^R -> A)
}

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