当前位置:网站首页>Leetcode: the maximum number of building change requests that can be reached (if you see the amount of data, you should be mindless)

Leetcode: the maximum number of building change requests that can be reached (if you see the amount of data, you should be mindless)

2022-06-12 21:54:00 Review of the white speed Dragon King

 Insert picture description here

 Insert picture description here
Ideas :
Less data
Binary representation of selection or No election , And then use delta Judge whether this method meets the requirements
Be careful all Usage of

src:

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        #  Choose the most st  Into the  =  Out of 
        #  Multiple small closed loops 
        #  Find out how many circles there are , And total points 
        #  Forget it   Look at the answer 
        #  Ah, this , The answer is binary violence enumeration 
        ans = 0
        for mask in range(1 << len(requests)):
            cnt = mask.bit_count()
            #  Not bigger 
            if cnt <= ans:
                continue
            
            #  It is used to record whether all are 0
            delta = [0] * n
            #  See which one you chose 
            for j in range(len(requests)):
                #  This is not equal to 1, It's greater than 0!!!
                if mask & (1 << j):
                    delta[requests[j][0]] -= 1
                    delta[requests[j][1]] += 1
            #  if delta All for 0, Description balance 
            if all(x == 0 for x in delta):
                ans = cnt
        
        return ans

summary :
Judge whether someone has chosen or not ==1, It is >0, Because it's someone on the , It should be 1000…
If you encounter small data, you can bf
Then by proper pruning (cnt <= ans break)

原网站

版权声明
本文为[Review of the white speed Dragon King]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/02/202202281204253491.html