Data Collections — Solutions数据集合 —— 解析

Two collection types, two different interfaces:

• Arrays use a field: arr.length (no parentheses). The literal {1,2,3,4} has length 4.
• ArrayList uses a method: list.size() (with parentheses). After three adds, list.size() == 3.

Trap (D): arrays do have length — but they do not have .length(). String, the other way around, uses s.length(). Mix these up and the compiler instantly complains. AP MCQ writers love this comparison.

两种集合类型，两种不同的接口：

• 数组用字段：arr.length（不带括号）。字面量 {1,2,3,4} 长度为 4。
• ArrayList 用方法：list.size()（带括号）。三次 add 之后，list.size() == 3。

陷阱 (D)：数组有 length——但没有 .length()。反过来 String 用的是 s.length()。混用编译器立刻报错。AP 出题人很爱这种对比。

An array of length n has valid indices 0 through n − 1. With vals.length == 3, valid indices are 0, 1, 2. Reading vals[3] is out of bounds and Java throws ArrayIndexOutOfBoundsException at run time.

Trap (D): the bounds check is dynamic, not static — the compiler cannot generally tell that an index will be out of range. Trap (B): Java does not "wrap around" or silently clamp to the last element — some languages do this, but Java does not.

长度为 n 的数组合法下标是 0 到 n − 1。vals.length == 3，合法下标是 0, 1, 2。读 vals[3] 越界（out-of-bounds），Java 在运行时抛出 ArrayIndexOutOfBoundsException。

陷阱 (D)：边界检查是动态的，不是静态的——编译器通常无法判断某个下标是否越界。陷阱 (B)：Java 不会"环绕"或者悄悄夹紧到最后一个元素——有些语言会，Java 不会。

The enhanced-for loop variable v is a copy of each array element (since int is a primitive). Reassigning v changes only the local copy — the array is untouched.

• To modify in place, use an indexed loop: for (int i = 0; i < vals.length; i++) vals[i] *= 10;
• Even if the element type were an object, reassigning v wouldn't modify the array — you'd need to mutate the object's state via v.someMethod(...).

Trap (D): Java allows reassignment of the for-each variable; it just has no external effect. This is a classic AP "looks-like-it-should-work" trap.

增强 for 循环（enhanced for-loop）的循环变量 v 是每个数组元素的副本（因为 int 是基本类型）。给 v 重新赋值只改变本地副本——数组本身不受影响。

• 想就地修改，要用索引循环：for (int i = 0; i < vals.length; i++) vals[i] *= 10;
• 即便元素类型是对象，重新赋值 v 也不会修改数组——需要通过 v.someMethod(...) 修改对象的状态。

陷阱 (D)：Java 允许对 for-each 的循环变量重新赋值；只是外部不可见。这是 AP 经典的"看起来该有效却无效"的陷阱。

Two independent ideas combined: (1) b = a does not clone the array — both names point to the same underlying object, so mutations are shared. (2) == on array references compares reference identity, not contents.

• After b = a: both a and b reference the same array {1, 2, 3}.
• b[1] = 99 reaches through that shared reference → the array becomes {1, 99, 3}. Reading a[1] sees 99.
• c = {1, 99, 3} allocates a brand-new array on the heap with matching contents.
• a == b → same reference → true.
• a == c → different references (even though contents are identical) → false.

Output: "99 true false".

Trap (A) "1 true false" assumes b = a is a copy. (C) "99 true true" assumes == compares content — it doesn't (no .equals() override for plain int[] beyond Object's reference equality; use Arrays.equals for content). (B) mixes both mistakes.

两个独立的概念结合在一起：(1) b = a 不会复制数组——两个名字指向同一个底层对象，修改是共享的（别名 aliasing）。(2) 数组引用的 == 比较的是引用身份，不是内容。

• b = a 之后：a 与 b 都引用同一个数组 {1, 2, 3}。
• b[1] = 99 透过共享引用修改 → 数组变为 {1, 99, 3}。读 a[1] 得到 99。
• c = {1, 99, 3} 在堆上分配一个全新的、内容相同的数组。
• a == b → 引用相同 → true。
• a == c → 引用不同（即便内容完全一致）→ false。

