Dota2 Senate-K6K4.com

原题： https://leetcode.com/problems/dota2-senate/description/

题意： 有两个阵营R和D，一个阵营的成员可以将另一个阵营的成员“禁言”。假设两阵营的成员都采用最优策略。求最终剩下的具有发言权的阵营。

约定：（1）给定的字符串的长度的范围为[1,10000]。

例子：

Example 1:
Input: "RD"
Output: "Radiant"
Explanation: The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
And the second senator can't exercise any rights any more since his right has been banned. 
And in the round 2, the first senator can just announce the victory since he is the only guy in the senate who can vote.

Example 2:
Input: "RDD"
Output: "Dire"
Explanation: 
The first senator comes from Radiant and he can just ban the next senator's right in the round 1. 
And the second senator can't exercise any rights anymore since his right has been banned. 
And the third senator comes from Dire and he can ban the first senator's right in the round 1. 
And in the round 2, the third senator can just announce the victory since he is the only guy in the senate who can vote.

标签： senator、阵营、senate、round、radiant、面试

猜你感兴趣的圈子：

LeetCode交流圈

SLPH

2017-08-14 16:52:59 1楼#1层

Python：

class Solution(object):
    def predictPartyVictory(self, senate):
        """
        :type senate: str
        :rtype: str
        """
        delta = 0
        while len(set(senate)) > 1:
            nsenate = ''
            for s in senate:
                if s == 'R':
                    if delta >= 0: nsenate += 'R'
                    delta += 1
                else:
                    if delta <= 0: nsenate += 'D'
                    delta -= 1
            senate = nsenate
        return {'D' : 'Dire', 'R' : 'Radiant'}[senate[0]]

SLPH

2017-08-14 16:53:56 2楼#1层

Java：

public class Solution {
    public String predictPartyVictory(String senate) {
        Queue<Integer> q1 = new LinkedList<Integer>(), q2 = new LinkedList<Integer>();
        int n = senate.length();
        for(int i = 0; i<n; i++){
            if(senate.charAt(i) == 'R')q1.add(i);
            else q2.add(i);
        }
        while(!q1.isEmpty() && !q2.isEmpty()){
            int r_index = q1.poll(), d_index = q2.poll();
            if(r_index < d_index)q1.add(r_index + n);
            else q2.add(d_index + n);
        }
        return (q1.size() > q2.size())? "Radiant" : "Dire";
    }
}

取消

回复

推荐圈子

LeetCode交流圈