更新题目 值替换连续：最少操作数
题目 amazon-replace-values-contiguous-min-ops · 修改（rev 6） · · 2026-10-27 00:33
body
@@ -1,96 +1,171 @@ +## TL;DR + +- 一次操作把 x 全换成数组里已有的 y，就是把两种值并成一种，不同值的种数最多少 1（「思路」第 1 步）。 +- 答案是 $D - P$：$D$ 是不同值的种数，$P$ 是数组最多能切成的段数，要求每种值只落在一段里（「思路」第 2、3 步）。 +- 求 $P$ 用划分字母区间（Partition Labels，LC 763）的扫法：记每种值的最后位置，从左扫，扫到「当前段最远的最后位置」就切一刀（「思路」第 4 步）。 +- 只数「自身不连续的值」是错的，`[1,2,1,2]` 会多算、`[1,2,3,1]` 会少算（「易错点」）。 + ## 题目 -给一个整数数组。一次操作是：选两个值 x 和 y，把数组里**所有**等于 x 的元素一次性换成 y。问最少要几次操作，才能让数组「按值成块」，也就是每一种（最终还留在数组里的）值，它的所有出现位置都连成一整段，中间不夹别的值。输出一个整数。 +给一个整数数组。一次操作是选两个不同的值 x 和 y，把数组里**所有**等于 x 的元素一次性换成 y。问最少几次操作，能让数组按值成块：最终还留在数组里的每种值，它的所有出现位置连成一整段，中间不夹别的值。返回一个整数。 -- 几篇面经（面试经验帖）都是按**操作次数**算代价。其中一篇给了英文原句，意思是「求这种操作的最少次数，使数组变得连续（contiguous），也就是每个值的出现位置组成一个不被打断的块」；另一篇写的是把某个值「全部替换成另一个值」，可见 x 和 y 是两个不同的值。 -- 原帖都**没有给样例、数据范围和函数签名**，OA 里的函数名和输入格式未核实。下面的样例全部来自一亩三分地（北美华人求职论坛）站方用 AI 生成的整理（下文简称「站方 AI」），不是楼主（发帖的人）写的： +几篇面经（面试经验帖）都按**操作次数**算代价。其中一篇给了英文原句，意思是求这种操作的最少次数，使数组变得连续（contiguous），也就是每个值的出现位置组成一个不被打断的块。另一篇写的是把某个值「全部替换成另一个值」，所以 x 和 y 是两个不同的值。 + +原帖都没有给样例、数据范围和函数签名，OA 里的函数名和输入格式未核实。下面的样例都来自一亩三分地（北美华人求职论坛）站方用 AI 生成的整理（下称「站方 AI」），不是楼主（发帖人）写的，未经原帖证实。每一个都用暴力解核对过（见「代码」一节的实测），和「按操作次数计」的理解一致： | 输入 | 输出 | 说明 | | --- | --- | --- | -| `[1,2,1,2]` | 1 | 把 1 全换成 2（站方 AI 整理，未经原帖证实） | -| `[1,2,1,3]` | 1 | 把 2 换成 1，得到 `[1,1,1,3]`（站方 AI 整理，未经原帖证实） | -| `[1,2,1,3,2]` | 2 | 三种值的区间连成一片，只能全部并成一个值（站方 AI 整理，未经原帖证实） | -| `[1,2,1,2,3,3,3]` | 1 | （站方 AI 整理，未经原帖证实） | -| `[1,2,1,3,2,3]` | 2 | （站方 AI 整理，未经原帖证实） | -| `[5,1,5,5,2,1,2,2]` | 2 | （站方 AI 整理，未经原帖证实） | -| `[1,1,2,2,3]`、`[42]` | 0 | 本来就成块（站方 AI 整理，未经原帖证实） | +| `[1,2,1,2]` | 1 | 把 1 全换成 2 | +| `[1,2,1,3]` | 1 | 把 2 换成 1，得到 `[1,1,1,3]` | +| `[1,2,1,3,2]` | 2 | 三种值的范围连成一片，只能并成一种值 | +| `[1,2,1,2,3,3,3]` | 1 | 后面的 3 本来就成块，不用动 | +| `[1,2,1,3,2,3]` | 2 | 三种值连成一片 | +| `[5,1,5,5,2,1,2,2]` | 2 | 5 和 2 的范围不相交，但都和 1 相交，三种值连成一片 | +| `[1,1,2,2,3]`、`[42]` | 0 | 本来就成块 | -这些样例都用暴力解（brute force，在数组状态上做 BFS 搜最少步数，见「代码」一节末尾的说明）核对过，结果和「按操作次数计」的理解一致。站方 AI 还给了数据范围 `1 <= n <= 2*10^5`、值在 `-10^9..10^9`，同样未经原帖证实，所以只当作提示：按这个规模，O(n²) 的算法会超时，需要 O(n) 或 O(n log n) 的解法。 +站方 AI 还给了数据范围 `1 <= n <= 2*10^5`、值在 `-10^9..10^9`，同样未经证实，只当提示：按这个规模，$O(n^2)$ 会超时，要 $O(n)$ 或 $O(n \log n)$。 -这道题有一个**变体** [[q:amazon-replace-values-contiguous-min-cost]]（`getMinAmount`），规则一样，但代价算的是**被改动的元素个数**，而不是操作次数。所以同一个输入，两题的答案不同：`[1,2,1,2]` 在这题是 1 次操作，在那题要改动 2 个元素。也有可能某位楼主把「代价」记成了「次数」，未证实；考试时要先看清题目问的是哪一个。 +这道题有一个变体 [[q:amazon-replace-values-contiguous-min-cost]]（`getMinAmount`），操作一样，代价算的是**被改动的元素个数**。同一个输入两题答案不同：`[1,2,1,2]` 在这题是 1 次操作，在那题要改动 2 个元素。也可能是某位楼主把「代价」记成了「次数」，未证实。考试时先看清题目问的是哪一个。 ## 面经里怎么考的 -- **2026-04 的一篇**，楼主是应届毕业生（new grad，NG），硕士，投的是全职岗位，1～2 月直接投递。这次 OA 分四段：coding、AI coding、Work Simulation 和 Work Style。Coding 段 40 分钟，只有这一道题。接下来的 AI coding 段 60 分钟，要借助 AI 完成一个工程任务：在给定的全栈项目里加上限流（rate limit）、关键词屏蔽和把用户加进黑名单这几个功能，楼主说 AI 还算靠谱。Work Simulation 段模拟日常工作场景，标的是 45 分钟，形式是邮件式的选择题，要轮流扮演前端、后端和测试，针对 bug 和 code review 选择怎么回应。Work Style 段是工作风格问卷，标的是 15 分钟，每题选哪种描述更像自己。后两段楼主都注明了「不计时」，和标出来的时长对不上，回复里也有人问过，楼主没有解释。楼主很久没练算法题，觉得难度偏大，自己说基本已经挂了（帖子结果标的是 Fail），但没说卡在哪一步。 -- **2026-06 的一篇**，楼主是在职跳槽。Coding 段有两道题：第一题楼主用谐音数字写成「要就要要」（幺九幺幺，即 1911），【推断】是 LC 1911，很快就做出来了；第二题就是这道。楼主的做法是先把相邻的重复元素压缩成一个，再用贪心（greedy）的思路数有多少种值散落在不连续的位置，然后逐步合并；据楼主说，**边界情况（edge case）很多，调了好一会儿**。楼主还说做过「利口物流」，对想出思路有帮助，时间也够用。「利口物流」是谐音写法：「利口」谐音力扣（LeetCode 中文站），「物流」谐音 56，【推断】指的是 [[q:lc56]] 合并区间（Merge Intervals）。这篇没提 AI coding（回复里有人问是不是旧版 OA，楼主没回）；行为问题（behavioral）部分是一份 LP 问卷，LP 指 Amazon 的领导力准则（Leadership Principles）。 -- **2026-08 的一篇**，楼主也是在职跳槽。Coding 部分楼主只写了这一道，而且只有一句题意。AI coding 段是在一个现成的代码仓库（repo）里修接口：有 6 个测试没通过，要去查 controller 的参数校验、数据持久化和接口返回的 status；AI 能帮着找到相关文件，但改动要自己做，楼主觉得不难，但很耗时间。最后一段是行为问题（behavioral question，BQ）的选择题。 +这几篇帖子都是 Amazon SDE 的 OA，题面都只有一两句话、没有样例，能拿多少分取决于自己能不能把规则想透。 -把这几篇放在一起看，这道题从 2026-04 到 2026-08 一直在考。在「一道 coding 题 + AI coding」格式的帖子里（2026-04、2026-08；2026-08 那篇只提到一道 coding），唯一的那道 coding 题都是它；在有两道 coding 题的版本里（2026-06），它排第二题。题面只有一两句话、没有样例，能拿多少分取决于自己能不能把规则想透。想透的关键是看出**一次操作其实就是把两种值并成一种**，看出这一点之后，剩下的就是合并区间问题。那位说「调了好一会儿」的楼主遇到的边界情况，多半是只数了「自己不连续」的值，漏掉了被夹在别的值中间的值（见易错点）【推断】。 +- **2026-04 的一篇**，楼主是硕士应届毕业生（new grad，NG），投全职，1～2 月直接投递。OA 分 coding、AI coding、Work Simulation、Work Style 四段。Coding 段 40 分钟，只有这一道题。AI coding 段 60 分钟，在给定的全栈项目里借助 AI 加限流（rate limit）、关键词屏蔽和用户黑名单，楼主说 AI 还算靠谱（这一段的做法见 [[q:amazon-oa-ai-debug]]）。Work Simulation 标 45 分钟，是邮件式选择题，轮流扮演前端、后端和测试，选怎么回应 bug 和 code review。Work Style 标 15 分钟，是工作风格问卷。后两段楼主又注明「不计时」，和标出的时长对不上，回复里有人问，楼主没解释（这两段的做法见 [[q:amazon-oa-work-simulation]]）。楼主很久没练算法题，觉得偏难，自己说基本已经挂了（帖子标 Fail），没说卡在哪一步。 +- **2026-06 的一篇**，楼主是硕士，在职跳槽。Coding 段两道题。第一题楼主用谐音数字写成「要就要要」（幺九幺幺，即 1911），【推断】是 LC 1911，很快做完。第二题是这道，楼主说和地里另一篇基本一样。他的做法是先把相邻的重复元素压缩成一个，再用贪心（greedy）数有多少种值散落在不连续的位置，然后逐步合并。据他说**边界情况（edge case）很多，调了好一会儿**。他说做过「利口物流」，对想出思路有帮助，时间也够。「利口」谐音力扣（LeetCode 中文站），「物流」谐音 56，【推断】指 [[q:lc56]] 合并区间（Merge Intervals）。这篇没提 AI coding，回复里有人问是不是旧版 OA，楼主没回。行为部分是一份 LP 问卷，LP 指 Amazon 的领导力准则（Leadership Principles）。 +- **2026-08 的一篇**，楼主在职跳槽。Coding 部分只写了这一道，只有一句题意。AI coding 段是在现成的代码仓库（repo）里修接口，有 6 个测试没过，要查 controller 的参数校验、数据持久化和接口返回的 status。AI 能帮着找到相关文件，改动要自己做，楼主觉得不难但很耗时间。最后一段是行为问题（behavioral question，BQ）的选择题。 + +几篇放在一起看，这道题在 OA 里的位置有规律。2026-04 和 2026-08 两篇的 OA 都有 AI coding 段，这道题是 coding 段里唯一的算法题（2026-08 那篇只提到这一道）。2026-06 那篇没提 AI coding，coding 段有两道题，这道排第二，前面那道楼主很快就做完了。两位写了感受的楼主，一位觉得偏难，一位说边界情况多、调了很久。想透的关键是看出**一次操作就是把两种值并成一种**，看出这一点，剩下的就是合并区间。 ## 思路 -先说结论：答案等于数组里不同值的种数，减去数组最多能切成的段数，切的时候要求每种值只落在其中一段里。下面一步步说明为什么。 +结论先说：答案等于不同值的种数 $D$ 减去数组最多能切出的段数 $P$，切的时候要求每种值只落在其中一段里。下面分四步推出来。 -1. **一次操作，其实就是把两类值合并成一类。** 设数组里一共有 D 种不同的值。把 x 全换成 y 时，如果 y 已经在数组里，x 和 y 就并成了一类，不同值的种数恰好少 1；如果 y 是数组里没有的新值，那只是给 x 改了个名字，对是否成块没有任何影响。也就是说，每次操作最多让值的种数减少一种。所以如果最终把这 D 种值分成 m 组、每组变成同一个值，至少需要 D − m 次；反过来，在每组里把其余的值都换成组里的某一个，正好用 D − m 次。于是要让操作次数最少，就要让组数 m 尽量大，问题变成**最多能分成几组**。 -2. **合法的分组是什么样子。** 每组最后会变成一整块，这些块从左到右铺满整个数组。相邻两块之间的分界（下面叫「切口」）不能被任何一种值跨过去，否则这种值在切口两边都有，它就没法只占一块。反过来，每一个没有任何值跨过的位置都可以切。所以最多能分成的组数，就等于在「每种值只落在一段里」的前提下最多能切出的段数，把它记作 P。这正是划分字母区间（Partition Labels，LC 763）那道题的切法：那道题要把字符串切成尽量多的段，让每个字母只出现在其中一段里。 -3. **所以答案是 D − P。** 一段内部不能再切，因为再切就会出现一个被某种值跨过的、不合法的切口；所以一段里有 k 种值，就必须把它们并成一种，要并 k − 1 次。所有段的种数加起来是 D，每段的次数都比种数少一次，总共就是 D − P 次。 -4. **求 P 只需要扫两遍数组。** 第一遍记下每种值最后一次出现的位置 `last[v]`。第二遍从左往右扫，用 `reach` 记录当前这一段里所有已出现的值中最远的结束位置，每扫到一个值就更新 `reach = max(reach, last[v])`。扫到 `i == reach` 时，说明当前段里出现过的值都已经在这里结束、后面不会再出现，可以在这里切一刀。 -5. **这和楼主说的「合并区间」是同一件事。** 给每种值取它第一次和最后一次出现的位置，组成区间 `[first, last]`，再把互相重叠的区间合并起来（LC 56），最后会合并出 P 个大区间；每个大区间里有 k 种值，就花 k − 1 次。楼主先把相邻的重复元素压缩掉，这一步不影响答案，可以不做：相邻的重复元素属于同一种值，压缩前后各个值的区间之间怎么重叠并没有变化。 +### 第 1 步：一次操作就是合并两类值 -举个例子，`[1,2,3,1,4,5,4]`。第一遍得到的 `last`（值→最后一次出现的下标）是 1→3、2→1、3→2、4→6、5→5。第二遍扫到下标 3 时 `reach` = 3，切出第一段 `{1,2,3}`；扫到下标 6 时切出第二段 `{4,5}`。这里 D = 5，P = 2，答案是 3，具体操作是 2→1、3→1、5→4。 +把 x 全换成 y 时，如果 y 已经在数组里，x 和 y 就并成一类，不同值的种数恰好少 1。如果 y 是数组里没有的新值，那只是给 x 改了个名字，位置一个没变，对是否成块没有影响。所以每次操作最多让种数少 1。最终数组里如果剩 $m$ 种值，至少要 $D - m$ 次。反过来，把原来的 $D$ 种值分成 $m$ 组，每组把其余的值都换成组里某一个，正好 $D - m$ 次。要操作最少，就要让最终剩下的组数 $m$ 尽量大。 + +### 第 2 步：最多能剩几组 + +成块的最终数组里，每组占一整块，这些块从左到右铺满数组。相邻两块之间的分界（下面叫「切口」）不能被任何一种原来的值跨过：要是值 v 在切口两边都有，v 所在的组就会占两块。反过来，任何一个没被跨过的位置都可以切。所以最多的组数就是最多能切出的段数 $P$，这正是划分字母区间（LC 763）的切法，那道题要把字符串切成尽量多的段，让每个字母只出现在一段里。 + +### 第 3 步：答案等于种数减段数 + +一段内部再找不到合法切口，所以一段里的 $k$ 种值必须并成一种，要 $k - 1$ 次。各段的种数加起来是 $D$，每段的次数比种数少 1，总共 $D - P$ 次。第 2 步说明最多只能剩 $P$ 组，代入第 1 步的 $D - m$，$D - P$ 就是下界（lower bound），答案就是它。 + +> [!say] Replacing every x with an existing value y merges two value classes, so each operation reduces the number of distinct values by at most one. If I can keep at most P groups, I need at least D minus P operations, and merging each group into one representative achieves exactly that. + +### 第 4 步：扫两遍求段数 + +第一遍记下每种值最后一次出现的下标 `last[v]`。第二遍从左往右扫，用 `reach` 记当前段里已出现的值中最远的 `last`，每扫到一个值就更新 `reach = max(reach, last[v])`。扫到 `i == reach` 时，当前段出现过的值都在这里结束，后面不会再出现，这里是一个合法切口，段数加 1。 + +### 和合并区间的关系 + +2026-06 楼主说的合并区间是同一件事的另一种写法：每种值取第一次和最后一次出现的位置组成区间，把互相重叠的区间合并（LC 56），会合并出 $P$ 个大区间。他先压缩相邻的重复元素，这一步可以不做。相邻的重复元素是同一种值，压缩前后各区间之间的重叠关系不变，答案也不变。 + +### 例子 + +以 `[1,2,3,1,4,5,4]` 为例。第一遍得到 `last`：1→3、2→1、3→2、4→6、5→5。第二遍扫到下标 3 时 `reach` 是 3，切出第一段 `{1,2,3}`。扫到下标 6 时切出第二段 `{4,5}`。$D = 5$，$P = 2$，答案是 3，具体操作是 2→1、3→1、5→4。 + +> [!say] To find P, I record the last index of every value, then scan left to right tracking the farthest last index in the current segment. Whenever the current index equals it, no value crosses this point, so I can cut there. The answer is the number of distinct values minus the number of segments. ## 代码 ```python -from typing import List +from typing import Dict, List + + +def last_positions(arr: List[int]) -> Dict[int, int]: + """每种值最后一次出现的下标。""" + last = {} + for i, value in enumerate(arr): + last[value] = i + return last + + +def count_blocks(arr: List[int], last: Dict[int, int]) -> int: + """最多能切成几段，要求每种值只落在其中一段里。""" + blocks = 0 + reach = -1 # 当前段里已出现的值中，最远的最后位置 + for i, value in enumerate(arr): + reach = max(reach, last[value]) + if i == reach: # 当前段的值都在 i 之前（含 i）结束，可以切 + blocks += 1 + return blocks def min_operations(arr: List[int]) -> int: - last = {} - for i, v in enumerate(arr): - last[v] = i # 每种值最后一次出现的位置 - blocks = 0 - reach = -1 # 当前段里所有值的最远结束位置 - for i, v in enumerate(arr): - reach = max(reach, last[v]) - if i == reach: # 前面出现过的值都在这里之前结束，可以切一刀 - blocks += 1 - return len(last) - blocks # 不同值的种数 - 段数 - - -if __name__ == "__main__": - print(min_operations([1, 2, 1, 2])) # 1 - print(min_operations([1, 2, 3, 1])) # 2 - print(min_operations([1, 2, 3, 1, 4, 5, 4])) # 3 + last = last_positions(arr) + return len(last) - count_blocks(arr, last) ``` -这段代码已运行（Python 3.12，2026-10-17），样例和边界用例全部通过。另外写了一个暴力解：把每个数组状态当作一个节点，每一步枚举一次 x→y 替换，直接在数组状态上做 BFS 找最少步数。用这个暴力解在 3000 组随机小数据（n ≤ 8，值取 0～4）上和上面的解法对比结果（这种做法叫「对拍」），全部一致。n = 2×10^5 时运行约 0.05 秒。 +空数组时 `last` 为空、段数为 0，返回 0，不用单独判断。 + +### 实测 + +2026-10-27 用 Python 3.13 跑了三样东西： + +- 暴力解：把每个数组状态当一个节点，每步枚举一次「把 x 全换成另一个已有的值 y」，在状态上做 BFS 找最少步数。换成新值只是改名，所以不枚举。 +- 两个错误版本。「只数不连续」：数自身出现位置不连续的值有几种，每种算一次。只盯着「散落的值」时，容易写成这样。「每段 1 次」：切段对了，但每个多值段只算 1 次。 +- 上面的正解。 + +「只数不连续」的代码如下。一种值的出现位置连续，等价于它从第一次到最后一次出现的跨度正好等于它的出现次数： + +```python +def count_scattered(arr: List[int]) -> int: + """错误版本：数自身出现位置不连续的值有几种。""" + first: Dict[int, int] = {} + last: Dict[int, int] = {} + count: Dict[int, int] = {} + for i, value in enumerate(arr): + first.setdefault(value, i) + last[value] = i + count[value] = count.get(value, 0) + 1 + return sum(1 for v in first if last[v] - first[v] + 1 != count[v]) +``` + +在同一组输入上并排的结果（期望值和暴力解全部一致）： + +| 输入 | 暴力解 | 正解 | 只数不连续 | 每段 1 次 | +| --- | --- | --- | --- | --- | +| `[1,2,1,2]` | 1 | 1 | 2 | 1 | +| `[1,2,1,3,2,3]` | 2 | 2 | 3 | 1 | +| `[5,1,5,5,2,1,2,2]` | 2 | 2 | 3 | 1 | +| `[1,2,3,1]` | 2 | 2 | 1 | 1 | +| `[3,1,3,2,1,2]` | 2 | 2 | 3 | 1 | +| `[1,2,3,1,4,5,4]` | 3 | 3 | 2 | 2 | + +「只数不连续」两个方向都会错：`[1,2,1,2]` 里 1 和 2 都不连续，`count_scattered` 算 2，实际把 1 换成 2 一次就够。`[1,2,3,1]` 里只有 1 不连续，`count_scattered` 算 1，漏了夹在中间的 2 和 3。 + +再用 3000 组随机小数据（长度 0～8，值取 0～4，种子 20261027）和暴力解对拍：正解全部一致，「只数不连续」错 656 组，「每段 1 次」错 807 组。$n = 2 \times 10^5$、值在 $\pm 10^9$ 内随机时，正解跑了三次，每次约 0.16 到 0.21 秒。「题目」和「测试用例」两张表里的 17 个输入也都跑过，正解和暴力解都等于期望值。另外在 400 组随机小数据上让暴力解多枚举「换成数组里没有的新值」，最少步数一次都没变，和第 1 步「换成新值只是改名」的说法一致。 ## 复杂度 -时间是 O(n)，因为只对数组扫两遍。空间是 O(D)，D 是不同值的种数，它们存在 `last` 字典里。值很大或者是负数都没关系，因为用的是字典，而不是按值的大小开数组。 +时间 $O(n)$，数组扫两遍，每步是一次字典读写。空间 $O(D)$，存 `last` 字典。值很大或为负数都没关系，用的是字典，不按值的大小开数组。 + +> [!say] It's two linear passes, so O(n) time, plus a dictionary of last indices, O(D) space. ## 易错点 -- **只数「自己不连续」的值是错的。** `[1,2,3,1]` 里只有 1 不连续，但 2 和 3 夹在 1 的区间里。要让那个不连续的值成块，它最后所在的那一块必须盖住整个区间，所以夹在里面的值也得并进去，答案是 2 不是 1。要按「段」来算，而不是按「散落的值」来算。 -- **一段里 k 种值要并 k − 1 次，不是 1 次。** 同样是 `[1,2,3,1]`：只有一段，里面有三种值，所以要 2 次。 -- **区间可能是链式重叠的**，也就是两个区间互不相交，但都和中间某个区间相交。比如 `[3,1,3,2,1,2]`：3、1、2 的区间分别是 `[0,2]`、`[1,4]`、`[3,5]`，3 和 2 不相交，但经过 1 连成了一段，答案是 2。所以合并时要拿「目前为止的最远右端」来比，不能只看相邻的两个值。 -- **别和按改动元素个数计代价的变体（min-cost 版）搞混。** 按改动的元素个数计，`[1,2,1,2]` 是 2；按操作次数计是 1。 -- 把 x 换成数组里没有的新值，或者 x 和 y 相同，都不会减少值的种数，对答案没有帮助，所以不用考虑这两种操作。 -- 空数组、所有元素都相同、所有元素都不同，这几种情况本来就成块，答案都是 0。 +- **只数自身不连续的值。** 被夹在别人范围里的值，自身连续也得并进去（`[1,2,3,1]` 答案是 2），自身不连续的两种值也可能一次就并好（`[1,2,1,2]` 答案是 1）。要按段算，见「思路」第 2、3 步。 +- **一段里 $k$ 种值要并 $k - 1$ 次，不是 1 次。** `[1,2,3,1]` 只有一段、三种值，要 2 次。 +- **区间链式重叠。** `[3,1,3,2,1,2]` 里 3 和 2 的范围不相交，但经过 1 连成一段，答案是 2。所以要和「目前为止最远的最后位置」`reach` 比，不能只看相邻两个值。 +- **和按改动元素个数计的变体搞混。** `[1,2,1,2]` 按操作次数是 1，按改动元素个数是 2。 ## 测试用例 +前四行是站方 AI 的样例，其余是自己补的。 + | 输入 | 期望 | 测的是什么 | | --- | --- | --- | -| `[1,2,1,2]` | 1 | 最小的交错情形（站方 AI 样例） | -| `[1,2,1,3]` | 1 | 后面独立的一段不用动（站方 AI 样例） | -| `[1,2,1,3,2]` | 2 | 三种值连成一段（站方 AI 样例） | -| `[5,1,5,5,2,1,2,2]` | 2 | 三种值链式交错，并成一段：5 和 2 的区间不相交，经过 1 连起来（站方 AI 样例） | -| `[1,2,3,1]` | 2 | 被夹住、但自身连续的值也要并 | -| `[1,2,2,1]` | 1 | 同上，被夹住的值有重复 | +| `[1,2,1,2]` | 1 | 最小的交错情形 | +| `[1,2,1,3]` | 1 | 后面独立的一段不用动 | +| `[1,2,1,3,2]` | 2 | 三种值连成一段 | +| `[5,1,5,5,2,1,2,2]` | 2 | 链式交错，5 和 2 经过 1 连起来 | +| `[1,2,3,1]` | 2 | 被夹住但自身连续的值也要并 | +| `[1,2,2,1]` | 1 | 被夹住的值有重复 | | `[3,1,3,2,1,2]` | 2 | 链式重叠 | -| `[1,2,1,3,4,3]` | 2 | 两段各要 1 次，加起来 | -| `[1,2,3,1,4,5,4]` | 3 | 两段，分别要 2 次和 1 次 | +| `[1,2,1,3,4,3]` | 2 | 两段各 1 次 | +| `[1,2,3,1,4,5,4]` | 3 | 两段分别 2 次和 1 次 | | `[1,2,3,4]`、`[7,7,7]`、`[42]`、`[]` | 0 | 本来就成块 | | `[-5,1000000000,-5]` | 1 | 负数和大数 | @@ -98,33 +173,3 @@ ## Follow-up -- **如果要求把具体的操作也输出来**，可以每段取第一个值当代表，把段里其余的值都换成它。下面的代码已运行，并验证过照着输出的操作做完以后，数组确实成块、操作次数等于答案。 - - ```python - def min_operations_with_plan(arr): - last = {v: i for i, v in enumerate(arr)} - ops, reach, rep, seen = [], -1, None, set() - for i, v in enumerate(arr): - if rep is None: - rep = v # 这一段的代表值 - if v not in seen: - seen.add(v) - if v != rep: - ops.append((v, rep)) # 把 v 全部换成 rep - reach = max(reach, last[v]) - if i == reach: # 段结束 - rep, seen = None, set() - return len(ops), ops - - # min_operations_with_plan([1, 2, 3, 1, 4, 5, 4]) -> (3, [(2, 1), (3, 1), (5, 4)]) - ``` - -- **如果代价改成「被改动的元素个数」**，就是变体 [[q:amazon-replace-values-contiguous-min-cost]]。切段的方法完全一样，只是每段的代价变成「段长 − 段内出现次数最多的那个值的次数」：做法是把整段都并到出现次数最多的那个值上，这样不用动的元素最多。这个公式和枚举「每种值最后变成谁」的暴力解对拍过（n ≤ 7），结果一致。它的结构和 Codeforces 1209G1 Into Blocks 相同（凭记忆，未核实）。 -- **面试官问正确性时，要能说清为什么不能更少。** 每次操作最多让不同值的种数少 1；而在成块的最终数组里，每种值占一块，块与块之间都是合法的切口，所以最终最多剩下 P 种值。这两句合起来，就说明至少需要 D − P 次，这就是下界（lower bound）的证明；思路里的做法又正好用 D − P 次，所以答案就是它。 - -## 英文讲法 - -> [!say] Replacing every x with y is really merging two value classes, so each operation reduces the number of distinct values by at most one. If the final array has m distinct values, I need at least D minus m operations, and that is achievable by merging each group into one representative. - -> [!say] So I want the maximum number of groups. Each group ends up as one contiguous block, and a cut between two blocks is only legal if no value appears on both sides. That's exactly the Partition Labels split: record the last index of every value, scan left to right tracking the farthest last index seen so far, and cut whenever the current index equals it. - -> [!say] The answer is the number of distinct values minus the number of blocks. It's two linear passes, O(n) time and O(D) space. The trap is counting only values that are themselves broken; a value sitting inside another value's span, like the 2 and 3 in [1,2,3,1], has to be merged too. +- **代价改成被改动的元素个数**，就是 [[q:amazon-replace-values-contiguous-min-cost]]。切段方法完全一样，每段的代价变成「段长减去段内出现最多的那个值的次数」：把整段并到出现最多的值上，不用动的元素最多。这个公式 2026-10-27 和枚举「每种值最后变成谁」的暴力解在 2000 组随机小数据（$n \le 7$）上对拍过，全部一致。结构和 Codeforces 1209G1 Into Blocks 相同（凭记忆，未核实）。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" +}