输出："99 true false"。

陷阱 (A) "1 true false" 以为 b = a 是复制。(C) "99 true true" 以为 == 比较内容——并不（原生 int[] 没有重写 .equals() 超出 Object 的引用相等；要比较内容用 Arrays.equals）。(B) 把两种错误都犯了。

The bug is that after remove(i), every later element shifts left by one — but i still increments, so the loop skips the element that just moved into position i.

state           i  get(i)  action
[20,20,30,40]   0    20    remove → [20,30,40], i = 1
[20,30,40]      1    30    keep,        i = 2
[20,30,40]      2    40    remove → [20,30],    i = 3
[20,30]         3    —     3 < 2 false → exit

The second 20 (which shifted into index 0) is never re-checked, so it survives in the list. Result: [20, 30].

Trap (A) is the intended result if the bug weren't there. Fix: either loop backwards (for i = list.size() − 1 down to 0), or do i-- after a successful remove so the same index is re-checked.

这里的 bug 是：remove(i) 之后，后续每个元素左移一位——但 i 仍然自增，于是循环跳过了刚刚移动到位置 i 的那个元素。

state           i  get(i)  动作
[20,20,30,40]   0    20    remove → [20,30,40], i = 1
[20,30,40]      1    30    保留,         i = 2
[20,30,40]      2    40    remove → [20,30],    i = 3
[20,30]         3    —     3 < 2 false → 退出

第二个 20（已经移动到下标 0）从未被重新检查，所以它留在了列表里。结果：[20, 30]。

陷阱 (A) 是 bug 不存在时本应得到的结果。修复方法：要么逆序循环（for i = list.size() − 1 down to 0），要么在成功删除后执行 i--，让同一个下标被再次检查。

r + c == 2 picks out the anti-diagonal — the diagonal running from top-right to bottom-left.

row\col   0     1     2
   0   |  .     .   [3] ← r+c=2
   1   |  .   [5]    .  ← r+c=2
   2   | [7]    .     .  ← r+c=2

Sum: 3 + 5 + 7 = 15.

Anti-diagonal trick: for an N×N grid, all elements on the anti-diagonal satisfy r + c == N − 1. Memorize the two diagonal forms — they appear constantly on FRQ-style 2D problems.

条件 r + c == 2 选出反对角线（anti-diagonal）——从右上到左下的对角线。

row\col   0     1     2
   0   |  .     .   [3] ← r+c=2
   1   |  .   [5]    .  ← r+c=2
   2   | [7]    .     .  ← r+c=2

求和：3 + 5 + 7 = 15。

反对角线小窍门：对 N×N 网格，反对角线上的所有元素满足 r + c == N − 1。把两条对角线的判定形式（r == c 主对角线、r + c == N − 1 反对角线）背熟——FRQ 风格的 2D 题里反复出现。

The inner loop starts at c = r + 1, so each pair (r, c) with r < c is swapped exactly once. (If the inner started at c = 0, each pair would swap twice and the array would end up unchanged.)

start:                  swap (0,1) ↔ (1,0):    swap (0,2) ↔ (2,0):    swap (1,2) ↔ (2,1):
1 2 3                   1 4 3                   1 4 7                  1 4 7
4 5 6                   2 5 6                   2 5 6                  2 5 8
7 8 9                   7 8 9                   3 8 9                  3 6 9

Final grid is the transpose: rows are the original columns. Read out:

• g[0][2] → 7
• g[2][0] → 3
• g[1][1] → 5 (center is invariant under transpose)

Print: "7 3 5".

2D-mutation-through-parameter pattern: the array is passed by reference, so changes inside transpose persist in the caller — no return needed.

内层循环从 c = r + 1 开始，所以每对 (r, c)（满足 r < c）只交换一次。（如果内层从 c = 0 开始，每对会交换两次，最终数组保持不变。）

start:                  swap (0,1) ↔ (1,0):    swap (0,2) ↔ (2,0):    swap (1,2) ↔ (2,1):
1 2 3                   1 4 3                   1 4 7                  1 4 7
4 5 6                   2 5 6                   2 5 6                  2 5 8
7 8 9                   7 8 9                   3 8 9                  3 6 9

