leetcode weekly contes 364
最近周赛题目的质量越来越高了，非常不错的周赛题目，适合思维性的思考题目，不涉及到非常复杂的算法，基本上全是思维题目。
8048. 最大二进制奇数
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
示例 1：
输入：s = "010" |
示例 2：
输入：s = "0101" |
提示：
1 <= s.length <= 100s仅由'0'和'1'组成s中至少包含一个'1'
地址
https://leetcode.cn/contest/weekly-contest-364/problems/maximum-odd-binary-number/
题意
模拟
思路
- 比较简单的题目，若使得通过字符交换构成最大的奇数，需要满足如下条件：
- 最低位一定为 $1$；
- 若使得构成的数字最大，则一定满足最低位以外，高位全部为 $1$,低位全部为 $0$;
- 根据上述分析可以构造最大的奇数即可；
- 复杂度分析：
- 时间复杂度：$O(n)$，其中 $n$ 表示字符串的长度,。
- 空间复杂度：$O(1)$。
代码
class Solution { |
100049. 美丽塔 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]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
示例 1：
输入：maxHeights = [5,3,4,1,1] |
示例 2：
输入：maxHeights = [6,5,3,9,2,7] |
示例 3：
输入：maxHeights = [3,2,5,5,2,3] |
提示：
1 <= n == maxHeights <= 1031 <= maxHeights[i] <= 109
地址
https://leetcode.cn/contest/weekly-contest-364/problems/beautiful-towers-i/
题意
枚举
思路
- 首先 $O(n^2)$ 的解法非常简单，我们直接枚举以第 $i$ 个数位最大值即可，此时枚举方案如下，假设第 $i$ 个数为美丽塔 的最大元素，按照贪心法则，则第 $i$ 个数应该尽可能的大，此时第 $i$ 个数的取值即为 $maxHeights[i]$，然后依次向两遍扩展，使得每个位置上的元素尽可能的大，解法比较简单，设上一个元素的值为 $pre$,则当前元素最大值只能取到 $\max(pre, maxHeights[i])$，我们依次对每个位置上可以取的最大元素求和即可。
- 复杂度分析：
- 时间复杂度：$O(n^2)$，其中 $n$ 为数组的长度。
- 空间复杂度：$O(1)$。
代码
class Solution { |
100048. 美丽塔 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]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
示例 1：
输入：maxHeights = [5,3,4,1,1] |
示例 2：
输入：maxHeights = [6,5,3,9,2,7] |
示例 3：
输入：maxHeights = [3,2,5,5,2,3] |
提示：
1 <= n == maxHeights <= 1051 <= maxHeights[i] <= 109
地址
https://leetcode.cn/contest/weekly-contest-364/problems/beautiful-towers-ii/
题意
单调栈 + 动态规划
思路
第三题与第二题的题目一样，只是数量级有所变换，给定的数量级为 $10^5$，这说明只能用 $O(n)$ 的解法了，这就需要仔细分析了。假设我们设 $dp[i]$ 表示前 $i$ 个元素变为非递减且以 $maxHeights[i]$ 为结尾的前缀和最大值，则此时我们可以观察一下如下 $dp[i]$ 是否与 $dp[j]$ 存在递推关系，其中 $j < i$, 通过仔细观察可以发现如下：
假设 $[j + 1, i-1]$ 之间的元素都满足 $maxHeights[{j+1} \cdots {i-1}] \ge maxHeights[i]，maxHeights[j] \le maxHeights[i]$ ，即 $[j+1,i]$ 之间的最小元素为 $maxHeights[i]$, 由于此时区间 $[0,i]$ 的最大值为 $maxHeights[i]$, 则此时 $[j+1,i]$ 之间的元素的最大值只能取到 $maxHeights[i]$, 则此时存在递推关系为:
$$dp[i] = dp[j] + (i- j) * maxHeights[i]$$
根据以上分析可以发现，我们只需要找到 $maxHeights[i]$ 左边第一个小于等于 $maxHeights[i]$ 的元素，即可使用上述的递推关系，此时我们自然而然想到用单调栈即可解决上述的问题，当然了山峰问题本身就是可以利用单调栈解决该问题，因为单调的情况下才能满足当前的值满足连续递增或者递减。
复杂度分析：
- 时间复杂度：$O(n)$，其中$n$ 表示数组的长度；
- 空间复杂度：$O(n)$，其中$n$ 表示数组的长度；
代码
class Solution { |
100047. 统计树中的合法路径数目
给你一棵 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)视为 同一条 路径，且只计入答案 一次 。
示例 1：
输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]] |
示例 2：
输入：n = 6, edges = [[1,2],[1,3],[2,4],[3,5],[3,6]] |
提示：
1 <= n <= 105edges.length == n - 1edges[i].length == 21 <= ui, vi <= n- 输入保证
edges形成一棵合法的树。
地址
https://leetcode.cn/contest/weekly-contest-364/problems/count-valid-paths-in-a-tree/
题意
树形dp
思路
- 当然拿到题目就可以确定要使用树形
dp，典型的树形 $dp$ 问题，但是细节不好处理，我们需要仔细计算。首先我们分析一个问题, 假设树以节点 $a$ 为根节点，则当前计算经过节点 $a$ 且只有一个质数的路径数目如何计算呢？- 此时我们假设 $a$ 的孩子节点分别为 $p_0,p_1,p_2, \cdots p_{m-1}$, 则以 $p_0，p_1,p_2,\cdots p_{m-1}$ 为终点且不含质数的路径数目分别为 $c_0,c_1, c_2, \cdots, c_{m-1}$, 以 $p_0，p_1,p_2,\cdots, c_{m-1}$ 为终点且刚好含有一个质数的路径数目分别为 $pc_0,pc_1, pc_2, \cdots,pc_{m-1}$, 在这些信息已经知道的情况下如何计算经过 $a$ 的且只含有一个质数的路径数目，其中 $a$ 的孩子节点共有 $m$ 个。
- 假设当前 $a$ 是非质数，分为两种情况：
- $a$ 为路径的中间节点，即 $a$ 左侧也有路径，$a$ 右侧也有路径，即此时的路径一定是 $x \rightarrow a \rightarrow y$,则此时 $a$ 左侧的路径中 $x \rightarrow a$ 包含有一个质数，$a$ 的右侧的路径$a \rightarrow y$一定不包含质数，或者 $a$ 右侧路径 $a \rightarrow y$ 中包含有一个质数，$a$ 的左侧路径$x \rightarrow a$一定不包含质数，在上述两种情况下一定可以构成只包含一个质数的路径，这时路径的总数目即为 $\sum_{i=0}^{m-1}c_i \times \sum_{i=0}^{m-1}pc_i - \sum_{i=0}^{m-1}c_ipc_i$;
- $a$ 为路径的终点，即 $a$ 左侧存在路径，$a$ 右侧不存在，即此时的路径一定是 $x \rightarrow a $,则此时 $a$ 左侧的路径中 $x \rightarrow a$ 包含有一个质数，此时路径的总数为 $\sum_{i=0}^{m-1}pc_i$;
- 综上可知此时以 $a$ 为根节点的子树中包含节点 $a$ 且只含有一个质数的路径的总数目为: ${\sum_{i=0}^{m-1}c_i \times \sum_{i=0}^{m-1}pc_i - \sum_{i=0}^{m-1}c_ipc_i}{2} + \sum_{i=0}^{m-1}pc_i$;
- 假设当前 $a$ 是质数,分为两种情况：
- $a$ 为路径的中间节点，即 $a$ 左侧也有路径，$a$ 右侧也有路径，即此时的路径一定是 $x \rightarrow a \rightarrow y$,则此时 $a$ 左侧的路径中 $x \rightarrow a$ 一定不能包含质数，$a$ 的右侧的路径$a \rightarrow y$ 也一定不包含质数，只能在上述一种情况下可以构成只包含一个质数的路径，这时路径的总数目即为 $\dfrac{(\sum_{i=0}^{m-1}c_i)^2- \sum_{i=0}^{m-1}c_i^2}{2}$;
- $a$ 为路径的终点，即 $a$ 左侧存在路径，$a$ 右侧不存在，即此时的路径一定是 $x \rightarrow a $,则此时 $a$ 左侧的路径中 $x \rightarrow a$ 一定不能包含质数，此时路径的总数为 $\sum_{i=0}^{m-1}c_i$;
- 综上可知此时以 $a$ 为根节点的子树中包含节点 $a$ 且只含有一个质数的路径的总数目为: $\dfrac{(\sum_{i=0}^{m-1}c_i)^2- \sum_{i=0}^{m-1}c_i^2}{2} + \sum_{i=0}^{m-1}c_i$;
- 当然上述的分析还是挺难写的，细节特别容易出错，我们采用树形 $dp$ ，每次返回以当前节点 $p$ 为根中的子树中存在以 $p$ 为终点且路径包含质数的路径数目 $sum_1$ 和不包含质数路径的数目 $sum_0$，然后利用上述的递推关系进行动态规划即可。
- 假设 $a$ 为非质数，由于 $a$ 本身为非质数，此时以 $a$ 为终点的不包含质数和仅有一个质数的路径数目分别为 $(\sum_{i=0}^{m-1}c_i + 1, \sum_{i=0}^{m-1}pc_i)$；
- 假设 $a$ 为质数，由于$a$ 为质数，凡是经过节点 $a$ 的路径均包含质数，此时以 $a$ 为终点的不包含质数和仅有一个质数的路径数目分别为 $(0, \sum_{i=0}^{m-1}c_{i} + 1)$；
- 复杂度分析：
- 时间复杂度：$O(E + V)$，其中 $V$ 表示树中节点的数目， $E$ 表示树中边的数目。
- 空间复杂度：$O(E + V)$，其中 $V$ 表示树中节点的数目， $E$ 表示树中边的数目。
代码
class Solution { |
欢迎关注和打赏，感谢支持！
- 关注我的博客: http://whistle-wind.com/
- 关注我的知乎：https://www.zhihu.com/people/da-hua-niu
- 关注我的微信公众号: 公务程序猿
扫描二维码，分享此文章