⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 常识星球发问。
学习数据结构与算法的关键在于把握问题背地的算法思维框架，你的思考越形象，它能笼罩的问题域就越广，了解难度也更简单。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起领会上分之旅。
本文是 LeetCode 上分之旅系列的第 47 篇文章，往期回顾请移步到文章开端\~
LeetCode 周赛 364
T1. 最大二进制奇数（Easy）
- 标签：贪婪
T2. 漂亮塔 I（Medium）
- 标签：枚举、前后缀合成、枯燥栈
T3. 漂亮塔 II（Medium）
- 标签：枚举、前后缀合成、枯燥栈
T4. 统计树中的非法门路数目（Hard）
- 标签：DFS、质数
T1. 最大二进制奇数（Easy）
https://leetcode.cn/problems/maximum-odd-binary-number/description/题解（模仿）
简略模拟题，先计算 $1$ 的个数，将其中一个 $1$ 置于最低位，其它 $1$ 置于最高位：
class Solution { fun maximumOddBinaryNumber(s: String): String { val cnt = s.count { it == '1' } return StringBuilder().apply { repeat(cnt - 1) { append("1") } repeat(s.length - cnt) { append("0") } append("1") }.toString() }}class Solution: def maximumOddBinaryNumber(self, s: str) -> str: n, cnt = len(s), s.count("1") return "1" * (cnt - 1) + "0" * (n - cnt) + "1"class Solution {public: string maximumOddBinaryNumber(string s) { int n = s.length(); int cnt = 0; for (auto& e : s) { if (e == '1') cnt++; } string ret; for (int i = 0; i < cnt - 1; i++) { ret.push_back('1'); } for (int i = 0; i < n - cnt; i++) { ret.push_back('0'); } ret.push_back('1'); return ret; }};复杂度剖析：
- 工夫复杂度：$O(n)$ 线性遍历；
- 空间复杂度：$O(1)$ 不思考后果字符串。
T2. 漂亮塔 I（Medium）
https://leetcode.cn/problems/beautiful-towers-i/description/同 T3. 漂亮塔 I
T3. 漂亮塔 II（Medium）
https://leetcode.cn/problems/beautiful-towers-ii/description/问题剖析
初步剖析：
- 问题指标： 结构满足条件的计划，使得数组出现山状数组，返回元素和；
- 计划条件： 从数组的最大值向左侧为递加，向右侧也为递加。
思考实现：
- 在 T2. 漂亮塔 I（Medium） 中的数据量只有 $1000$，咱们能够枚举以每个点作为山峰（数组最大值）的计划，从山顶顺次向两侧递加，使得以后地位不高于前一个地位，整体的工夫复杂度是 $O(n^2)$；
- 在 T3. 漂亮塔 II（Medium） 中数据量有 $10^5$，咱们须要思考低于平方工夫复杂度的办法。
思考优化：
以示例 [6,5,3,9,2,7] 为例，咱们察看以 $3$ 和 $9$ 作为山顶的两个计划：
以 3 作为山顶：3 3 |3 3| 2 2以 9 作为山顶3 3 |3 9| 2 2能够发现：以 $3$ 作为山顶的左侧与以 $9$ 为山顶的右侧在两个计划之间是能够复用的，至此发现解决办法：咱们能够别离预处理出以每个节点作为山顶的前缀和后缀的和：
- $pre[i]$ 示意以 $maxHeights[i]$ 作为山顶时左侧段的前缀和；
- $suf[i]$ 示意以 $maxHeights[i]$ 作为山顶时右侧段的后缀和。
那么，最佳计划就是 $pre[i] + suf[i] - maxHeight[i]$ 的最大值。 当初，最初的问题是如何以均摊 $O(1)$ 的工夫复杂度计算出每个元素前后缀的和？
思考递推关系：
持续以示例 [6,5,3,9,2,7] 为例：
- 以 $6$ 为山顶，前缀为 $[6]$
- 以 $5$ 为山顶，须要保障左侧元素不大于 $5$，因而找到 $6$ 并批改为 $5$，前缀为 $[5, 5]$
- 以 $3$ 为山顶，须要保障左侧元素不大于 $3$，因而找到两个 $5$ 并批改为 $3$，前缀为 $[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$。「寻找上一个更小元素」，这是枯燥栈的典型场景。
题解一（枚举）
枚举以每个元素作为山顶的计划：
class Solution { fun maximumSumOfHeights(maxHeights: List<Int>): Long { val n = maxHeights.size var ret = 0L for (i in maxHeights.indices) { var curSum = maxHeights[i].toLong() var pre = maxHeights[i] for (j in i - 1 downTo 0) { pre = min(pre, maxHeights[j]) curSum += pre } pre = maxHeights[i] for (j in i + 1 ..< n) { pre = min(pre, maxHeights[j]) curSum += pre } ret = max(ret, curSum) } return ret }}class Solution: def maximumSumOfHeights(self, maxHeights: List[int]) -> int: n, ret = len(maxHeights), 0 for i in range(n): curSum = maxHeights[i] pre = maxHeights[i] for j in range(i + 1, n): pre = min(pre, maxHeights[j]) curSum += pre pre = maxHeights[i] for j in range(i - 1, -1, -1): pre = min(pre, maxHeights[j]) curSum += pre ret = max(ret, curSum) return retclass Solution {public: long long maximumSumOfHeights(vector<int>& maxHeights) { int n = maxHeights.size(); long long ret = 0; for (int i = 0; i < n; i++) { long long curSum = maxHeights[i]; int pre = maxHeights[i]; for (int j = i + 1; j < n; j++) { pre = min(pre, maxHeights[j]); curSum += pre; } pre = maxHeights[i]; for (int j = i - 1; j >= 0; j--) { pre = min(pre, maxHeights[j]); curSum += pre; } ret = max(ret, curSum); } return ret; }};复杂度剖析：
- 工夫复杂度：$O(n^2)$ 每个计划的工夫复杂度是 $O(n)$，一共有 $n$ 种计划；
- 空间复杂度：$O(1)$ 仅应用常量级别空间。
题解二（前后缀合成 + 枯燥栈）
应用单点栈保护前后缀数组，为了便于边界计算，咱们结构长为 $n + 1$ 的数组。以示例 [6,5,3,9,2,7] 为例：
0, 5, 6, 10, 4, 513, 8, 6, 2, 1, 0class Solution { fun maximumSumOfHeights(maxHeights: List<Int>): Long { val n = maxHeights.size val suf = LongArray(n + 1) val pre = LongArray(n + 1) // 枯燥栈求前缀 val stack = java.util.ArrayDeque<Int>() for (i in 0 until n) { // 弹出栈顶 while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) { stack.pop() } val j = if (stack.isEmpty()) -1 else stack.peek() pre[i + 1] = pre[j + 1] + 1L * (i - j) * maxHeights[i] stack.push(i) } // 枯燥栈求后缀 stack.clear() for (i in n - 1 downTo 0) { // 弹出栈顶 while (!stack.isEmpty() && maxHeights[stack.peek()] > maxHeights[i]) { stack.pop() } val j = if (stack.isEmpty()) n else stack.peek() suf[i] = suf[j] + 1L * (j - i) * maxHeights[i] stack.push(i) } // 合并 var ret = 0L for (i in 0 until n) { ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i]) } return ret }}class Solution: def maximumSumOfHeights(self, maxHeights: List[int]) -> int: n = len(maxHeights) suf = [0] * (n + 1) pre = [0] * (n + 1) stack = [] # 枯燥栈求前缀 for i in range(n): # 弹出栈顶 while stack and maxHeights[stack[-1]] > maxHeights[i]: stack.pop() j = stack[-1] if stack else -1 pre[i + 1] = pre[j + 1] + (i - j) * maxHeights[i] stack.append(i) # 枯燥栈求后缀 stack = [] for i in range(n - 1, -1, -1): # 弹出栈顶 while stack and maxHeights[stack[-1]] > maxHeights[i]: stack.pop() j = stack[-1] if stack else n suf[i] = suf[j] + (j - i) * maxHeights[i] stack.append(i) # 合并 ret = 0 for i in range(n): ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i]) return retclass Solution {public: long long maximumSumOfHeights(vector<int>& maxHeights) { int n = maxHeights.size(); vector<long long> suf(n + 1, 0); vector<long long> pre(n + 1, 0); stack<int> st; // 枯燥栈求前缀 for (int i = 0; i < n; i++) { // 弹出栈顶 while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) { st.pop(); } int j = st.empty() ? -1 : st.top(); pre[i + 1] = pre[j + 1] + 1LL * (i - j) * maxHeights[i]; st.push(i); } // 枯燥栈求后缀 while (!st.empty()) st.pop(); for (int i = n - 1; i >= 0; i--) { // 弹出栈顶 while (!st.empty() && maxHeights[st.top()] > maxHeights[i]) { st.pop(); } int j = st.empty() ? n : st.top(); suf[i] = suf[j] + 1LL * (j - i) * maxHeights[i]; st.push(i); } // 合并 long long ret = 0; for (int i = 0; i < n; i++) { ret = max(ret, pre[i + 1] + suf[i] - maxHeights[i]); } return ret; }};复杂度剖析：
- 工夫复杂度：$O(n)$ 在一侧的计算中，每个元素最多如何和出栈 $1$ 次；
- 空间复杂度：$O(n)$ 前后缀数组空间。
T4. 统计树中的非法门路数目（Hard）
https://leetcode.cn/problems/count-valid-paths-in-a-tree/description/这道题仿佛比 T3 还简略一些。
问题剖析
初步剖析：
- 问题指标： 寻找满足条件的计划数；
- 问题条件： 门路 $[a, b]$ 上质数的数目有且仅有 $1$；
- 问题因素： 门路和 - 示意门路上质数的数目。
思考实现：
子问题： 对于以根节点 x 的原问题，能够分为 3 种状况：
- 左子树能够结构的计划数
- 右子树能够结构的计划数
- 如果根节点为质数：「从根到子树节点的门路和为 $0$ 的数目」与「从根到其它子树节点的门路和为 $0$ 的数目」的乘积（乘法原理）
题解（DFS）
结构 DFS 函数，子树的 DFS 返回值为两个值：
- $cnt0$：到子树节点和为 $0$ 的门路数；
- $cnt1$：到子树节点和为 $1$ 的门路数；
返回后果时：
- 如果根节点为质数，那么只能与 $cnt0$ 个门路和为 $1$ 的门路；
- 如果根节点为非质数，那么 $cnt0$ 个门路能够组成和为 $0$ 的门路，同理 $cnt1$ 个门路能够组成和为 $1$ 的门路。
在子树的计算过程中还会结构后果：
因为题目阐明 $[a, b]$ 与 $[b, a]$ 是雷同门路，咱们能够记录以后子树左侧曾经计算过的 $cnt0$ 和 $cnt1$ 的累加和，再与以后子树的 $cnt0$ 与 $cnt1$ 做乘法：
$ret += cnt0 * cnt[1] + cnt1 * cnt[0]$
class Solution { companion object { val U = 100000 val primes = LinkedList<Int>() val isPrime = BooleanArray(U + 1) { true } init { isPrime[1] = false for (i in 2 .. U) { if (isPrime[i]) primes.add(i) for (e in primes) { if (i * e > U) break isPrime[i * e] = false if (i % e == 0) break } } } } fun countPaths(n: Int, edges: Array<IntArray>): Long { val graph = Array(n + 1) { LinkedList<Int>() } for ((from, to) in edges) { graph[from].add(to) graph[to].add(from) } var ret = 0L // return 0 和 1 的数量 fun dfs(i: Int, pre: Int): IntArray { // 终止条件 var cnt = IntArray(2) if (isPrime[i]) { cnt[1] = 1 } else { cnt[0] = 1 } // 递归 for (to in graph[i]) { if (to == pre) continue // 返祖边 val (cnt0, cnt1) = dfs(to, i) // 记录计划 ret += cnt0 * cnt[1] + cnt1 * cnt[0] // 记录影响 if (isPrime[i]) { cnt[1] += cnt0 } else { cnt[0] += cnt0 cnt[1] += cnt1 } } return cnt } dfs(1, -1) // 随机抉择根节点 return ret }}U = 100000primes = deque()isPrime = [True] * (U + 1)isPrime[1] = Falsefor i in range(2, U + 1): if isPrime[i]: primes.append(i) for e in primes: if i * e > U: break isPrime[i * e] = False if i % e == 0: breakclass Solution: def countPaths(self, n, edges): graph = defaultdict(list) for u, v in edges: graph[u].append(v) graph[v].append(u) ret = 0 def dfs(i, pre): nonlocal ret # 批改内部变量 cnt = [0, 0] # 终止条件 if isPrime[i]: cnt[1] = 1 else: cnt[0] = 1 for to in graph[i]: if to == pre: continue # 返祖边 cnt0, cnt1 = dfs(to, i) # 记录计划 ret += cnt0 * cnt[1] + cnt1 * cnt[0] # 记录影响 if isPrime[i]: cnt[1] += cnt0 else: cnt[0] += cnt0 cnt[1] += cnt1 return cnt dfs(1, -1) # 随机抉择根节点 return retconst int U = 100000;list<int> primes;bool isPrime[U + 1];bool inited = false;void init() { if (inited) return; inited = true; memset(isPrime, true, sizeof(isPrime)); isPrime[1] = false; for (int i = 2; i <= U; ++i) { if (isPrime[i]) primes.push_back(i); for (auto e : primes) { if (i * e > U) break; isPrime[i * e] = false; if (i % e == 0) break; } }}class Solution {public: long long countPaths(int n, vector<vector<int>>& edges) { init(); vector<list<int>> graph(n + 1); for (const auto& edge : edges) { int from = edge[0]; int to = edge[1]; graph[from].push_back(to); graph[to].push_back(from); } long long ret = 0; // return 0 和 1 的数量 function<vector<int>(int, int)> dfs = [&](int i, int pre) -> vector<int> { // 终止条件 vector<int> cnt(2, 0); if (isPrime[i]) { cnt[1] = 1; } else { cnt[0] = 1; } // 递归 for (auto to : graph[i]) { if (to == pre) continue; // 返祖边 vector<int> subCnt = dfs(to, i); int cnt0 = subCnt[0]; int cnt1 = subCnt[1]; // 记录计划 ret += cnt0 * cnt[1] + cnt1 * cnt[0]; // 记录影响 if (isPrime[i]) { cnt[1] += cnt0; } else { cnt[0] += cnt0; cnt[1] += cnt1; } } return cnt; }; dfs(1, -1); // 随机抉择根节点 return ret; }};复杂度剖析：
- 工夫复杂度：预处理工夫为 $O(U)$，建图工夫 和 DFS 工夫为 $O(n)$；
- 空间复杂度：预处理空间为 $O(U)$，模仿空间为 $O(n)$。
枚举质数
OI - 素数筛法
枚举法：枚举 $[2, n]$ ，判断它是不是质数，整体工夫复杂度是 $O(n\sqrt{n})$
// 暴力求质数fun getPrimes(max: Int): IntArray { val primes = LinkedList<Int>() for (num in 2..max) { if (isPrime(num)) primes.add(num) } return primes.toIntArray()}// 质数判断fun isPrime(num: Int): Boolean { var x = 2 while (x * x <= num) { if (num % x == 0) return false x++ } return true}Eratosthenes 埃氏筛：如果 $x$ 是质数，那么 $x$ 的整数倍 $2x$、$3x$ 肯定不是质数。咱们设
isPrime[i]示意 $i$ 是否为质数。从小开始遍历，如果 $i$ 是质数，则同时将所有倍数标记为合数，整体工夫复杂度是 $O(nlgn)$为什么要从 $x^2$, $2x^2$ 开始标记，而不是 $2x$, $3x$ 开始标记，因为 $2x$, $3x$ 曾经被小于 $x$ 的质数标记过。
// 埃氏筛求质数val primes = LinkedList<Int>()val isPrime = BooleanArray(U + 1) { true }for (i in 2..U) { // 查看是否为质数，这里不须要调用 isPrime() 函数判断是否质数，因为它没被小于它的数标记过，那么肯定不是合数 if (!isPrime[i]) continue primes.add(i) // 标记 var x = i * i while (x <= U) { isPrime[x] = false x += i }}Euler 欧氏线性筛：只管咱们从 $x^2$ 开始标记来缩小反复标记，但埃氏筛还是会反复标记合数。为了防止反复标记，标记 $x$ 与 “小于等于 $x$ 的最小质因子的质数” 的乘积为合数，保障每个合数只被标记最小的质因子标记，整体工夫复杂度是 $O(n)$
// 线性筛求质数val primes = LinkedList<Int>()val isPrime = BooleanArray(U + 1) { true }for (i in 2..U) { // 查看是否为质数，这里不须要调用 isPrime() 函数判断是否质数，因为它没被小于它的数标记过，那么肯定不是合数 if (isPrime[i]) { primes.add(i) } // 标记 for (e in primes) { if (i * e > U) break isPrime[i * e] = false if (i % e == 0) break }}举荐浏览
LeetCode 上分之旅系列往期回顾：
- LeetCode 单周赛第 363 场 · 经典二分答案与质因数分解
- LeetCode 单周赛第 361 场 · 同余前缀和问题与经典倍增 LCA 算法
- LeetCode 双周赛第 113 场 · 精妙的 O(lgn) 扫描算法与树上 DP 问题
- LeetCode 双周赛第 112 场 · 计算机科学实质上是数学吗？
⭐️ 永远置信美妙的事件行将产生，欢送退出小彭的 Android 交换社群\~