最终的网格是转置（transpose）：行是原来的列。读出：

• g[0][2] → 7
• g[2][0] → 3
• g[1][1] → 5（中心在转置下不变）

打印："7 3 5"。

"通过参数修改 2D 数组"的模式：数组按引用传递，transpose 内的修改会持久到调用方——不需要返回值。

ArrayList is an object; b = a aliases the same underlying list. Every mutation through b is visible through a.

step          | underlying list  a.size()
a.add(1..3)   | [1, 2, 3]            3
b = a         | [1, 2, 3]            3   (same list, two names)
b.set(0, 99)  | [99, 2, 3]           3   (no size change — set overwrites)
b.add(4)      | [99, 2, 3, 4]        4   (append → size grows)

Then a.size() = 4, a.get(0) = 99, a.get(3) = 4 → print "4 99 4".

Lesson: assigning one ArrayList reference to another never clones. To copy, use new ArrayList<>(a).

ArrayList 是对象；b = a 让两者别名同一个底层列表。通过 b 的每次修改对 a 都可见。

step          | 底层列表              a.size()
a.add(1..3)   | [1, 2, 3]            3
b = a         | [1, 2, 3]            3   （同一个列表，两个名字）
b.set(0, 99)  | [99, 2, 3]           3   （size 不变——set 是覆盖）
b.add(4)      | [99, 2, 3, 4]        4   （追加 → size 增长）

于是 a.size() = 4，a.get(0) = 99，a.get(3) = 4 → 打印 "4 99 4"。

规律：把一个 ArrayList 引用赋给另一个，永远不会复制底层列表。要复制，用 new ArrayList<>(a)。

The loop has no early-exit (no break, no return), so it visits every index 0–5. Each match overwrites idx:

i    arr[i]   action               idx after
0     3       skip                    -1
1     7       idx = 1                  1
2     5       skip                     1
3     7       idx = 3                  3
4     9       skip                     3
5     7       idx = 5                  5

Final idx = 5 — the index of the last occurrence. Trap (B) is what a correctly-written "find first" would produce (with a break after the first match). On the AP exam, watch for the missing break: it inverts the algorithm from "find first" to "find last."

循环没有提前退出（没 break、没 return），所以会遍历 0–5 的所有下标。每次命中都会覆盖 idx：

i    arr[i]   动作              idx 之后
0     3       跳过                   -1
1     7       idx = 1                 1
2     5       跳过                    1
3     7       idx = 3                 3
4     9       跳过                    3
5     7       idx = 5                 5

最终 idx = 5 —— 最后一次出现（last occurrence）的下标。陷阱 (B) 是"找第一次出现"的正确写法（要在第一次命中后 break）的结果。AP 考试时务必盯紧有没有 break：差这一句，算法就从"找第一次"变成了"找最后一次"。

Selection sort: on pass k (0-indexed), find the minimum of a[k..end] and swap it to position k.

start              : {5, 3, 8, 1, 9, 2}
Pass 1 (k=0):
  min of full array = 1 at idx 3
  swap a[0] ↔ a[3] : {1, 3, 8, 5, 9, 2}
Pass 2 (k=1):
  min of a[1..5]   = 2 at idx 5
  swap a[1] ↔ a[5] : {1, 2, 8, 5, 9, 3}

After 2 passes, indices 0 and 1 hold the two smallest values; everything from index 2 onward is whatever was left after the swaps. Trap (A) jumps to the fully-sorted state. (C) stops after one pass.

选择排序（selection sort）：第 k 轮（从 0 计）找出 a[k..end] 的最小值，与位置 k 交换。

start              : {5, 3, 8, 1, 9, 2}
Pass 1 (k=0):
  全数组最小 = 1，下标 3
  swap a[0] ↔ a[3] : {1, 3, 8, 5, 9, 2}
Pass 2 (k=1):
  a[1..5] 最小 = 2，下标 5
  swap a[1] ↔ a[5] : {1, 2, 8, 5, 9, 3}

2 轮之后，下标 0、1 已经是最小的两个值；下标 2 起的部分就是几次交换之后留下的样子。陷阱 (A) 直接跳到"完全排好"的状态。(C) 只做了一轮就停。

