[LeetCode周赛复盘] 第 312 场周赛20220925

一、本周周赛总结

• T4 wa2次TLE3次，难受。
• 并查集要好好练！
  

二、 [Easy] 6188. 按身高排序

链接: 6188. 按身高排序

1. 题目描述

2. 思路分析

定级Easy。
按题意排序即可。

3. 代码实现

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        return [a for a,b in sorted(zip(names,heights),key=lambda x:-x[1])]

三、[Medium] 6189. 按位与最大的最长子数组

链接: 6189. 按位与最大的最长子数组

1. 题目描述

2. 思路分析

定级Medium。

• 两个数与的话，一定不能使任意数变大
• 两个数相同使数不变。
• 因此数组最大与结果k一定是最大那个数
• 因此求出k，然后找连续的k的最长区间即可。

3. 代码实现

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        n  = len(nums)
        ans = 1
        mx = max(nums)
        
        f = [0]*n
        if nums[0] == mx:
            f[0] = 1
        for i in range(1,n):
            if nums[i] == mx:
                f[i] = f[i-1]+1
        return max(f)
        

四、[Medium] 6190. 找到所有好下标

链接: 6190. 找到所有好下标

1. 题目描述

2. 思路分析

定级Medium。

• dp
• 用f和g记录每个位置i前边连续非增、非降的区间大小。
• 然就检查题意区间[k,n-k)中所有下标两边的大小是否>=k即可。

3. 代码实现

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        f = [1]*n
        g = [1]*n
        for i in range(1,n):
            if nums[i]<=nums[i-1]:
                f[i]= f[i-1]+1
            if nums[i] >= nums[i-1]:
                g[i] = g[i-1]+1
        ans = []
        for i in range(k,n-k):
            if f[i-1] >= k and g[i+k]>=k:
                ans.append(i)
        return ans

五、[Hard] 6191. 好路径的数目

链接: 6191. 好路径的数目

1. 题目描述

2. 思路分析

定级Hard。

• 并查集。
• 先建图g。
• 然后把点离线，从小到大排序。
• 然后从小到大访问点，建立并查集，注意建立并查集的时候，扫描这个点连接的边：
  • 只能连接不大于当前点u的邻居v。
  • 只能连接已访问过（已经在并查集里）的邻居v 。
• 然后查询当前点所在集合中，相同值的数量，这里边一定都小于等于当前值，则有多少个点就有多少路径。
• 当前集合相同值一定存在一条路径（因为是连通的）。
• 由于是从小到大建树，因此路径中、集合中一定不存在比它大的值。
• 注意，自己单点也算一条长度1的路径。

3. 代码实现

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        p = vals[:]
        n = len(vals)
        f = [Counter([p[i]]) for i in range(n)]
        # print(f)
        fathers = list(range(n))
        def find_father(x):
            if fathers[x] != x:
                fathers[x] = find_father(fathers[x])
            return fathers[x]          
        def union(x,y,z):
            x = find_father(x)
            y = find_father(y)
            if x==y:
                return
            fathers[x] = y      
            f[y][z]+=f[x][z]
        
        g = [[] for _ in range(n)]
        for u,v in edges:
            g[u].append(v)
            g[v].append(u)
            
        vals = sorted([(v,k) for k,v in enumerate(vals)])
        vis = set()
        ans = 0
        for i in range(n):
            v,k = vals[i]
            for x in g[k]:
                if p[x] <= v and x in vis:                    
                    union(k,x,v)
            x = find_father(k)
            ans += f[x][v]
            vis.add(k)
            
        # ans += n
        return ans                                      

六、参考链接

• [python刷题模板] 并查集