更新题目 合并分支使冲突最少
题目 amazon-merge-min-conflicts · 修改（rev 5） · · 2026-10-27 00:33
body
@@ -1,99 +1,137 @@ +## TL;DR + +- 冲突就是合并串里的逆序对，同一个分支内部的逆序对也算（「题目」）。 +- 回溯枚举所有合并方式有 $\binom{m+n}{m}$ 种，长度 1000 时跑不完。贪心取较小的开头也不对，`c` + `dab` 贪心得 4，最优是 3（「思路」第 1、2 步）。 +- `dp[i][j]` 记「还剩 `primary[i:]` 和 `secondary[j:]` 时最少还会产生多少冲突」，放下一个字符的代价是剩下的字符里比它小的个数，用后缀计数表查成 $O(1)$（「思路」第 3、4 步）。 +- 总复杂度 $O(mn)$，两个串都是 1000 位时 Python 约 0.5 秒（「复杂度」）。 + ## 题目 -输入是两个只含小写字母的字符串 `primary` 和 `secondary`，分别代表两个分支（branch）上的提交序列。题面截图给的约束是 1 ≤ |primary|, |secondary| ≤ 1000。每个字符代表一次提交的优先级，字母越小优先级越高（a 最高，z 最低）。 - -要把两个分支合并成一个字符串，而且每个分支内部的提交顺序不能变。换句话说，合并结果是两个串的交错合并（interleaving）：每一步从其中一个串剩下部分的开头取一个字符，接到结果末尾，直到两个串都取完。 - -合并结果里，只要一个低优先级（字母大）的提交排在一个高优先级（字母小）的提交前面，就算一个冲突（conflict）。冲突按「对」计数，每一对这样前大后小的字符算一个。字符串里这种「前面的字符比后面的大」的一对位置叫逆序对（inversion），所以冲突数就是合并串的逆序对数。要注意，**同一个分支内部的对也算**：截图样例 `zcd` 的 2 个冲突里，z、c 都来自 `primary`。题目要求所有合法合并方式里冲突数的最小值，函数是 `getMinimumConflicts(primary, secondary)`，返回 int。 - -相同字母算不算冲突，题面没有明说。这里按「严格更大才算」来实现，理由是规则说的是「低优先级排在高优先级前面」才算冲突，而同一个字母的优先级相同，不满足这个条件。【推断】 +函数是 `getMinimumConflicts(primary, secondary)`，返回 int。输入是两个只含小写字母的字符串 `primary` 和 `secondary`，分别代表两个分支（branch）上的提交序列。题面截图给的约束是 1 ≤ |primary|, |secondary| ≤ 1000。每个字符是一次提交的优先级，字母越小优先级越高（a 最高，z 最低）。 + +要把两个分支合并成一个字符串，每个分支内部的提交顺序不能变。也就是做交错合并（interleaving）：每一步从其中一个串剩下部分的开头取一个字符，接到结果末尾，直到两个串都取完。 + +合并结果里，一个低优先级（字母大）的提交排在一个高优先级（字母小）的提交前面，就算一个冲突（conflict）。冲突按对计数，每一对前大后小的字符算一个。字符串里「前面的字符比后面的大」的一对位置叫逆序对（inversion），所以冲突数就是合并串的逆序对数。题目要所有合法合并方式里冲突数的最小值。 + +> [!note] 同一个分支内部的对也算冲突。截图样例 `zcd` 的 2 个冲突里，z、c 都来自 `primary`。 + +相同字母算不算冲突，题面没有明说。本页按「严格更大才算」实现【推断】，理由是规则说的是低优先级排在高优先级前面才算，同一个字母优先级相同，不满足这个条件。要改成相同也算，只需把后缀计数表改成数「小于等于」，也就是 `build_suffix_less` 里的循环从 `ord(s[i]) - ord("a")` 开始，不加 1。这个改法和「相同也算」的暴力解在 600 组随机小输入上对拍过，全部一致。 ### 样例 -题面截图里的样例是 `primary = "zc"`、`secondary = "d"`。保持各自顺序的合并一共有三种：`zcd` 有 2 个冲突（z 排在 c、d 前面），`zdc` 有 3 个，`dzc` 有 2 个，所以答案是 2。 - -另一篇原帖举了一个计数的例子：合并结果是 `zab` 时，z 排在 a、b 前面，冲突是 2。 - -还有一篇只给了输入：两个分支的 commit history 分别是 `acd` 和 `b`，没有给输出。按上面的规则，可以合并成 `abcd`，答案是 0（这是我算的，不是原帖给的）。 - -### 各篇面经的表述差异 - -给出 `acd`、`b` 这组输入的那一篇，原帖只有一句话：Merging branch，返回 merge 后最少的 commit conflict 数。冲突怎么定义、要不要保持各自顺序，都没有写，所以只能根据题名和输入形式推断它和截图是同一题【推断】。其余几篇写到的规则都和截图一致，没看到别的变体。 - -### 站方 AI 区的内容不可靠 - -论坛网站自己用 AI 整理的那部分内容（下面叫「站方 AI 区」）有几处没有原帖证实，或者算错了，不能直接当期望值用。 - -第一处是数据范围。它写的是 1 ≤ m, n ≤ 2000，并自称是「按常见 OA 约束补全」的，没有原帖证实；截图上写的是 ≤ 1000。 - -第二处是示例。它给了三个：`az` + `b` → 0 是对的；`z` + `a` → 1 和 `az` + `by` → 1 都错了（用暴力枚举核对过）。`z` + `a` 可以合并成 `az`，冲突是 0，它说「唯一合并结果为 za」并不对；`az` + `by` 可以合并成 `abyz`，冲突也是 0。 +截图里的样例是 `primary = "zc"`、`secondary = "d"`。保持各自顺序的合并一共三种： + +| 合并结果 | 冲突的对 | 冲突数 | +| --- | --- | --- | +| `zcd` | (z, c)、(z, d) | 2 | +| `zdc` | (z, d)、(z, c)、(d, c) | 3 | +| `dzc` | (z, c)、(d, c) | 2 | + +答案是 2。另一篇原帖举过一个计数的例子：合并结果是 `zab` 时，z 排在 a、b 前面，冲突是 2。 + +还有一篇只给了输入 `acd` 和 `b`，没给输出。按上面的规则可以合并成 `abcd`，答案是 0（这是本页算的，原帖没给）。 + +### 各篇的表述差异 + +给出 `acd`、`b` 的那篇只写了一句「合并分支，返回 merge 后最少的 commit conflict 数」，冲突怎么定义、要不要保持各自顺序都没写，根据题名和输入形式推断它和截图是同一题【推断】。其余几篇写到的规则都和截图一致，没看到别的变体。 + +### 站方 AI 区的内容不能当期望值 + +一亩三分地站方自己用 AI 整理的那部分内容（下称站方 AI 区）有几处没有原帖证实，或者算错了： + +- 数据范围写的是 1 ≤ m, n ≤ 2000，并自称「按常见 OA 约束补全」，没有原帖证实。截图写的是 ≤ 1000。 +- 三个示例里，`az` + `b` → 0 是对的。`z` + `a` → 1 错了，可以合并成 `az`，冲突是 0，它说「唯一合并结果为 za」并不对。`az` + `by` → 1 也错了，可以合并成 `abyz`，冲突是 0。这两个都用暴力枚举核对过。 ## 面经里怎么考的 -- **2026 年上半年**有一篇（面试在 1–3 月，4 月底发帖），发帖人是一位由招聘人员（recruiter）主动联系的在职跳槽候选人。这篇写得很简略：发帖人只写了一句 Merging branch、返回 merge 后最少的 commit conflict 数，后来在回复里补充说输入是两个分支的 commit history（举例 `acd`、`b`），冲突怎么定义、要不要保持各自顺序都没写。因为没给规则，只能根据题名和输入形式推断它和本题是同一题【推断】。这场 OA 是两道技术题（technical），一共 100 分钟，这道是第一题。发帖人用回溯（backtracking）枚举了所有合并方式、逐个数冲突，事后才意识到应该用 DP，第二天就收到了拒信。这一篇的教训是，合并方式一共有 C(m+n, m) 种，长度到 1000 时回溯不可能跑完；看到「保持各自顺序合并两个串」这类题，应该先想 `dp[i][j]`。 -- 同一场 OA 的第二题是 AI 辅助调试（AI-assisted debugging）：Amazon 的退货系统根据退货历史、商品价值、账号时长等因素打风险分，分数过高时应该判定为不可退，但现在有该拒没拒的情况，要找出系统里的 6 个问题。两道题之后还有一项，帖子原话叫「work style simulation」，是考察工作方式的行为测评，不是编程题。发帖人在回复里还提到：平台是 HackerRank，不用开摄像头，「monitor 会检查」（这句是在回答「会不会检测外接屏幕」，monitor 指显示器还是监考，原话看不出）；两道题可以在开始前分别选编程语言。 -- **2026-08 底到 9 月底**的几篇（发帖人是硕士，多数是在职跳槽）也都把它当作 OA 第一题。有人评价它是「一道字符串 DP，medium 偏 hard」。规则是其中一位发帖人在回复里补的：字母越小优先级越高，两个分支各自保持顺序，低优先级排在高优先级前面就算一个 conflict，求最小值。还有一篇直接贴了题面截图，函数名、样例和长度 ≤ 1000 都来自这张截图；截图左栏分 S1、S2 两段，各一道题，这位发帖人的 OA 结果是通过。 -- 这一时段的面经里，第二题的 AI 调试写到的都是 Spring Boot（Java）项目。一篇是给电影系统的增删改查（CRUD）功能找 bug，要让 6 个单元测试（unit test）通过，AI 只给建议，不能直接帮你改代码；发帖人不熟 Spring Boot，写了 45 分钟，觉得时间很紧。另一篇是电影搜索后端，要求支持部分匹配（partial match）、可以按标题 / 演员 / 全部字段匹配、忽略大小写、按 popularity 等字段排序、只返回已发布的电影。这位发帖人没有准备，第二题 0 个测试通过，自己估计 OA 没过，觉得浪费了一次内推（referral）。第二题的详细整理见 [[q:amazon-oa-ai-debug]]。 -- 各篇都没写这道题通过了多少个测试用例（test case），也没有人贴出自己的解法。 +这道题是 Amazon 社招 SDE OA 编程部分的第一题，2026 年 4 月和 8 到 9 月的帖子里都出现过。编程部分共两题，第二题是 AI 辅助调试，各篇的细节整理在 [[q:amazon-oa-ai-debug]]。 + +4 月那篇写得最简略，教训也最直接。发帖人是招聘人员（recruiter）主动联系的在职跳槽候选人，面试在 1–3 月，4 月底发帖。他的 OA 是两道技术题共 100 分钟，这道是第一题，第二题是给一个退货风险评分系统找 6 个问题的 AI 辅助调试。两道题之后还有一项，帖子原话叫「work style simulation」，是考察工作方式的行为测评，没有编程。他在回复里还提到：平台是 HackerRank，不用开摄像头，两道题可以在开始前分别选编程语言。有人问会不会检测外接屏幕，他答「monitor 会检查」，monitor 指显示器还是监考，原话看不出。 + +这道题他用回溯（backtracking）枚举所有合并方式、逐个数冲突，事后才意识到应该用 DP，第二天收到拒信。合并方式一共有 $\binom{m+n}{m}$ 种，长度到 1000 时回溯不可能跑完。看到「保持各自顺序合并两个串」这类题，应该先想 `dp[i][j]`。 + +8 月底到 9 月底的几篇，发帖人是硕士，多数是在职跳槽，也都把它当作 OA 第一题。规则是其中一位发帖人在回复里补的：字母越小优先级越高，两个分支各自保持顺序，低优先级排在高优先级前面就算一个 conflict，求最小值。另一位直接贴了题面截图，截图左栏分 S1、S2 两段，各一道题，函数名、样例和长度 ≤ 1000 都来自这张截图，这位的 OA 结果是通过。有人评价这题是「一道字符串 DP，medium 偏 hard」。还有一篇只写了「字符串 DP」，按同期另两篇推断是这道题【推断】。 + +这一时段写到的第二题都是 Spring Boot（Java）项目。其中一位抽到电影搜索后端，第二题 0 个测试通过，自己估计 OA 没过，觉得浪费了一次内推（referral）。 + +各篇都没写这道题过了多少个测试用例（test case），也没有人贴出自己的解法。 ## 思路 -### 把冲突看成逆序对 - -冲突就是合并串里的逆序对（inversion），也就是前面的字母比后面的大的一对字符。同一个串内部的逆序对，不管怎么合并都还在，因为合并不会改变串内的先后顺序；真正能选择的，只有两个串之间字符的相对顺序。 - -### 状态和转移 - -这题用二维 DP，不是区间 DP（interval DP，按子区间划分状态的那种）。状态按「两个串各用掉了几个字符」来划分，和 LeetCode 97「交错字符串」（Interleaving String）的状态一样；不过这题本身没有能确认的 LeetCode 原题【推断】。 - -`dp[i][j]` 的含义是：还剩 `primary[i:]` 和 `secondary[j:]` 没有放时，把它们合并，从现在起最少还会产生多少冲突。下一个字符只有两种选法： - -- 下一个放 `primary[i]`。它会排在所有剩下的字符前面，所以新增的冲突数就是剩下的字符里比它小的个数，也就是 `primary[i+1:]` 里比它小的个数加上 `secondary[j:]` 里比它小的个数。它和已经放好的字符之间的冲突，在放那些字符的时候已经算过了，不会重复计算。 -- 下一个放 `secondary[j]`。道理相同，新增的冲突数是 `primary[i:]` 和 `secondary[j+1:]` 里比它小的字符个数。 - -`dp[i][j]` 取这两种选法里较小的那个，最终答案是 `dp[0][0]`。 - -为了让每次转移都是 O(1)，要先给每个串建一张后缀计数表：`less[i][c]` 表示这个串从位置 i 到结尾的这一段（后缀，suffix）里，比字母 c 小的字符有几个。有了这张表，每种选法的新增冲突都只要查表就能得到。 - -还有一种等价的看法：DP 只算两个串之间的冲突，最后再加上两个串各自内部的逆序对数。后者和怎么合并无关，是一个常数。Follow-up 里处理任意整数的写法用的就是这个思路。 - -### 为什么不能贪心 - -直觉上会想到贪心：每一步比较两个串剩下部分的开头字符，取较小的那个。这样做不对。有时候要先把一个字母大的开头字符放出去，排在它后面的小字母才能早点放出来。反例见「易错点」。 +### 1. 回溯为什么不行 + +最直接的做法是枚举所有交错合并，逐个数逆序对。两个串长度分别是 m、n 时，合并方式的数量是从 m+n 个位置里挑 m 个放 `primary` 的字符，即 $\binom{m+n}{m}$。m = n = 10 时已经是 184756 种，m = n = 1000 时远远超出任何时限。4 月那位发帖人就是这样写的。 + +### 2. 贪心为什么不行 + +接下来容易想到贪心：每一步比较两个串剩下部分的开头字符，取较小的那个，相同时先取 `primary`。代码见「代码」一节的 `greedy_conflicts`。 + +反例是 `primary = "c"`、`secondary = "dab"`。贪心先放 c，得到 `cdab`，冲突是 (c, a)、(c, b)、(d, a)、(d, b) 共 4 个。最优是 `dabc`，冲突是 (d, a)、(d, b)、(d, c) 共 3 个。d 虽然大，但它挡在 a、b 前面，先把它放掉，a、b 才能排到 c 前面。贪心只看开头，看不到开头后面藏着的小字母。 + +开头相同（平局）时先取哪一边也会影响结果。`primary = "b"`、`secondary = "ba"` 时，先取 `primary` 的 b 得到 `bba`，冲突 2。最优是 `bab`，冲突 1。平局时改成固定先取 `secondary` 也有反例：`cbaa` + `abbc` 的最优是 7，平局先取 `primary` 的贪心得 9，先取 `secondary` 的得 12。 + +> [!say] Greedily taking the smaller head fails. For "c" and "dab" it gives 4 conflicts, while "dabc" gives 3, because the large "d" is blocking the small "a" and "b" behind it. + +### 3. DP 的状态和转移 + +状态按「两个串各用掉了几个字符」来划分，和 LeetCode 97「交错字符串」（Interleaving String）的状态一样。这题本身没找到对应的 LeetCode 原题，未核实。 + +`dp[i][j]` 的含义是：还剩 `primary[i:]` 和 `secondary[j:]` 没放时，把它们合并，从现在起最少还会产生多少冲突。下一个字符只有两种选法： + +- 下一个放 `primary[i]`。它会排在所有剩下的字符前面，所以新增的冲突数是剩下的字符里比它小的个数，也就是 `primary[i+1:]` 里比它小的个数加上 `secondary[j:]` 里比它小的个数，之后进入状态 `dp[i+1][j]`。 +- 下一个放 `secondary[j]`。道理相同，新增的冲突数是 `primary[i:]` 和 `secondary[j+1:]` 里比它小的个数，之后进入状态 `dp[i][j+1]`。 + +`dp[i][j]` 取两种选法里较小的那个，`dp[m][n] = 0`，答案是 `dp[0][0]`。 + +这样每一对冲突恰好算一次。一对冲突 (x, y) 里 x 在前，它在放 x 的那一步被计入，因为那时 y 还在剩下的字符里。放 y 的时候 x 已经放完，不在剩下的字符里，不会再算一次。同一个串内部的对也走这条路：`primary` 里 z 在 c 前面，放 z 时 c 一定还没放，所以 (z, c) 会被计入。这就是 `zc` + `d` 能算出 2 的原因。 + +> [!say] A conflict is just an inversion in the merged string, so I run a DP over how many characters I've taken from each branch. Placing a character next costs the number of smaller characters still remaining in either branch. + +### 4. 后缀计数表让转移变成 O(1) + +每次转移都要数「某个后缀里比字母 c 小的有几个」，现数是 $O(m+n)$。先给每个串建一张后缀计数表：`less[i][c]` 表示这个串从位置 i 到结尾的那一段（后缀，suffix）里，字母编号小于 c 的字符有几个，c 取 0 到 25，a 的编号是 0。从后往前建，`less[i]` 是 `less[i+1]` 的拷贝，再把比 `s[i]` 大的那些列各加 1。建好之后，放 `primary[i]` 的代价就是 `p_less[i+1][c] + s_less[j][c]`，两次查表。 + +> [!say] With suffix counts each transition is O(1), so the whole DP is O(m·n), about a million states for two strings of length 1000. ## 代码 -已运行（Python 3.12）。截图样例和下面「测试用例」表里的每一行都得到了期望结果。另外还用暴力解在随机小数据上对比了结果（对拍）：暴力解枚举所有交错合并、直接数逆序对，一共比了 1200 组随机字符串（长度 1–7，字母表分别取 ab、abc、abcde 和全部 26 个字母），结果全部一致。输入是两个长度都是 1000 的随机串时，本机运行约 0.6 秒。 +正解： ```python +ALPHABET = 26 + + +def build_suffix_less(s: str) -> list[list[int]]: + """less[i][c] = s[i:] 里字母编号小于 c 的字符个数（c 取 0..25，a 的编号是 0）。""" + less = [[0] * ALPHABET for _ in range(len(s) + 1)] + for i in range(len(s) - 1, -1, -1): + row = less[i + 1][:] + for c in range(ord(s[i]) - ord("a") + 1, ALPHABET): + row[c] += 1 + less[i] = row + return less + + def getMinimumConflicts(primary: str, secondary: str) -> int: m, n = len(primary), len(secondary) - - def suffix_less(s): - # less[i][c] = s[i:] 里比字母 c 小的个数（c = 0..26） - less = [[0] * 27 for _ in range(len(s) + 1)] - for i in range(len(s) - 1, -1, -1): - less[i] = less[i + 1][:] - v = ord(s[i]) - 97 - for c in range(v + 1, 27): - less[i][c] += 1 - return less - - lp, ls = suffix_less(primary), suffix_less(secondary) - INF = float("inf") - # dp[i][j] = 剩下 primary[i:] 和 secondary[j:] 时，后面最少还会产生多少冲突 - dp = [[INF] * (n + 1) for _ in range(m + 1)] - dp[m][n] = 0 + p_codes = [ord(ch) - ord("a") for ch in primary] + s_codes = [ord(ch) - ord("a") for ch in secondary] + p_less = build_suffix_less(primary) + s_less = build_suffix_less(secondary) + + # dp[i][j]：还剩 primary[i:] 和 secondary[j:] 没放时，从现在起最少还会产生的冲突数 + dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m, -1, -1): for j in range(n, -1, -1): if i == m and j == n: continue - best = INF - if i < m: # 下一个放 primary[i]：它排在所有剩余字符前面 - c = ord(primary[i]) - 97 - best = dp[i + 1][j] + lp[i + 1][c] + ls[j][c] + best = None + if i < m: # 下一个放 primary[i]，它排在所有剩下的字符前面 + c = p_codes[i] + best = dp[i + 1][j] + p_less[i + 1][c] + s_less[j][c] if j < n: # 下一个放 secondary[j] - c = ord(secondary[j]) - 97 - best = min(best, dp[i][j + 1] + lp[i][c] + ls[j + 1][c]) + c = s_codes[j] + cost = dp[i][j + 1] + p_less[i][c] + s_less[j + 1][c] + best = cost if best is None else min(best, cost) dp[i][j] = best return dp[0][0] @@ -106,64 +144,57 @@ ``` +「思路」第 2 步的错误做法，用来和正解并排跑： + +```python +def count_inversions(s: str) -> int: + return sum(1 for i in range(len(s)) for j in range(i + 1, len(s)) if s[i] > s[j]) + + +def greedy_conflicts(primary: str, secondary: str) -> int: + """错误做法：每一步取两个开头里较小的那个，相同时先取 primary。""" + i = j = 0 + merged = [] + while i < len(primary) or j < len(secondary): + if j == len(secondary) or (i < len(primary) and primary[i] <= secondary[j]): + merged.append(primary[i]) + i += 1 + else: + merged.append(secondary[j]) + j += 1 + return count_inversions("".join(merged)) +``` + +2026-10-27 用 Python 3.13.17 跑过：正解的 `__main__` 输出 2、0、3。「测试用例」表里 11 组输入，正解和暴力解（枚举所有交错合并、直接数逆序对）都等于期望值，贪心在 `c` + `dab`、`b` + `ba` 两组上算错。另外用固定随机种子生成 1200 组随机输入（每个串长 1 到 7，字母表分别取 ab、abc、abcde 和全部 26 个字母，各 300 组）和暴力解对拍，正解 0 组不一致，贪心有 439 组和暴力解不一致。两个串都是 1000 位随机字母时，正解先后跑 6 次，每次 0.45 到 0.53 秒。 + ## 复杂度 -- 时间复杂度是 O(m·n)。`dp` 数组大约有 m·n 格，每一格只做常数次查表和一次取最小值；预先建后缀计数表另外需要 O(27·(m+n))，其中 27 是后缀计数表每个位置的列数（代码里 `c` 取 0..26）。m、n ≤ 1000 时大约是 10^6 次转移，Python 在本机约 0.6 秒。HackerRank 上 Python 的时限是多少，未核实。 -- 空间上，`dp` 数组占 O(m·n)，后缀计数表 `lp`、`ls` 占 O(27·(m+n))。算 `dp` 的一格时只用到下一行和本行右边一格，所以 `dp` 可以只保留两行、轮流覆盖使用（滚动数组，rolling array），降到 O(n)；加上后缀计数表，总空间是 O(m+n)。 +- 时间 $O(mn)$。`dp` 有 $(m+1)(n+1)$ 格，每格两次查表、一次取最小值。建后缀计数表另需 $O(26(m+n))$。m、n 都是 1000 时约 $10^6$ 次转移，本机 Python 约 0.5 秒。HackerRank 上 Python 的时限是多少，未核实。 +- 空间上 `dp` 占 $O(mn)$，两张后缀计数表占 $O(26(m+n))$。算 `dp[i][j]` 只用到下一行的 `dp[i+1][j]` 和本行右边的 `dp[i][j+1]`，所以 `dp` 可以只留两行轮流覆盖（滚动数组，rolling array），降到 $O(n)$。 + +> [!optional] Java、C++ 里用 int 就够。冲突数最多是合并串里任取两个字符的对数 $\binom{2000}{2} \approx 2 \times 10^6$，远小于 int 的上限。 ## 易错点 -- **别把冲突方向数反。** 只有大字母在前、小字母在后才算冲突。 -- **相同字母不算冲突【推断】。** 题面没有明说；规则是「低优先级排在高优先级前」才算冲突，这要求前面的字母严格更大。 -- **串内的逆序对也要算。** 截图里 `zcd` 的 2 个冲突包含同在 `primary` 里的 z、c。如果 DP 只算两个串之间的冲突，最后要把两个串各自内部的逆序对数加回去，否则 `zc` + `d` 会得到 1，而不是 2。 -- **贪心「每次取较小的开头字符」是错的。** 以 `c` + `dab` 为例，贪心先放 c，得到 `cdab`，冲突 4；最优是 `dabc`，冲突 3。d 虽然大，但先把它放掉，后面的 a、b 才能提前。两个开头字符相同（平局）时先取哪一边，也会影响结果：`b` + `ba`，先取 `primary` 的 b，得到 `bba`，冲突 2；最优是 `bab`，冲突 1。而且无论平局时固定先取哪一边，都有反例：`cbaa` + `abbc` 的最优是 7，两种平局规则下的贪心分别得 9 和 12。 -- **不要回溯枚举所有合并。** 合并方式一共有 C(m+n, m) 种，长度到 1000 时不可能跑完。上半年那位收到拒信的发帖人就是这么写的。 -- **注意下标。** 放 `primary[i]` 时，剩下的字符是 `primary[i+1:]` 和 `secondary[j:]`，不包括它自己，所以查 `lp[i + 1]`、`ls[j]`；放 `secondary[j]` 时查 `lp[i]`、`ls[j + 1]`。 -- **别拿站方 AI 区的示例当期望值。** 它给的 `z` + `a` → 1、`az` + `by` → 1 都是错的，正确答案都是 0。 -- **Java / C++ 用 int 就够。** 冲突数最多是合并串里任取两个字符的组合数 C(2000, 2) ≈ 2×10^6，远小于 int 的上限。 +- **方向别数反。** 只有大字母在前、小字母在后才算冲突。 +- **串内的逆序对也要算。** `zc` + `d` 的答案是 2，其中 (z, c) 来自同一个串。只算两串之间的冲突会得到 1。本页的 DP 在放 z 时把剩下的 c 也数进去了，见「思路」第 3 步。 +- **贪心是错的。** `c` + `dab` 贪心得 4，最优是 3。平局怎么定都有反例，见「思路」第 2 步。 +- **下标差一。** 放 `primary[i]` 时剩下的是 `primary[i+1:]` 和 `secondary[j:]`，不含它自己，所以查 `p_less[i + 1]`、`s_less[j]`。放 `secondary[j]` 时查 `p_less[i]`、`s_less[j + 1]`。 +- **别拿站方 AI 区的示例对答案。** 它的 `z` + `a` → 1、`az` + `by` → 1 都是错的，正确答案都是 0。 ## 测试用例 -| primary | secondary | 期望 | 说明 | -| --- | --- | --- | --- | -| `zc` | `d` | 2 | 截图样例 | -| `acd` | `b` | 0 | 发帖人给的输入；期望值是我算的（合并成 `abcd`） | -| `a` | `a` | 0 | 相同字母不算冲突【推断】 | -| `b` | `a` | 0 | 合并成 `ab` | -| `z` | `a` | 0 | 站方 AI 区写的是 1，错了 | -| `az` | `by` | 0 | 站方 AI 区写的是 1，错了（可以合并成 `abyz`） | -| `zyx` | `a` | 3 | `zyx` 自身的 3 个逆序对怎么合并都在；把 a 放最前面，就不会再新增 | -| `cba` | `cba` | 9 | 两个串内部的逆序对是 3 + 3，两串之间最少还有 3 个 | -| `zzzzz` | `aaaaa` | 0 | 把整串 a 先放 | -| `c` | `dab` | 3 | 贪心的反例（贪心得 4） | -| `b` | `ba` | 1 | 平局的反例（先取 `primary` 的 b 得 2） | -| 随机 1000 位 | 随机 1000 位 | — | 只测运行时间，本机约 0.6 秒 | - -## Follow-up - -### 输出一个最优的合并串 - -如果要的不只是最小冲突数，还要给出一个最优合并串，可以在算 DP 时给每一格记下选的是哪一边，然后从 `(0, 0)` 出发，按记下的选择一步步走到 `(m, n)`，沿途依次放下的字符就是一个最优合并结果。 - -### 省内存 - -`dp` 数组可以滚动成两行，占 O(n)；加上后缀计数表，总空间是 O(m+n)。原因见「复杂度」一节。 - -### 字符换成任意整数（不止 26 个字母） - -后缀计数表的大小和字母表大小成正比，因为每个位置都要记下「比每一种可能的值小的有几个」。元素换成任意整数后，值域可能很大，这张表就不适用了。这时可以改成让 DP 只算两个串之间的冲突： - -- `dp[i][j]` 定义为合并 `primary[:i]` 和 `secondary[:j]`（两个串的前缀，prefix）时，两串之间的最少冲突数。 -- 如果最后放的是 `primary[i-1]`，`secondary[:j]` 的字符都排在它前面，新增的代价就是 `secondary[:j]` 里比它大的个数。i 固定时，这个个数可以随 j 增大逐个累加出来。 -- 如果最后放的是 `secondary[j-1]`，代价是 `primary[:i]` 里比它大的个数。为此维护一个长度为 n 的数组，记下每个位置 j 对应的这个个数，随 i 增大逐格更新。 - -这样复杂度仍是 O(m·n)，而且和值域无关。最后再加上两个串各自内部的逆序对数，可以用归并排序（merge sort）或树状数组（Fenwick tree，一种单点更新和前缀计数都只要 O(log L) 的数组结构）在 O(L log L) 内算出，L 是串的长度。这个写法另外运行过（代码没有放进正文），也用暴力解在随机数据上对比过结果（对拍）：300 组随机整数列表（长度 1–6，取值 −5 到 5），加上前面那 1200 组随机字符串，结果全部一致。 - -### k 个分支 - -如果要合并 k 个分支，状态要记下每个分支各用掉了几个字符，变成 k 维，状态数是各串长度的乘积，k 大了就不可行。【推断】面试里把这个复杂度说清楚即可。 - -## 英文讲法 - -> [!say] A conflict is just an inversion in the merged string, so I run a DP over how many characters I've taken from each branch; placing a character next costs the number of smaller characters still remaining in either branch. - -> [!say] Greedily taking the smaller head doesn't work — for "c" and "dab" it gives 4 conflicts, while "dabc" gives 3 — so I use an O(m·n) DP, about a million states when both strings have length 1000, with suffix counts making each transition O(1). +| primary | secondary | 期望 | 正解 | 暴力 | 贪心 | 说明 | +| --- | --- | --- | --- | --- | --- | --- | +| `zc` | `d` | 2 | 2 | 2 | 2 | 截图样例 | +| `acd` | `b` | 0 | 0 | 0 | 0 | 原帖给的输入，期望值是本页算的（合并成 `abcd`） | +| `a` | `a` | 0 | 0 | 0 | 0 | 相同字母不算冲突【推断】 | +| `b` | `a` | 0 | 0 | 0 | 0 | 合并成 `ab` | +| `z` | `a` | 0 | 0 | 0 | 0 | 站方 AI 区写的是 1 | +| `az` | `by` | 0 | 0 | 0 | 0 | 站方 AI 区写的是 1，可以合并成 `abyz` | +| `zyx` | `a` | 3 | 3 | 3 | 3 | `zyx` 自身的 3 个逆序对怎么合并都在 | +| `cba` | `cba` | 9 | 9 | 9 | 9 | 串内 3 + 3，两串之间最少还有 3 | +| `zzzzz` | `aaaaa` | 0 | 0 | 0 | 0 | 整串 a 先放 | +| `c` | `dab` | 3 | 3 | 3 | 4 | 贪心的反例 | +| `b` | `ba` | 1 | 1 | 1 | 2 | 平局的反例 | + +此外用两个 1000 位随机串只测运行时间，结果见「代码」一节末尾。
meta
@@ -1 +1,5 @@ -{} +{ + "depth_guide": "2026-10-23", + "rewritten_by": "cloud:20261026-2313", + "rewritten_at": "2026-10-27" +}