Own Solution
class Solution:
def predictPartyVictory(self, senate: str) -> str:
senate = list(senate)
pointer = 1
while pointer < len(senate):
if senate[pointer] != senate[0]:
del senate[pointer]
if pointer >1:
pointer -= 1
senate.append(senate.pop(0))
else:
pointer += 1
return "Dire" if senate[0] == "D" else "Radiant"
One strategy that would pass the judge (although not the most efficient) to think about the problem is for the first character in the string to move to the back and eliminate the first "opposing" character in the string. So in the case of "DDRRR":
DDRRR - the first D moves to the back and takes out the first R
DRRD - the first D moves to the back and takes out the first R
RDD - the first R moves to the back and takes out the first D
DR - the first (and only) D moves to the back and takes out the first (and only) R
D - D wins the vote.
Better Solution:
你可以使用队列来模拟议员的投票过程,这样就不需要手动删除元素和维护指针了。以下是使用队列的改进版本:
from collections import deque
class Solution:
def predictPartyVictory(self, senate: str) -> str:
radiant = deque()
dire = deque()
# 将议员按照阵营放入队列
for i, s in enumerate(senate):
if s == 'R':
radiant.append(i)
else:
dire.append(i)
while radiant and dire:
radiant_index = radiant.popleft()
dire_index = dire.popleft()
# 如果 Radiant 先发言,则 Dire 被禁言,将 Dire 重新放入队列
if radiant_index < dire_index:
radiant.append(radiant_index + len(senate))
# 如果 Dire 先发言,则 Radiant 被禁言,将 Radiant 重新放入队列
else:
dire.append(dire_index + len(senate))
# 判断最后剩余的队列中哪个阵营还有议员
return "Radiant" if radiant else "Dire"
这段代码使用两个队列来分别存储 Radiant 和 Dire 阵营的议员。然后,模拟投票过程,每次从队列中取出一名 Radiant 和一名 Dire 的议员进行投票。如果 Radiant 先发言,则将 Dire 被禁言的议员重新放入 Dire 队列,否则将 Radiant 被禁言的议员重新放入 Radiant 队列。最终,判断哪个阵营的队列不为空,即可确定胜利的阵营。