[数据结构与算法]9月5号，周赛四题，dfs自定义排序，dp(字节附加题)

今天周赛，起来就已经11点了，只写了三题，放上来分析分析：
第一题没什么好写的，据说暴力也能过：
这里试试dfs的方法
5863. 统计特殊四元组

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n= len(nums)
        res=0
        def dfs(nums,cnt,sum_,start):
            if cnt==3:
                for i in range(start,n):
                    if sum_ == nums[i]:
                        nonlocal res
                        res+=1
                return 
            for i in range(start,n):
                dfs(nums,cnt+1,sum_+nums[i],i+1)
            return
        dfs(nums,0,0,0)
        return res

其实这个和暴力的时间复杂度应该差不多，或者这就是一种暴力方法，但是实际运行的时候比暴力遍历快很多。可能是重复计算少了点。

第二题挺好的，非常有意思，是一种自定义排序问题，写的时候花了不少的时间，现在来总结一下。
看到这种多条件多对象的比较题目，第一时间就应该想到自定义排序的，记住了。
5864. 游戏中弱角色的数量

class Solution:
    def numberOfWeakCharacters(self, properties: List[List[int]]) -> int:
        newarr=sorted(properties,key=lambda x:(-x[0],x[1]))
        max_def=-1
        res=0
        for attack,defence in newarr:
            if defence<max_def:
                res+=1
            else:
                max_def = defence
        return res

第三题花了挺久的，主要是是超时：
5865. 访问完所有房间的第一天

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        mod= 10**9+1
        n = len(nextVisit)
        vistied=[0]*n
        vistNum = defaultdict(int)
        cnt,rnum=0,0
        while cnt<n or not all(vistied):
            vistNum[rnum]+=1
            if (vistNum[rnum])%2:
                vistied[rnum]=1
                rnum = nextVisit[rnum]
            else:
                rnum = (rnum+1)%n
            cnt= (cnt+1)%mod
        return (cnt-1)%mod

这道题目他们有人说是2018年字节的校招附加题目。应该是用dp来做。
https://blog.csdn.net/ansizhong9191/article/details/88357399

根据题目对nextVisit[]数组的限制，我们可以知道：

第一次访问 i号房间 的前一天一定是在 i-1号房间，同时此时一定访问了偶数次i-1号房间。
这是因为根据访问房间的规则，假如按照规则1.访问，我们只能往左（房间号小的方向）跳转，只有按照2.规则访问才能往右（房间号大的方向）跳转。
因此第一次到达i号房间，只能先 第二次到达(i-1)号房间 再按照规则2.才能访问到第i号房间。
同时，第一次访问i号房间时，[0,1,…,i-1]号房间都被访问了偶数次。因为假如第x(x<i)号房间被访问了奇数次，那么最后一次到达x号房间后，只能往左（房间号小的方向）跳转，且小于x的房间的nextVisit[]都小于x。因此第一次访问i号房间时[0,1,…,i-1]号房间都被访问了偶数次。

所以dp[i]为第一次到达房间i所用的天数

class Solution:
    def firstDayBeenInAllRooms(self, nextVisit: List[int]) -> int:
        mod = 10**9+7
        n = len(nextVisit)
        dp = [0]*n
        for i in range(1,n):
            dp[i] = (2*dp[i-1]+2-dp[nextVisit[i-1]])%mod
        return dp[n-1]