网站建立站点,站长工具网站备案查询,装修公司哪家好兰州的,做网站的宣传语Leetcode 第 364 场周赛题解 Leetcode 第 364 场周赛题解题目1#xff1a;2864. 最大二进制奇数思路代码复杂度分析 题目2#xff1a;美丽塔 I思路代码复杂度分析 题目3#xff1a;美丽塔 II思路代码复杂度分析 题目4#xff1a;统计树中的合法路径数目思路代码复杂度分析 … Leetcode 第 364 场周赛题解 Leetcode 第 364 场周赛题解题目12864. 最大二进制奇数思路代码复杂度分析 题目2美丽塔 I思路代码复杂度分析 题目3美丽塔 II思路代码复杂度分析 题目4统计树中的合法路径数目思路代码复杂度分析 Leetcode 第 364 场周赛题解
题目12864. 最大二进制奇数
思路
贪心。
要得到最大二进制奇数则高位尽可能放 1为了是奇数最后一位必须是 1。
设原字符串的长度为 n统计原字符串中 ‘1’ 的个数记为 count_one。
新字符串 count_one - 1 个 ‘1’ n - count_one 个 ‘0’ ‘1’。
代码
/** lc appleetcode.cn id2864 langcpp** [2864] 最大二进制奇数*/// lc codestart
class Solution
{
public:string maximumOddBinaryNumber(string s){int n s.size(), count_one 0;for (char c : s)if (c 1)count_one;string ans;for (int i 0; i count_one - 1; i)ans 1;for (int i 0; i n - count_one; i)ans 0;ans 1;return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是字符串的长度。
空间复杂度O(1)。
题目2美丽塔 I
思路
枚举峰值的位置向左、向右求高度和更新高度和的最大值。
代码
/** lc appleetcode.cn id2865 langcpp** [2865] 美丽塔 I*/// lc codestart
class Solution
{
public:long long maximumSumOfHeights(vectorint maxHeights){int n maxHeights.size();long long max_sum 0;// 枚举峰值的位置for (int i 0; i n; i){long long cur_sum maxHeights[i];// 向左求和int left_height maxHeights[i];for (int j i - 1; j 0; j--){left_height min(left_height, maxHeights[j]);cur_sum left_height;}// 向右求和int right_height maxHeights[i];for (int j i 1; j n; j){right_height min(right_height, maxHeights[j]);cur_sum right_height;}// 更新答案max_sum max(max_sum, cur_sum);}return max_sum;}
};
// lc codeend复杂度分析
时间复杂度O(n2)其中 n 是数组 maxHeights 的长度。
空间复杂度O(1)。
题目3美丽塔 II
思路
思考优化
以示例 [6,5,3,9,2,7] 为例我们观察以 3 和 9 作为山顶的两个方案
以 3 作为山顶3 3 |3 3| 2 2以 9 作为山顶3 3 |3 9| 2 2
可以发现以 3 作为山顶的左侧与以 9 为山顶的右侧在两个方案之间是可以复用的至此发现解决方法我们可以分别预处理出以每个节点作为山顶的前缀和后缀的和
prev[i] 表示以 maxHeights[i] 作为山顶时左侧段的前缀和suffix[i] 表示以 maxHeights[i] 作为山顶时右侧段的后缀和。
那么最佳方案就是 prev[i]suffix[i]−maxHeight[i] 的最大值。 现在最后的问题是如何以均摊 O(1) 的时间复杂度计算出每个元素前后缀的和
继续以示例 [6,5,3,9,2,7] 为例
以 6 为山顶前缀为 [6]以 5 为山顶需要保证左侧元素不大于 5因此找到 666 并修改为 555前缀为 [5,5]以 3 为山顶需要保证左侧元素不大于 3因此找到两个 555 并修改为 333前缀为 [3,3,3]以 9 为山顶需要保证左侧元素不大于 9不需要修改前缀为 [3,3,3,9]以 2 为山顶需要保证左侧元素不大于 2修改后为 [2,2,2,2,2]以 7 为山顶需要保证左侧元素不大于 7不需要修改前缀为 [2,2,2,2,2,7]
观察以上步骤问题的关键在于修改操作由于数组是递增的因此修改的步骤就是在「寻找小于等于当前元素 x 的上一个元素」再将中间的元素削减为 x。「寻找上一个更小元素」这是单调栈的典型场景。
代码
/** lc appleetcode.cn id2866 langcpp** [2866] 美丽塔 II*/// lc codestart
class Solution
{
public:long long maximumSumOfHeights(vectorint maxHeights){int n maxHeights.size();vectorlong long suffix(n 1, 0);vectorlong long prev(n 1, 0);stackint s;// 单调栈求前缀for (int i 0; i n; i){// 弹出栈顶while (!s.empty() maxHeights[s.top()] maxHeights[i])s.pop();int j s.empty() ? -1 : s.top();prev[i 1] prev[j 1] (long long)(i - j) * maxHeights[i];s.push(i);}// 清空栈while (!s.empty())s.pop();// 单调栈求后缀for (int i n - 1; i 0; i--){// 弹出栈顶while (!s.empty() maxHeights[s.top()] maxHeights[i])s.pop();int j s.empty() ? n : s.top();suffix[i] suffix[j] (long long)(j - i) * maxHeights[i];s.push(i);}// 合并long long max_sum 0;for (int i 0; i n; i)max_sum max(max_sum, prev[i 1] suffix[i] - maxHeights[i]);return max_sum;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 maxHeights 的长度。在一侧的计算中每个元素最多如何和出栈 1 次。
空间复杂度O(n)其中 n 是数组 maxHeights 的长度。
题目4统计树中的合法路径数目
超出能力范围。
思路
经典的树型 DP 模型。维护以下值
fu 表示以节点 u 为起点以 u 的子树中某个节点为终点的路径中所有点编号都是合数的路径有几条。gu 表示以节点 u 为起点以 u 的子树中某个节点为终点的路径中有一个点的编号为质数的路径有几条。
answer f[u] * g[v] f[v] * g[u]。
题解
https://leetcode.cn/problems/count-valid-paths-in-a-tree/solutions/2456568/shu-dp-by-tsreaper-of6v/
【图解】O(n) 线性做法Python/Java/C/Go
代码
/** lc appleetcode.cn id2867 langcpp** [2867] 统计树中的合法路径数目*/// lc codestart// 树型 DPclass Solution
{
private:#define MAXN (int)1e5bool inited false;bool flag[MAXN 10];// 筛法预处理 1e5 以内的质数void init(){if (inited)return;inited true;memset(flag, 0, sizeof(flag));flag[0] flag[1] true;for (int i 2; i * i MAXN; i)if (!flag[i])for (int j i 1; j MAXN; j i)flag[j] true;}public:long long countPaths(int n, vectorvectorint edges){init();vectorint e[n 1];for (auto edge : edges){e[edge[0]].push_back(edge[1]);e[edge[1]].push_back(edge[0]);}long long ans 0;int f[n 1], g[n 1];// 树 dpfunctionvoid(int, int) dfs [](int sn, int fa){if (flag[sn])f[sn] 1, g[sn] 0;elsef[sn] 0, g[sn] 1;for (int fn : e[sn])if (fn ! fa){dfs(fn, sn);// 路径上深度最低的节点为 sn这样的合法路径有几条ans f[sn] * g[fn] g[sn] * f[fn];// 更新以 sn 为起点且走到子树里的路径数量if (flag[sn]){f[sn] f[fn];g[sn] g[fn];}else{g[sn] f[fn];}}};dfs(1, 0);return ans;}
};
// lc codeend复杂度分析
时间复杂度O(n)其中 n 是数组 edges 的长度。
空间复杂度O(n)其中 n 是数组 edges 的长度。
