52. N皇后 II

• 思路
  • example
  • 暴力回溯
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(i):
            nonlocal res  
            if i == n:
                res += 1
                return  
            for j in range(n):
                if column[j] or diagnoal1[i+j] or diagnoal2[i-j+n-1]:
                    continue  
                column[j] = True  
                diagnoal1[i+j] = True  
                diagnoal2[i-j+n-1] = True 
                backtrack(i+1)
                column[j] = False  
                diagnoal1[i+j] = False  
                diagnoal2[i-j+n-1] = False  
            return 
        column = [False] * n
        diagnoal1 = [False] * (2*n-1) # top right, i+j=constant
        diagnoal2 = [False] * (2*n-1) # top left, i-j+n-1=constant
        res = 0
        backtrack(0)
        return res  

class Solution:
    def totalNQueens(self, n: int) -> int:
        def backtrack(i): # i: row-index
            nonlocal res 
            if i == n:
                res += 1
                return 
            for j in range(n): 
                idx1 = i + j 
                idx2 = j - i + n - 1
                if col[j] or diag1[idx1] or diag2[idx2]:
                    continue 
                col[j] = True 
                diag1[idx1] = True 
                diag2[idx2] = True 
                backtrack(i+1) 
                col[j] = False 
                diag1[idx1] = False 
                diag2[idx2] = False 
        res = 0 
        col = [False for _ in range(n)] 
        diag1 = [False for _ in range(2*n-1)] # / idx1 = i + j
        diag2 = [False for _ in range(2*n-1)] # \ idx2 = j - i + n - 1
        backtrack(0) 
        return res 

649. Dota2 参议院

• 思路
  • example
  • 贪心，双deque记录还存在的议员index
• 复杂度. 时间：O(n), 空间: O(n)

消灭的策略是，尽量消灭自己后面的对手，因为前面的对手已经使用过权利了，而后续的对手依然可以使用权利消灭自己的同伴！
RRDDD, ans = R
用deque模拟投票过程 (数字低代表优先行使权利: 把对方表头的弹出（出局）popleft()，同时在自己的表末加上index + n，说明在接下去的轮次该人员的排位)
radiant = [0,1], dire = [2,3,4]
radiant = [1,5], dire = [3,4] (radiant末尾加上5 (index + n)，表明下一次比较时优先权比0-4要低)
radiant = [5,6], dire = [4]
radiant = [6], dire = [9]
radiant = [11], dire = []

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate)
        radiant, dire = collections.deque(), collections.deque()  
        for i in range(n):
            if senate[i] == 'R':
                radiant.append(i) 
            else:
                dire.append(i)  
        while radiant and dire:  
            if radiant[0] < dire[0]:
                dire.popleft() 
                idx = radiant.popleft()
                radiant.append(idx + n)
            else: # radiant[0] > dire[0] 
                radiant.popleft() 
                idx = dire.popleft()  
                dire.append(idx + n)  
        return "Radiant" if radiant else "Dire"

class Solution:
    def predictPartyVictory(self, senate: str) -> str:
        n = len(senate) 
        Radiant, Dire = collections.deque(), collections.deque() 
        for i in range(n):
            ch = senate[i] 
            if ch == 'R':
                Radiant.append(i) 
            else:
                Dire.append(i) 
        while Radiant and Dire:
            if Radiant[0] < Dire[0]:
                Dire.popleft() 
                index = Radiant.popleft() 
                Radiant.append(index+n) 
            else:
                Radiant.popleft() 
                index = Dire.popleft() 
                Dire.append(index+n) 
        return 'Radiant' if Radiant else 'Dire'