Insertion sort: starting at index 1, insert a[i] into the already-sorted prefix a[0..i-1].

start         : {5, 2, 8, 1, 9, 3}
Pass 1 (i=1):
  insert 2 into [5]    →   prefix becomes [2, 5]
  array         : {2, 5, 8, 1, 9, 3}
Pass 2 (i=2):
  insert 8 into [2, 5] →   8 > 5, no shift
  array         : {2, 5, 8, 1, 9, 3}

After 2 passes, indices 0–2 are a sorted prefix; the tail is untouched. Trap (D) assumes nothing has been inserted yet.

Selection vs Insertion (compare with Q10): selection sort fixes one element at a time from the front of the unsorted region; insertion sort grows a sorted prefix by slotting each new element. After k passes both have the prefix correct, but the trailing region looks different.

插入排序（insertion sort）：从下标 1 开始，把 a[i] 插入已经排好序的前缀 a[0..i-1]。

start         : {5, 2, 8, 1, 9, 3}
Pass 1 (i=1):
  把 2 插入 [5]    →   前缀变为 [2, 5]
  数组          : {2, 5, 8, 1, 9, 3}
Pass 2 (i=2):
  把 8 插入 [2, 5] →   8 > 5，不用移动
  数组          : {2, 5, 8, 1, 9, 3}

2 轮之后，下标 0–2 已经是排好的前缀；尾部不变。陷阱 (D) 以为还没开始插入。

选择 vs 插入（对比 Q10）：选择排序从未排序区的最前面，每轮固定一个元素；插入排序把已排好的前缀慢慢扩大，把新元素插入合适位置。k 轮后两者前缀都正确，但尾部状态不同。

Indices: 0:2, 1:5, 2:7, 3:12, 4:18, 5:23, 6:31, 7:42, 8:56.

lo  hi  mid  arr[mid]  compare to 19    next
 0   8    4      18      18 < 19          lo = 5
 5   8    6      31      31 > 19          hi = 5
 5   5    5      23      23 > 19          hi = 4
 5   4   —       —       lo > hi, exit (not found)

Examined values in order: 18, 31, 23. The last one examined before the loop exits is 23.

Note the search runs even when the target is absent — the loop terminates when lo > hi. Trap (A) stops after the first comparison; (C) stops before the final mid.

下标：0:2, 1:5, 2:7, 3:12, 4:18, 5:23, 6:31, 7:42, 8:56。

lo  hi  mid  arr[mid]  与 19 比较       下一步
 0   8    4      18      18 < 19          lo = 5
 5   8    6      31      31 > 19          hi = 5
 5   5    5      23      23 > 19          hi = 4
 5   4   —       —       lo > hi，退出（未找到）

检查的值依次为：18, 31, 23。退出循环之前最后检查的是 23。

注意：即使目标不存在，二分查找（binary search）也会一直运行，直到 lo > hi 时退出。陷阱 (A) 只看到第一次比较就停；(C) 在最后一个 mid 之前就停。

Each recursive call splits into two identical sub-calls and concatenates their results. The length doubles at every level.

n  | mystery(n)              length
0  | "X"                      1
1  | "X" + "X"      = "XX"    2
2  | "XX" + "XX"   = "XXXX"   4
3  |  "XXXX"+"XXXX"           8
4  |  …            (8+8)     16

In general, mystery(n) has length 2ⁿ. For n = 4, that's 2⁴ = 16.

The deeper lesson: a recursive method with k recursive calls has a call tree with branching factor k. Total work is exponential in the depth: this method makes 2ⁿ + 2ⁿ⁻¹ + … + 2 + 1 = 2ⁿ⁺¹ − 1 total calls. Even at n = 30, you'd be making ~2 billion calls — the classic naive-Fibonacci trap.

每一次递归调用都会分裂为两个完全相同的子调用，再把结果拼接。长度在每一层都翻倍。

n  | mystery(n)              长度
0  | "X"                      1
1  | "X" + "X"      = "XX"    2
2  | "XX" + "XX"   = "XXXX"   4
3  |  "XXXX"+"XXXX"           8
4  |  …            (8+8)     16

