649. Dota2 参议院 [medium]

https://leetcode-cn.com/problems/dota2-senate/

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

禁止一名参议员的权利：
参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。
宣布胜利：
如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

示例 1:

输入: "RD"
输出: "Radiant"
解释:  第一个参议员来自  Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

示例 2:

输入: "RDD"
输出: "Dire"
解释: 
第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利
第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止
第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利
因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利

注意:

给定字符串的长度在 [1, 10,000] 之间.

通过次数3,621 | 提交次数9,386

Second Try

2020-06-26

额外使用外部的计数来替代每一轮对列表进行处理判断唯一，速度快了几十倍，不过还是只能排到中间。anyway,算是还可以了。不过没看出跟dota有什么关系。。。

class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        # 首先禁止在后面的人，然后才禁止已经走过一轮的人
        # 写了一圈其他版本后，发现使用queue队列最有效，终于体会到队列的好处了

        decrease_r = sum([i == "R" for i in senate])  # 每次被屏蔽，人少少一个
        decrease_d = len(senate) - decrease_r

        count_r = 0  # 可以用来屏蔽对方的净胜数
        count_d = 0

        mos = {"R": "Radiant", "D": "Dire"}
        queue = list(senate)
        
        while decrease_r and decrease_d:
            ele = queue.pop(0)
            # print(ele, queue, decrease_r, decrease_d)
            if ele == "R":
                if count_d:
                    count_d -= 1
                    decrease_r -= 1
                    continue
                 # bug 写法，会导致最后mos[queue[0]]出错，因为并没有真正被pop掉
                # decrease_d -= 1 
                count_r += 1
                queue.append(ele)
            elif ele == "D":
                if count_r:
                    count_r -= 1
                    decrease_d -= 1
                    continue
                # decrease_r -= 1  # bug写法
                count_d += 1
                queue.append(ele)
        return mos[queue[0]]

执行用时：216 ms, 在所有 Python 提交中击败了29.41%的用户
内存消耗：12.9 MB, 在所有 Python 提交中击败了100.00%的用户

First Try

2020-06-27

思路很清晰，问题在于每一个元素都需要遍历列表判断一次是否可以结束，导致时间超时非常严重，不过没想到7788ms也能够通过测试。

其实一开始也没想到使用队列来做，用了额外的列表来保存第一轮没有问题的元素。写着写着才发现其实用队列非常方便，这才真正体会到队列在循环类型的问题中的方便之处，两个循环之间的处理一下子就清晰了起来。

对于问题本身，如果想要利用正向循环解决问题，最好就是先把准备处理的内容保存起来，等到遇到的时候再进行处理，这样就不用在循环之间不停前后切换了。

class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        # 首先禁止在后面的人，然后才禁止已经走过一轮的人
        # 写了一圈其他版本后，发现使用queue队列最有效，终于体会到队列的好处了
        count_r = 0
        count_d = 0
        mos = {"R": "Radiant", "D": "Dire"}
        queue = list(senate)
        while (len(set(queue)) != 1):
            ele = queue.pop(0)
            if ele == "R":
                if count_d:
                    count_d -= 1
                    continue 
                count_r += 1
                queue.append(ele)
            elif ele == "D":
                if count_r:
                    count_r -= 1
                    continue
                count_d += 1
                queue.append(ele)
        return mos[queue[0]]

        # while i < len(senate):
        #     if senate[i] == "R":
        #         if cd:
        #             cd -= 1
        #             i += 1
        #             continue
        #         cr += 1
        #     elif senate[i] == "D":
        #         if cr: 
        #             cr -= 1
        #             i += 1
        #             continue
        #         cd += 1
        #     reserve.append(senate[i]) 
        #     print(senate[i], reserve)

        #     i += 1
        #     print("wtf", i)
        #     if i == len(senate):
        #         print('vola', i, reserve)
        #         if len(set(reserve)) == 1:  # reserve 不可能为0
        #             return mos[reserve[0]]
        #         senate = "".join(reserve)
        #         reserve = []
        

执行用时：7788 ms, 在所有 Python 提交中击败了5.88%的用户
内存消耗：13 MB, 在所有 Python 提交中击败了100.00%的用户