leetcode 第 364 场周赛

2864. 最大二进制奇数

核心思想：留一个1在最后其余的1全部放在前面即是最大的。

2865. 美丽塔 I

核心思想：枚举每个值作为峰值，然后从当前值，往前进行遍历不断取最小的，同理往后遍历，也不断取最小的，时间复杂度为O（n**2）。

2866. 美丽塔 II

核心思想：这题与美丽塔 I的区别就在于数据的范围，这题O（n**2）肯定是过不了的，所以需要优化。我们往前遍历往后遍历不就是为了求当前值到前面的以及当前值到后面的满足要求的和吗。求和问题就想到了前后缀，具体的做法就是用一个栈来维护这些数据。比如求当前值到后面的满足要求的值。枚举到当前值是小于栈顶元素的，那么我们肯定需要把栈顶元素拿出来，然后替换成当前值，详细的解释可以看灵神题解有很详细的解释，这里栈的功能就是优化的，帮助我们求出满足要求的前缀和后缀和。

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

核心思想：由于要统计树中所有的合法路径。所以我们可以枚举每个节点作为根节点的合法路径树，然后统计结果，但是由于根节点为非质数很难讨论。所以我们可以只枚举质数节点作为根节点的合法路径数目和，假设x为质数根节点，它有三个子树，分别2，3，4，2表示这个子树能枚举到的所有非质数个数，那么2*3；2*4，3*4为一组，加上2+3+4单独为一组，我们就可以统计出所有的答案。具体就是求某个节点最多能遍历到多少个非质数。

标签：leetcode 第 364 场周赛_igang of rebirth的博客