17370845950

本文详解 leetcode “dota 2 senate” 问题中常见的逻辑错误——在 for 循环中直接修改正在遍历的列表导致跳过元素，并提供基于分组+循环链表的高效、正确解法。

你在 DRRD 测试用例中得到 "Radiant"（错误）而非预期的 "Dire"，根本原因在于在 for senator in senators: 循环中调用 senators.remove(...) 动态修改列表长度。Python 的 for 循环底层通过索引递增遍历，当删除前方元素后，后续元素整体前移，但循环索引仍按原步进递增，从而跳过紧邻被删元素之后的那个元素。

以 ['D','R','R','D'] 为例：

• 初始索引 i=0 → 取 'D'，执行 remove("R") → 列表变为 ['D','R','D']；
• 下次索引 i=1 → 实际取到的是原索引 2 的 'R'（即第二个 'R'），而原索引 1 的 'R' 已被跳过；
• 接着 i=2 → 取 'D'，再删 "R" → 列表变为 ['R','D']；
• 此时循环结束（因原列表长度为 4，只迭代了 3 次），最后一个 'D' 在首轮未被处理，导致策略失真。

更深层问题在于：贪心删除“第一个出现的对手”并非最优策略。游戏规则是“按顺序轮流禁言”，应优先禁言下一个将获得发言权的对手（即循环队列中当前 senator 后方最近的对手），而非列表开头的第一个对手。这天然具有循环性，普通线性列表难以高效建模。

✅ 正确解法思路：分组 + 循环链表 + 延迟淘汰

• 分组压缩：利用正则 r"R+|D+" 将连续相同阵营合并为一个节点（如 "DRRD" → R(1)→R(2)→D(1)？不对，应为 D(1)→RR(2)→D(1)；实际 "DRRD" 分组为 "D","RR","D" → D(1)→R(2)→D(1)）；
• 循环链表

  

  ：首尾相接，支持 O(1) 删除与遍历；
• 状态管理：记录当前节点中已行使投票权的议员数 i，结合对方节点剩余人数，计算本次能禁言多少人，避免重复遍历。

以下是优化后的完整实现（含详细注释）：

import re

class Solution:
    class Node:
        def __init__(self, party: str, count: int):
            self.party = party
            self.count = count
            self.next = None

    def predictPartyVictory(self, senate: str) -> str:
        # Step 1: 构建分组循环链表
        # 例如 "DRRD" → ["D", "RR", "D"] → D(1) → R(2) → D(1) → back to D(1)
        sentinel = tail = Solution.Node("", 0)
        for group in re.findall(r"R+|D+", senate):
            tail.next = Solution.Node(group[0], len(group))
            tail = tail.next
        head = sentinel.next  # 跳过哨兵
        tail.next = head      # 成环

        # Step 2: 模拟投票过程
        # curr: 当前处理节点；i: curr 中已投票的议员数
        curr = head
        i = 0
        while curr.next != curr:  # 至少两个不同阵营节点
            nxt = curr.next
            if nxt.party == curr.party:
                # 同阵营：合并节点
                curr.count += nxt.count
                curr.next = nxt.next
            else:
                # 异阵营：curr 中剩余可投票人数 = curr.count - i
                remaining_votes = curr.count - i
                # 最多禁言 min(己方可投数, 对方可存数)
                banned = min(remaining_votes, nxt.count)
                nxt.count -= banned
                i += banned  # 更新已投票数
                if nxt.count == 0:
                    # 对方节点清空，移除
                    curr.next = nxt.next
                if i == curr.count:
                    # 当前节点全员投票完毕，切换到下一节点
                    i = 0
                    curr = curr.next

        # 唯一剩余节点即胜者
        return "Radiant" if curr.party == "R" else "Dire"

? 关键注意事项：

• ❌ 避免在 for/while 遍历列表时调用 list.remove() 或 del —— 改用索引倒序遍历或构建新列表；
• ✅ 分组压缩将时间复杂度从 O(n²) 降至接近 O(n)，尤其对长连续序列（如 "R"*1000 + "D"）效果显著；
• ⚠️ 循环链表需严格维护 next 指针，删除节点时务必更新前驱的 next，防止内存泄漏或无限循环；
• ? 该解法本质是模拟“带计数的循环队列”，i 变量巧妙复用了当前节点的“已消耗投票额度”，无需额外队列存储待处理议员。

此方案通过数据结构升级规避了原始逻辑缺陷，既保证正确性，又具备工业级可扩展性。