一般地，mystery(n) 的长度是 2ⁿ。n = 4 时是 2⁴ = 16。

更深的教训：递归方法中每层做 k 次递归调用，调用树就是分支因子为 k。总工作量随深度呈指数增长（exponential branching）：这道题总共会调用 2ⁿ + 2ⁿ⁻¹ + … + 2 + 1 = 2ⁿ⁺¹ − 1 次。就算 n = 30，已经要做大约 20 亿次调用——这就是经典的"朴素斐波那契陷阱"。

The recursion counts the number of integer halvings needed to drop below 2.

g(17) = 1 + g(8)
      = 1 + 1 + g(4)
      = 1 + 1 + 1 + g(2)
      = 1 + 1 + 1 + 1 + g(1)
      = 1 + 1 + 1 + 1 + 0
      = 4

Conceptually, this is ⌊log₂(n)⌋ for n ≥ 1 — exactly the running-time intuition behind binary search (Q12).

Trap (C) counts the base call. Trap (A) stops one halving early. Be careful with the integer-division step: 17 / 2 = 8, not 8.5.

这个递归数的是：把 n 整除以 2 多少次才能降到 2 以下。

g(17) = 1 + g(8)
      = 1 + 1 + g(4)
      = 1 + 1 + 1 + g(2)
      = 1 + 1 + 1 + 1 + g(1)
      = 1 + 1 + 1 + 1 + 0
      = 4

概念上，对 n ≥ 1，这就是 ⌊log₂(n)⌋——正是二分查找（Q12）背后的运行时直觉。

陷阱 (C) 多算了基础调用。陷阱 (A) 提前一次停止。注意整除：17 / 2 = 8，不是 8.5。

Java passes the array reference by value: the parameter a is a local copy of the reference. The body does three things, in order — and only the first escapes the method.

step                          | parameter a points to         caller's vals
on entry                      | (original) {1,2,3,4,5}        {1,2,3,4,5}
a[0] = 99                     | {99,2,3,4,5}                  {99,2,3,4,5}   ← shared array mutated
a = new int[]{100,200,300}    | (NEW)     {100,200,300}       {99,2,3,4,5}   ← caller untouched
a[0] = 999                    | (NEW)     {999,200,300}       {99,2,3,4,5}   ← still untouched

After return: vals = {99, 2, 3, 4, 5}. Print vals[0] = 99, vals[2] = 3, vals.length = 5 → "99 3 5".

Trap (C) "999 300 3" is the canonical mistake — assumes the method's reassignment of a is visible to the caller. It isn't. Reassigning a parameter never reaches the caller; mutating through it does. (A) "1 3 5" assumes pass-by-value means nothing happens. (D) "100 300 3" sees the rebind but misses the second mutation.

This is the array twin of Unit 3 Q7's rebind-vs-mutate. The rule is uniform across int[], ArrayList, and any class instance.

Java 把数组引用按值传递：参数 a 是引用的一个本地副本。方法体按顺序做三件事——只有第一件会逃出方法。

步骤                            | 参数 a 指向                   调用方的 vals
进入方法时                       | （原数组）{1,2,3,4,5}         {1,2,3,4,5}
a[0] = 99                       | {99,2,3,4,5}                  {99,2,3,4,5}   ← 共享数组被修改
a = new int[]{100,200,300}      | （新对象）{100,200,300}       {99,2,3,4,5}   ← 调用方未受影响
a[0] = 999                      | （新对象）{999,200,300}       {99,2,3,4,5}   ← 仍未受影响

返回后：vals = {99, 2, 3, 4, 5}。打印 vals[0] = 99、vals[2] = 3、vals.length = 5 → "99 3 5"。

陷阱 (C) "999 300 3" 是经典错误——以为方法内对 a 的重新赋值（rebind）对调用方可见。其实不会。"重新赋值参数"永远不会影响调用方；"透过参数修改对象"才会。(A) "1 3 5" 以为按值传递就什么都不发生。(D) "100 300 3" 看到了 rebind，却漏掉了之后的第二次修改。

这是 Unit 3 Q7 "rebind vs mutate" 的数组版。规则对 int[]、ArrayList 和任何类实例都一致。