LeetCode 767 Reorganize String贪心判据 三种重排策略深度解析leetcode1 仓库实践【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇基于 leetcode1 仓库中的 articles/reorganize-string.md 一文展开系统讲解 LeetCode 767「重排字符串」的三个核心解法线性扫频贪心、最大堆延迟重入、偶数下标间隔放置并对照仓库内 python/0767-reorganize-string.py、java/0767-reorganize-string.java 等多语言实现帮助你掌握「可行性判据 贪心/堆」这一类字符重排问题的完整解题框架。1. 题目与前置知识给定一个字符串s要求重新排列其中的字符使得任意两个相邻字符都不相同若存在多个合法结果返回任意一个即可若无法做到则返回空字符串。例如输入aab→ 输出aba合法相邻字符不同输入aaab→ 输出a出现 3 次超过(311)/2无法重排。原文档「Prerequisites」部分指出了三道前置技能这三点也正是本文三个解法共同依赖的基石前置技能含义在本题中的体现频率统计Frequency Counting用数组或哈希表统计字符出现次数三个解法的第一步都是 26 位freq数组或Counter贪心算法Greedy做局部最优选择优先放最高频字符以获得全局解解法一、三的核心思想堆 / 优先队列Heap / Priority Queue高效取出当前最大频率元素解法二的核心数据结构1.1 关键可行性判据三个解法共享同一个「无解」判据若某个字符出现次数超过(n 1) / 2整除向上取整即(n 1) // 2则必然无解。直觉上可以这样理解把字符串想象成一排座位最频繁的那个字符最多只能占据全部「隔位」座位0, 2, 4, ...这些隔位座位的总数恰好是(n 1) / 2。一旦某个字符的数量超过这个上限无论怎么排它都不可避免地出现相邻。这一判据在文档「Common Pitfalls」中也被列为第一个易错点写成n / 2或忘记向上取整会导致误判——要么拒绝了本可解的输入要么放行了无解输入。2. 解法一频率统计 线性扫描最大值2.1 直觉Intuition为避免相邻重复我们应每次放置剩余字符中频率最高的那个然后放置第二高的。这样在「两个最高频字符之间来回交替」能最大程度拉开相同字符的间距。贪心成立的原因只要可行性判据通过「先放最高频、再放次高频」的局部选择永远不会把局面推向死局。2.2 算法步骤原文档给出的完整算法如下用freq数组统计每个字符的频率若最大频率超过(n 1) / 2直接返回空字符串构建结果res的过程中每轮循环找到频率最高的字符下标maxIdx追加到结果中若该字符还有剩余次数则临时把它「隐藏」置为负无穷再找出第二高频字符追加第二字符然后恢复第一个字符的计数。返回res。这里有一个非常值得注意的实现技巧——用负无穷「遮蔽」刚用过的字符因为不能连续放置同一个字符找到最高频后先减一次计数再用float(-inf)Python/Integer.MIN_VALUEJava/INT_MINC/-InfinityJavaScript临时压掉它的值让findMax自然选出「次高」取完后立即恢复。这比显式写「排除 maxIdx 再扫一遍」的循环代码更简洁。2.3 参考实现Pythonclass Solution: def reorganizeString(self, s: str) - str: freq [0] * 26 for char in s: freq[ord(char) - ord(a)] 1 max_freq max(freq) if max_freq (len(s) 1) // 2: return res [] while len(res) len(s): maxIdx freq.index(max(freq)) char chr(maxIdx ord(a)) res.append(char) freq[maxIdx] - 1 if freq[maxIdx] 0: continue tmp freq[maxIdx] freq[maxIdx] float(-inf) nextMaxIdx freq.index(max(freq)) char chr(nextMaxIdx ord(a)) res.append(char) freq[maxIdx] tmp freq[nextMaxIdx] - 1 return .join(res)同构的 Java 版本原文档完整给出findMaxIndex为线性扫描的私有辅助方法public class Solution { public String reorganizeString(String s) { int[] freq new int[26]; for (char c : s.toCharArray()) { freq[c - a]; } int maxFreq Arrays.stream(freq).max().getAsInt(); if (maxFreq (s.length() 1) / 2) { return ; } StringBuilder res new StringBuilder(); while (res.length() s.length()) { int maxIdx findMaxIndex(freq); char maxChar (char) (maxIdx a); res.append(maxChar); freq[maxIdx]--; if (freq[maxIdx] 0) { continue; } int tmp freq[maxIdx]; freq[maxIdx] Integer.MIN_VALUE; int nextMaxIdx findMaxIndex(freq); char nextMaxChar (char) (nextMaxIdx a); res.append(nextMaxChar); freq[maxIdx] tmp; freq[nextMaxIdx]--; } return res.toString(); } private int findMaxIndex(int[] freq) { int maxIdx 0; for (int i 1; i freq.length; i) { if (freq[i] freq[maxIdx]) { maxIdx i; } } return maxIdx; } }2.4 复杂度分析时间复杂度 $O(n)$每轮循环最多做两次 26 长度数组的线性扫描而循环总次数为 $O(n)$由于 26 是常数总复杂度仍为 $O(n)$。空间复杂度额外空间 $O(1)$最多 26 个不同字符输出字符串 $O(n)$。原文档为该解法提供了 Python、Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust 共 9 种语言实现核心骨架完全一致26 位频率数组 「负无穷遮蔽」的次高选择。3. 解法二频率统计 最大堆延迟重入3.1 直觉Intuition相比解法一「每轮线性扫描找最大值」最大堆能在 $O(1)$ 量级内直接取到当前频率最高的字符堆大小上界为 26$\log 26$ 为常数。解法二的关键机制是prev延迟重入弹出堆顶字符放入结果后不立即把它剩余计数塞回堆里而是暂存到prev等下一轮处理完另一个字符后再把prev推回堆中。这一「隔一轮再放回」的延迟机制从数据结构层面保证了同一字符绝不会被连续取出。若堆已空但prev手中还压着待放字符说明无解。3.2 算法步骤统计频率构建(count, character)对的最大堆维护一个prev元素表示刚刚用过、本轮不能复用的字符当maxHeap非空或prev存在时循环若prev存在但maxHeap为空返回空字符串无解弹出堆顶元素cnt将其字符追加进res并将cnt减 1若prev存在将其重新入堆若当前元素计数仍为正将其存为新的prev。返回res。3.3 参考实现Pythonclass Solution: def reorganizeString(self, s: str) - str: count Counter(s) maxHeap [[-cnt, char] for char, cnt in count.items()] heapq.heapify(maxHeap) prev None res while maxHeap or prev: if prev and not maxHeap: return cnt, char heapq.heappop(maxHeap) res char cnt 1 # 注意堆里存的是负数1 等价于实际计数 -1 if prev: heapq.heappush(maxHeap, prev) prev None if cnt ! 0: prev [cnt, char] return res注意 Python 版的堆元素是[-cnt, char]负数实现最大堆语义所以「取出一位」体现为cnt 1而非cnt - 1Java / C / Kotlin / Rust 等版本直接使用正计数 自定义比较器写法上更直白。3.4 仓库源码交叉验证prev机制的三种等价变体仓库中针对本题收录了多种语言实现README.md 第 299 行的完成度表中登记了cpp、java、javascript、kotlin、python五个 ✔️ 文件。逐一对比源码可以看到「延迟重入」思想在工程实现里有至少三种等价变体变体 Aprev缓冲与文档解法二一致python/0767-reorganize-string.py 就是标准的prev缓冲写法带详尽注释class Solution: def reorganizeString(self, s: str) - str: count Counter(s) # Hashmap, count each char maxHeap [[-cnt, char] for char, cnt in count.items()] heapq.heapify(maxHeap) # O(n) prev None res while maxHeap or prev: if prev and not maxHeap: return # most frequent, except prev cnt, char heapq.heappop(maxHeap) res char cnt 1 if prev: heapq.heappush(maxHeap, prev) prev None if cnt ! 0: prev [cnt, char] return reskotlin/0767-reorganize-string.kt 的第一个解法同样是prev缓冲且用while (maxHeap.isNotEmpty() || prev ! null)维持「堆空但 prev 未消」的循环条件——这是prev写法中最容易漏掉的边界循环条件必须覆盖prev单独存活的情况。变体 B检查结果串尾字符tail checkjava/0767-reorganize-string.java 换了一个思路不显式维护prev而是直接比较堆顶字符与结果串最后一个字符——若相同则把堆顶「挂起」改弹第二个字符若此时第二个不存在temp2 null则返回Map.EntryCharacter, Integer temp1 pq.poll(); if (sb.length() 0 || sb.charAt(sb.length() - 1) ! temp1.getKey()) { sb.append(temp1.getKey()); temp1.setValue(temp1.getValue() - 1); } else { //the character is same //hold the current character and look for the 2nd most frequent character Map.EntryCharacter, Integer temp2 pq.poll(); //if there is no temp2 ... no way to avoid adjacent duplicate values if (temp2 null) return ; sb.append(temp2.getKey()); temp2.setValue(temp2.getValue() - 1); if (temp2.getValue() ! 0) pq.offer(temp2); } if (temp1.getValue() ! 0) pq.offer(temp1);javascript/0767-reorganize-string.js 也是 tail check 变体orgStr[orgStr.length - 1] char时改取次高其文件头注释标注了MaxHeap | Hashing, Time O(n*log(n)) | Space O(n)——由于它基于字符哈希表而非 26 位数组复杂度表述上多了一个 $\log n$ 的堆因子。变体 C一次弹两个pairwise popcpp/0767-reorganize-string.cpp 采用了第三种节奏主循环每次成对弹出堆顶两个字符依次放入结果再按剩余计数重新入堆循环结束后若堆中还剩一个元素且其计数大于 1返回否则追加最后一个字符。文件头注释明确标注Time: O(NlogN), Space: O(N)基于unordered_map建堆。这种「成对消费」从节奏上天然避开了相邻重复等价于把解法二的「弹一个、延迟一个」压缩成「弹两个」的批量操作。三种变体殊途同归其正确性都源自同一不变式任一时刻刚被放置的字符在下一个字符落地前不可再被取出。从源码结构看选prev缓冲的好处是失败判断prev heap.empty()非常显式选 tail check 则省去一个变量代价是每次多一次与结果串的比较选 pairwise 写法则代码最紧凑但收尾判断需要单独处理。3.5 复杂度分析时间复杂度 $O(n)$文档标注为 $O(n)$。严格来说堆操作是 $O(\log k)$$k$ 为不同字符数本题上界 26由于 $\log 26$ 是常数整体仍为 $O(n)$。仓库 JS 实现基于哈希表建堆的 $O(n \log n)$ 表述正对应「$k$ 不受 26 上界约束时」的一般情形。空间复杂度额外 $O(1)$最多 26 种字符输出 $O(n)$。4. 解法三频率统计 偶数下标贪心放置4.1 直觉Intuition前两个解法是「逐字符决定下一个放谁」解法三换了个视角预先确定位置再往位置里填字符。先把最频繁的字符全部填进偶数下标0, 2, 4, ...——偶数位彼此间隔一个位置天然保证这些字符互不相邻偶数位放满后剩余字符继续从当前idx以步长 2 填入idx越界超过n时回绕到idx 1从奇数位继续。这个「隔位填充 回绕」把解法一/二的运行时贪心转化成了静态的位置规划问题。4.2 算法步骤统计freq找出频率最高的字符下标maxIdx若最大频率超过(n 1) / 2返回空字符串可行性判据第三次登场将最高频字符依次放入下标 0, 2, 4, ... 直到放完对其余所有字符i从当前idx开始、步长 2 依次放置当idx超出n时回绕为idx 1继续填奇数位置。返回res。4.3 参考实现Python / Goclass Solution: def reorganizeString(self, s: str) - str: freq [0] * 26 for char in s: freq[ord(char) - ord(a)] 1 max_idx freq.index(max(freq)) max_freq freq[max_idx] if max_freq (len(s) 1) // 2: return res [] * len(s) idx 0 max_char chr(max_idx ord(a)) while freq[max_idx] 0: res[idx] max_char idx 2 freq[max_idx] - 1 for i in range(26): while freq[i] 0: if idx len(s): idx 1 res[idx] chr(i ord(a)) idx 2 freq[i] - 1 return .join(res)Go 版本的关键片段回绕逻辑if idx len(s) { idx 1 }是所有语言实现中最容易写错的一行res : make([]byte, len(s)) idx : 0 maxChar : byte(maxIdx a) for freq[maxIdx] 0 { res[idx] maxChar idx 2 freq[maxIdx]-- } for i : 0; i 26; i { for freq[i] 0 { if idx len(s) { idx 1 } res[idx] byte(i a) idx 2 freq[i]-- } } return string(res)4.4 回绕为什么必然安全初看回绕到idx 1似乎有风险奇数位填完后继续idx 2会不会撞上偶数位不会。偶数下标已被最高频字符「占满或占空」剩余字符只可能填入还没被写过的奇数下标而回绕只发生在偶数下标全部用尽之后此时idx 1, 3, 5, ...恰好就是所有剩余空位的下标集合。这也是文档 Common Pitfalls 中第二个陷阱的正面表述若忘记在越界后把idx重置为 1就会越界或错放位置。4.5 复杂度分析时间复杂度 $O(n)$每个字符只做一次放置for i in range(26)的外层循环是常数。空间复杂度额外 $O(1)$26 位频率数组输出 $O(n)$。4.6 仓库佐证Kotlin 文件中的「双解法」kotlin/0767-reorganize-string.kt 在同一个文件里收录了两个Solution类第一个是解法二最大堆 prev第二个标注// another solution without heap正是解法三的偶数下标回绕实现先判maxFreq (s.length 1) / 2再以i 2填充、越界时if (i s.lastIndex) i 1。这份源码同时印证了三件事解法三确实无需堆结构可行性判据在「先放最高频」路径中不可省略回绕判断用的是i s.lastIndex即i s.length等价写法。5. 三解法横向对比与选型建议维度解法一线性扫频贪心解法二最大堆 prev解法三偶数下标放置核心数据结构26 位频率数组最大堆上界 26 个元素prev26 位频率数组 结果槽位无解判据前置max_freq (n1)//2运行时prev heap.empty()前置max_freq (n1)//2相邻约束的保证方式负无穷遮蔽 次高选择延迟一轮再重入堆隔位放置 回绕时间复杂度$O(n)$$O(n)$堆上界 26$O(n)$额外空间$O(1)$$O(1)$$O(1)$适用直觉想「每轮挑最大」又不想引入堆字符集较大 / 需要通用堆框架追求最简实现与最少分支选型上字符集固定为 26 个小写字母时三种解法复杂度同为 $O(n)$解法三代码量最小、分支最少是工程上的推荐实现当字符集扩大到任意 Unicode 范围时「26 位数组 线性扫描」的前提不再成立解法二的堆方案是自然外推仓库 JS 实现即为任意字符哈希版本。解法则介于两者之间适合不想引入堆、又要支持较大字符集的中间地带。6. 常见陷阱Common Pitfalls原文档末尾归纳的三个陷阱结合三个解法的代码逐条对应6.1 无解判据写错无解条件是最高频字符出现次数超过(n 1) / 2。写成n / 2或忘记向上取整会误拒合法输入或放行无解输入。例如n 4时上限为(41)/2 2某字符出现 2 次可解、3 次无解。6.2 解法三的下标错放偶数下标0, 2, 4, ...必须先填完才回绕到奇数下标。忘记在越界后把idx重置为 1会导致数组越界或位置错放。对照 kotlin/0767-reorganize-string.kt 中的if (i s.lastIndex) i 1这是回绕的唯一正确形式。6.3 堆解法中立即重入堆方案里刚使用的字符必须扣留一轮再重新入堆。若弹出后立即推回下一轮 pop 仍可能取到它直接产生相邻重复。三个仓库实现python 的prev、java 的 tail check、cpp 的成对弹出从三种不同角度规避了同一陷阱。7. 仓库相关文件索引文件内容articles/reorganize-string.md本文主体来源前置知识 三解法9 语言实现 复杂度 陷阱python/0767-reorganize-string.py最大堆 prev缓冲解法二标准形态带注释java/0767-reorganize-string.java最大堆 结果串尾字符检查变体cpp/0767-reorganize-string.cpp最大堆成对弹出变体$O(N \log N)$ 标注javascript/0767-reorganize-string.js任意字符哈希 MaxPriorityQueue 尾检查变体kotlin/0767-reorganize-string.kt同文件双解法堆版 无堆偶数下标版README.md0767 题完成度登记行cpp / java / javascript / kotlin / python以上路径均可在 leetcode1 仓库中直接查阅三套解法的完整 9 语言代码请回到 articles/reorganize-string.md 对应章节获取。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考