力扣 767要求重新排列小写字母让相邻字符不同。能做到就返回任意合法排列否则返回空字符串。例如 aab 可以变成 abaaaab 无解。我原来的解法是统计次数先处理出现最多的字母放在 0、2、4……位置剩余字母继续隔位填偶数位置用完就回到 1、3、5……。代码不长但“为什么这样放就行”不能只用一句“与上一题一样”带过。1. 先问什么时候根本不可能假设最多的字符是 a共 M 个其余字符共 n-M 个。要隔开 M 个 a至少需要 M-1 个其他字符a _ a _ a _ a 至少需要三个分隔字符因此 M-1 n-M也就是 M (n1)/2。代码用整数除法右边相当于向上取整的 n/2。输入最多次数 M允许上限判断aab22可以构造aaab32无解aaabc33正好到边界aaabbc33正好到边界这解释了“为什么超过上限必定无解”。接下来还要用构造解释“不超过时能做到”。2. 先把最难安排的字符分开长度为 n 的数组偶数下标有 (n1)/2 个刚好等于允许上限。先让出现最多的字母占用它们两个相同字母之间至少留一个位置。例如 aaabbc下标012345先放三个 aa空a空a空再放两个 bababa空最后放 cababac得到 ababac。先安排次数最多的字符是避免后面留下一个比空位容量还难放的大块。原图里“超过一半”的表述要按前面的整数上限理解。奇数长度中最多字符比 n/2 略多仍可行比如 aaabc不能按浮点的一半直接拒绝。3. 偶数位转到奇数位会不会碰在一起填充顺序不是 0、1、2、3而是长度 70 - 2 - 4 - 6 - 1 - 3 - 5同一种字母会连续占用这条填充顺序中的一段。完全落在偶数位或奇数位时显然隔着一个位置。真正要检查的是同一种字母跨过“6 - 1”这个转折。例如 aabbccd先放 aa _ a _ _ _ _ 再放 ba _ a _ b _ b 再放 ca c a c b _ b 最后 da c a c b d b这里 b 用完偶数位c 从奇数位开始两种不同字母当然没问题。若一个字母本身跨过转折也不能只靠这个例子说明安全。设偶数位总数为 E跨转折的某字母从第 r 个偶数位置开始一共 t 个。它在偶数部分最靠左的位置是 2r放完剩余偶数位后奇数部分最靠右的位置是 2(t-Er)-1。当 t E后一个位置至多是 2r-3两部分至少还隔着一个位置不会相邻。若 t E它也是最大次数先放的最多字符已经占满全部偶数位这个剩余字母只能从奇数位开始根本不会跨两部分。这就是“先放最多的再隔位填剩下字符”的关键边界。不是只要随便按 0、2、4、1、3、5 放就一定安全。4. Java 实现保留原方法补注释输入按原题限定为非空小写字母字符串。class Solution { public String reorganizeString(String s) { int[] count new int[26]; int maxLetter 0; for (int i 0; i s.length(); i) { int letter s.charAt(i) - a; count[letter]; if (count[letter] count[maxLetter]) maxLetter letter; } int n s.length(); if (count[maxLetter] (n 1) / 2) return ; char[] result new char[n]; int index 0; for (int i 0; i count[maxLetter]; i) { result[index] (char) (a maxLetter); index 2; } count[maxLetter] 0; for (int letter 0; letter 26; letter) { for (int i 0; i count[letter]; i) { if (index n) index 1; result[index] (char) (a letter); index 2; } } return new String(result); } }统计和填充都只处理线性数量的字符26 字母扫描为固定开销时间 O(n)。计数表和下标等工作空间 O(1)结果数组 O(n)Java 创建返回字符串也可能涉及线性存储不能说程序整体只占常数空间。5. 怎么测一个答案不唯一的题输入 aabbabab 与 baba 都合法。把期望答案写死成 abab会错判正确算法。本次实际编译运行正文 Java非空输出必须同时满足长度相同、每种字母次数相同、相邻字母不同。短输入是否有解由一个回溯程序独立判断每次试放一个与前一字符不同且还有剩余数量的字母全部放完才算成功不使用前面的数量公式作为裁判。测试覆盖四种字母的短计数分布以及长输入、奇偶长度、边界和无解情况还故意把 (n1)/2 写成 n/2检查测试能否抓到错误拒绝奇数长度的情况。计数分布枚举不是枚举全部输入排列但本算法只依赖计数和最多字母的选择。并列最多的字母可能因原顺序不同而选中不同字母因此另测了不同输入顺序不要求每次返回同一个字符串。这道题值得记住的不是“下标加二”而是先用分隔空位找出不可能条件再把这个条件变成可行的放置方案最后用约束而不是固定字符串来验证结果。