周赛笔记257

一、统计特殊四元组

给你一个 下标从 0 开始 的整数数组 nums ，返回满足下述条件的 不同 四元组 (a, b, c, d) 的 数目 ：

• nums[a] + nums[b] + nums[c] == nums[d] ，且
• a < b < c < d

class Solution:
    def countQuadruplets(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        
        for a in range(n-3):
            for b in range(a+1, n-2):
                for c in range(b+1, n-1):
                    for d in range(c+1, n):
                        if nums[a]+nums[b]+nums[c] == nums[d]:
                            res += 1
        
        return res

二、游戏中弱角色的数量⭐

返回攻击防御都低于某个角色的角色数目。

class Solution:
    def numberOfWeakCharacters(self, p: List[List[int]]) -> int:
        p.sort(key = lambda x:[x[0],-x[1]])
        print(p)
        stack = []
        res = 0
        
        for a, d in p:
            while stack and stack[-1][0]<a and stack[-1][1]<d:   #总是相同攻击力下的最高防御加入栈，666
                stack.pop()
                res += 1
            stack.append((a,d))
            
        return res

在那双指针没做出来。。。

三、访问完所有房间的第一天⭐

奇数时根据arr访问，偶数时访问下一个房间；

arr[i] < i；取余

class Solution:
    def firstDayBeenInAllRooms(self, arr: List[int]) -> int:
        dp = [0]*len(arr)
        dp[0] = 1
    
        for i,num in enumerate(arr[:-1]):
            if i==num:  # num == i
                dp[i+1] = dp[i] + 1 + 1    # 下一步 = pre + 当前一步 + 前进一步
            else:       # num < i
                dp[i+1] = 2*dp[i] - dp[num] + 2 
                
        #print(dp)
        mod = 10**9+7
        
        return (dp[-1]-1)%mod

状态转移，一定要画图，取余wa了一次。。。

四、数组的最大公因数排序⭐

能否交换某些数（gcd(i,j) > 1）使数组非递减。

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        
        f = {}
        def find(x):
            f.setdefault(x, x)
            while x != f[x]:
                f[x] = f[f[x]]
                x = f[x]
            return x
        def union(x,y):
            f[find(x)] = find(y)
            
        d = set(nums)
        mx = max(nums)
        for x in range(2, mx+1):
            for y in range(2*x, mx+1, x):
                if y in d:  
                    union(x, y)
        
        target = sorted(nums)
        for u,v in zip(nums,target):
            if u==v: continue
            if find(u) != find(v):
                return False
        return True

这也能并查集，秀啊。

主要思路：枚举因数进行联通，最后与目标数组比较，不同时判断两数是否联通，当所有不同位置都有>1个联通时，一定可以全部有序