526互联

[Leetcode Weekly Contest]364

发布时间 2023-09-26 22:13:46作者: Jamest

链接：LeetCode

[Leetcode]2864. 最大二进制奇数

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。

把一个 1 放末尾，其余全部放在开头。

class Solution:
    def maximumOddBinaryNumber(self, s: str) -> str:
        length = len(s)
        ones = s.count("1")
        res = (ones-1) * "1" + (length-ones) * "0" + "1"
        return res;

[Leetcode]2865. 美丽塔 I

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：

  • 1 <= heights[i] <= maxHeights[i]
  • heights 是一个 山状 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状 数组：

  • 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
  • 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

数据量只有 \(1000\)，我们可以枚举以每个点作为山峰（数组最大值）的方案，从山顶依次向两侧递减，使得当前位置不高于前一个位置，整体的时间复杂度是 \(O(n^2)\)

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        res = 0
        n = len(maxHeights)
        for i in range(0, len(maxHeights)):
            if(n * maxHeights[i] <= res): continue
            result = maxHeights[i]
            last = maxHeights[i]
            for j in reversed(range(0, i)):
                result += min(maxHeights[j], last)
                last = min(maxHeights[j], last)

            last = maxHeights[i]
            for j in range(i+1, len(maxHeights)):
                result += min(maxHeights[j], last)
                last = min(maxHeights[j], last)
            res = max(res, result)
        return res

[Leetcode]2866. 美丽塔 II

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：

  • 1 <= heights[i] <= maxHeights[i]
  • heights 是一个 山状 数组。

如果存在下标 i 满足以下条件，那么我们称数组 heights 是一个 山状 数组：

  • 对于所有 0 < j <= i ，都有 heights[j - 1] <= heights[j]
  • 对于所有 i <= k < n - 1 ，都有 heights[k + 1] <= heights[k]

请你返回满足 美丽塔 要求的方案中，高度和的最大值 。

前后缀分解+单调栈.最佳方案就是 pre[i]+suf[i]−maxHeight[i]的最大值。 算前缀最大值时，枚举到i，找到左边离i最近的j，使得a[j]<=a[i]，用j的最大值更新i，对于中间的部分，这些数x比a[i]大，那么就将x变成a[i]，加到pre[i]中，后缀同理

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        left = self.getSumOfHeights(maxHeights)
        right = self.getSumOfHeights(maxHeights[::-1])[::-1]
        n = len(maxHeights)
        res = 0
        for i in range(n):
            res = max(res, left[i] + right[i] - maxHeights[i])
        return res


    def getSumOfHeights(self, maxHeights):
        res = []
        stack = []
        n = len(maxHeights)
        for i in range(n):
            while stack and maxHeights[stack[-1]] > maxHeights[i]:
                stack.pop()
            if not stack:
                res.append((i+1) * maxHeights[i])
            else:
                res.append((i-stack[-1]) * maxHeights[i] + res[stack[-1]])
            stack.append(i)
        return res

[Leetcode]2867. 统计树中的合法路径数目

给你一棵 n 个节点的无向树，节点编号为 1 到 n 。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示节点 ui 和 vi 在树中有一条边。
请你返回树中的 合法路径数目 。
如果在节点 a 到节点 b 之间 恰好有一个 节点的编号是质数，那么我们称路径 (a, b) 是 合法的 。
注意：
路径 (a, b) 指的是一条从节点 a 开始到节点 b 结束的一个节点序列，序列中的节点 互不相同 ，且相邻节点之间在树上有一条边。
路径 (a, b) 和路径 (b, a) 视为 同一条 路径，且只计入答案 一次 。

import collections
class Solution:
    def countPaths(self, n: int, edges: List[List[int]]) -> int:
        primes = self.get_primes(n)
        graph = collections.defaultdict(list)
        cache = collections.defaultdict(int)
        res = 0
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        for i in range(1,n+1):
            if i not in primes: continue
            result = 0
            for nxt in graph[i]:
                if nxt in primes:
                    cache[nxt] = 0
                else:
                    if cache[nxt] == 0:
                        max_count, subSet = self.bfs(graph, nxt, primes)
                        for s in subSet:
                            cache[s] = max_count
                res += result * cache[nxt]
                result += cache[nxt]
            res += result
        return res

    def bfs(self, graph, node, primes):
        visited = set()
        queue = collections.deque([node])
        res = 0
        while queue:
            res += len(queue)
            for i in range(len(queue)):
                cur = queue.popleft()
                visited.add(cur)
                for nxt in graph[cur]:
                    if nxt in visited or nxt in primes:
                        continue
                    else: queue.append(nxt)
        return res, visited

    def get_primes(self, n):
        res = set()
        is_primes = [True for _ in range(n+1)]
        is_primes[0] = is_primes[1] = False
        for i in range(2, n+1):
            if is_primes[i]: res.add(i)
            for val in range(i*i, n+1, i):
                is_primes[val] = False
        return res

参考：LeetCode