526互联

第 365 场周赛 (依赖树， 环形滑动窗口，内向基环树)

发布时间 2023-11-02 16:22:19作者: 深渊之巅

本题可以发现一些枚举的技巧，在枚举多个值的时候，自己有时候脑袋晕晕的，会把变量的更新顺序搞混，此时，可以用依赖树来解决。

如同本题:

class Solution:
    def maximumTripletValue(self, nums: List[int]) -> int:
        res = pre_max = pre_dif = 0

        for x in nums:
            res = max(res, pre_dif * x)
            pre_dif = max(pre_dif, pre_max - x)
            pre_max = max(pre_max, x)
      　　　　 '''
　　　　　　　　　　res -> pre_dif -> pre_max 按照拓扑序来更新变量就不会出问题
　　　　　　　　'''  
        return res

 

 

 我们可以将一个数组无限的拼起来，找到元素和为target的最小子数组，可以预想在 nums + nums + nums + ... 这样的数组中做滑动窗口

1 2 3 | 1 2 3  | 1 2 3... 

可以发现我们在滑动窗口时，窗口内的元素由多个nums和一个前缀和一个后缀组成。

窗口内的nums个数为: target // sum(nums)

所以本题在分析到这里后，只要考虑前一个nums的前缀和后一个nums的后缀（这个后缀可能是跨过了nums），其实就是在 nums + nums这个大数组中，任意地方插入我们 target//sum(nums)个nums就是答案。

class Solution:
    def minSizeSubarray(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        n = len(nums)
        ans = inf
        left = 0
        s = 0

        for right in range(n * 2):
            s += nums[right % n]
            while s > target % total:
                s -= nums[left % n]
                left += 1
            if s == target % total:
                ans = min(ans, right - left + 1)

        if ans == inf:
            return -1
        return ans + target // total * n

 

 

 

 这个题目给的图有个特点，出度都是1，且有n个点n条边，是一个内向基环树。

处理基环树问题时，首先是要找环，可以使用拓扑排序来找环。

有向图中可以建立反向边，从入度为0的点开始进行拓扑排序，最后那几个点度数不会为0，不会被加入队列；无向图中度数为2的那些点就是基环上的点。

本题我们先建立反向边找到基环，然后从基环上的点进行遍历。

基环上的点可达的点数就是环的大小。基环外的子树可达的点就是其到基环点的距离+基环大小。这个距离就是其到基环的深度。

class Solution:

    '''
        每个点都只有一条出边, 并且有n个点，n条边，是内向基环图
    '''

    def countVisitedNodes(self, g: List[int]) -> List[int]:
        n = len(g)
        rg = [[] for _ in range(n)]
        deg = [0] * n

        for x, y in enumerate(g):
            rg[y].append(x)
            deg[y] += 1

        q = deque(i for i, d in enumerate(deg) if d == 0)
        while q:
            x = q.popleft()
            y = g[x]
            deg[y] -= 1
            if deg[y] == 0:
                q.append(y)

        ans = [0] * n

        def rdfs(x: int, depth: int) -> None:
            ans[x] = depth
            for y in rg[x]:
                if deg[y] == 0:   # 是树枝边
                    rdfs(y, depth + 1)
        
        for i, d in enumerate(deg):
            if d <= 0:
                continue
            ring = []
            x = i
            while True:
                deg[x] = -1
                ring.append(x)
                x = g[x]
                if x == i:
                    break
                
            for x in ring:
                rdfs(x, len(ring))

        
        return ans