标签：Contest int 312 self nums List range ans Weekly

Weekly Contest 312

Problem A

Sort the People

思路

水题，按值排序就行

代码

class Solution:
    def sortPeople(self, names: List[str], heights: List[int]) -> List[str]:
        ans = []
        for i in range(len(names)):
            ans.append([heights[i],names[i]])
        ans.sort()
        for i in range(len(names)):
            ans[i] = ans[i][1]
        return ans[::-1]

Problem B

Longest Subarray With Maximum Bitwise AND

思路

除非同值AND 否则一定会越AND越小，思路就是找一下最大的值，然后算一下最长连续的这个值

代码

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

Problem C

Find All Good Indices

思路

开两个数组，一个记录左边有多长非递增，一个记录右边多少非递减，然后筛一下就好了

代码

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        lcnt, rcnt = [1 for _ in range(n)], [1 for _ in range(n)]
        for i in range(n-1):
            if nums[i+1] <= nums[i]:
                lcnt[i+1] = lcnt[i]+1
            if nums[n-1-i] >= nums[n-2-i]:
                rcnt[n-2-i] = rcnt[n-1-i]+1
        return [i for i in range(k, n-k) if lcnt[i-1] >= k and rcnt[i+1] >= k]

Problem D

Number of Good Paths

思路

并查集，先按值分组，然后对同组的点做并查集，最后对能联通的点求$C_n^2$

代码

class Solution:
    def numberOfGoodPaths(self, vals: List[int], edges: List[List[int]]) -> int:
        
        adj_list = defaultdict(list)
        for i, j in edges:
            adj_list[i].append(j)
            adj_list[j].append(i)
        
        nodes = defaultdict(list)
        for i, v in enumerate(vals):
            nodes[v].append(i)
        
        uf = UnionFind(len(vals))
        
        ans = 0
        for v in sorted(nodes.keys()):
        
            # Add nodes with value v
            for i in nodes[v]:
                for j in adj_list[i]:
                    if vals[j] <= vals[i]:
                        uf.union(i, j)
            
            # Count number of nodes with value v in its root
            cnt = defaultdict(int)
            for i in nodes[v]:
                cnt[uf.find(i)] += 1
            
            # For each subtree that contains x nodes with value v,
            # it has x + (x choose 2) = x + x * (x - 1) // 2 good paths.
            for x in cnt.values():
                ans += x + x * (x - 1) // 2
        
        return ans
        
class UnionFind:
    """
    Disjoint-set forest implemented by union-find with
    1. path compression find()
    2. weighted union()
    Both find() and union() have an amortized O(a(n)) time complexity
    """
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, p: int) -> int:
        """find root with path compression"""
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])
        return self.parent[p]

    def union(self, p: int, q: int) -> None:
        """weighted union: join small tree to large tree"""
        root1 = self.find(p)
        root2 = self.find(q)
        if self.size[root1] >= self.size[root2]:
            root1, root2 = root2, root1
        # size of root1 is always smaller
        self.parent[root1] = self.parent[root2]
        self.size[root2] += self.size[root1]

总结

这场出了两题，后两题感觉就是思路没想到，蛮可惜的，看到树有点畏难了

标签：Contest,int,312,self,nums,List,range,ans,Weekly
From： https://www.cnblogs.com/baihualiaoluan/p/16748415.html