For 循环未到达特定测试用例的末尾，LeetCode 问题

Question

我的代码不适用于这个leetcode问题Dota 2参议院，具体来说，它不适用于这个测试用例：“DRRD”，这是我的调试打印行为此输入提供的标准输出：

['D', 'R', 'R', 'D']
R
['D', 'R', 'D']
final for this cycle ['R', 'D']
R
['R', 'D']
final for this cycle ['R']
last dog r

输出 “容光焕发” 预期的 “可怕”

这是我的代码：

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        '''We have the list of the string, have a loop that  get the first element 
        and if it's R it removes the next D and vice versa, if there isn't try/ except a value error to win.'''
        senateList= list(senate)
        
        def votingRound(senators: list):
            
            if len(senators) == 1:
                if senators[0] == "R":
                    print(f'last dog r')
                    return "Radiant"
                else:
                    print(f'last dog d')
                    return "Dire"

            for senator in senators:
                print(senator)
                print(senators)
                if senator == "R":
                    try:
                        senators.remove("D")
                    except:
                        print(f'only r')
                        return "Radiant"
                else:
                    try:
                        senators.remove("R")
                    except:
                        print(f'only d')
                        return "Dire"
            
            print(f'final for this cycle {senators}')
            return votingRound(senators)


        return votingRound(senateList)

我不确定为什么循环不执行初始参议员列表中的最后一个 D，而对于其他测试用例，代码可以完美运行。

自动评分器正在调用该类，其中它使用该测试用例的字符串调用predictPartyVictory()。

Answer 1

错误的直接原因是您的代码迭代了一个列表，同时也从该列表中删除了项目。例如，如果迭代位于索引 3 处，并且您删除了索引 0 处的项目，则下一次迭代仍将位于索引 4 处，但这不是下一个项目...下一个项目现在位于索引 3 处（在在索引 0 处删除）。所以你的循环会跳过元素。

另一个问题涉及您删除第一位从列表左侧开始的参议员（来自反对党）的策略。这不是一个最佳策略。您应该罢免将是下一轮中第一个“轮到”的反对派参议员。那可能不是您删除的那个。它可能是当前索引之后索引的参议员。循环链表

有很多方法可以解决这个问题。我们还应该考虑到，从标准列表中删除并不是非常有效：所有后续条目都需要向后移动一个位置。例如，您可以使用循环链表。然后，您可以删除具有恒定时间复杂度的节点，前提是您拥有对目标节点之前的节点的引用。您还可以通过将同一政党的相邻参议员聚集到一个这样的节点中来获得一些时间，并保留一个“计数”。例如，如果输入是“RDDDRRD”，您可以首先将其转换为这个循环链表：

┌───────────┐ ┌───────────┐ ┌───────────┐ ┌───────────┐ │ party: R │ │ party: D │ │ party: R │ │ party: D │ │ num: 1 │ │ num: 3 │ │ val: 2 │ │ num: 1 │ ┌─► │ next: ──────► │ next: ──────► │ next: ──────► │ next: ─┐ │ │ └───────────┘ └───────────┘ └───────────┘ └────────│──┘ └────────────────────────────────────────────────────────────┘ 使用此数据结构，您可以执行以下操作：

如果当前节点和下一个节点有同一方：合并它们（将它们的计数相加）

否则，如果下一个节点的计数不超过当前节点可以轮流的参议员数量，则删除该下一个节点，并记下当前节点中有多少参议员轮流实现这一目标。

否则，减少下一个节点的计数并将其设为当前节点。

上面的算法草图产生了以下代码：

class Solution(object): class Node: def init(self, party, num_senators): self.party = party self.num_senators = num_senators self.next = None def predictPartyVictory(self, senate): # Create a circular linked list sentinel = tail = Solution.Node("", 0) for span in re.findall(r"R+|D+", senate): # Group same-party neighbors tail.next = Solution.Node(span[0], len(span)) tail = tail.next curr = sentinel.next # Remove sentinel tail.next = curr # Make circular i = 0 # Number of senators in the current node that took a turn while curr.next is not curr: # More than one party represented nxt = curr.next if nxt.party == curr.party: # Merge curr.num_senators += nxt.num_senators curr.next = nxt.next else: banned = min(curr.num_senators - i, nxt.num_senators) nxt.num_senators -= banned i += banned if not nxt.num_senators: # Next group is empty # Remove emptied node curr.next = nxt.next if i == curr.num_senators: # All in current node did their turn i = 0 curr = curr.next # Continue with next group of senators return "Radiant" if curr.party == "R" else "Dire"

For 循环未到达特定测试用例的末尾，LeetCode 问题

问题描述投票：0回答：1

1个回答

最新问题

For 循环未到达特定测试用例的末尾，LeetCode 问题

问题描述 投票：0回答：1

1个回答

最新问题

问题描述投票：0回答：1