leetcode 周赛 364

参考视频：

单调栈【力扣周赛 364】

8048. 最大二进制奇数

题目链接

给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。

你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。

以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。

注意 返回的结果字符串 可以 含前导零。

---

思路：把第一个 1 放在末尾，其他的 1 从第一个从前往后进行交换，

void swap(char* s, int i, int j) {char t = s[i];s[i] = s[j];s[j] = t;
}char* maximumOddBinaryNumber(char* s) {int length = strlen(s);bool flag = false;int i = 0, j = 0;while (i < length-1) {if (s[i] == '1') {if (!flag) {flag = true;swap(s, i, length - 1);}else {swap(s, i, j);j++;i++;}}else {i++;}}return s;
}

为什么下面这里不管 s[i] 是否等于 s[j]

swap(s, i, j);
j++;
i++;

如果一开始 j 指向了0，那么 i 会往后遍历寻找到下一个 1 ，进行交换后，i、j 都后移 1 位，此时 j 不可能指向 1，因为上一个 1 已经被交换到前面去了。

如果一开始 j 指向了 1 ，那么 i、j 一起后移，直到指向了 0，然后 i 单独后移寻找下一个 1，这就重现了之前的步骤。

也就是说，j 一定会指向在 0 的位置，哪怕它一开始就指向在 1。于是，不会出现 1 和 1交换的情况，除了当前元素与当前元素自身交换时。

100049. 美丽塔 I

题目链接

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

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

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

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

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

• 1 <= n == maxHeights <= 10^3
• 1 <= maxHeights[i] <= 10^9

---

暴力枚举：每个元素为山顶的情况都枚举一次，计算每一次的数组和，和最大

// 计算数组和
long long calculateSum(int* arr,int length) {long long sum = 0;for (int i = 0; i < length; i++) {sum += arr[i];}return sum;
}long long maximumSumOfHeights(int* maxHeights, int maxHeightsSize) {long long max = 0;int* temp = (int*)malloc(maxHeightsSize * sizeof(int));for (int i = 0; i < maxHeightsSize; i++) {for (int i = 0; i < maxHeightsSize; i++) {temp[i] = maxHeights[i];}// 对 i 左边进行同化，削平山顶for (int j = i; j >= 1; j--) {if (temp[j] < temp[j - 1]) {temp[j - 1] = temp[j];}}// 对 i 右边进行同化for (int j = i; j < maxHeightsSize - 1; j++) {if (temp[j] < temp[j + 1]) {temp[j + 1] = temp[j];}}long long t = calculateSum(temp, maxHeightsSize);max = max > t ? max : t;}free(temp); // 释放动态分配的内存return max;
}

100048. 美丽塔 II

题目链接

给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。

你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。

如果以下条件满足，我们称这些塔是 美丽 的：

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

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

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

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

• 1 <= n == maxHeights <= 10^5
• 1 <= maxHeights[i] <= 10^9

---

思路：单调栈+前后缀数组

维护一个单调栈，栈元素为数组元素下标，对应的值从栈底到栈顶严格递增。

从后往前遍历数组，如果栈非空且当前元素小于等于栈顶元素，那么出栈，直到当前元素大于栈顶元素，更新 sum 值，减去出栈的，注意栈为空的情况。退出循环后，sum 加上要进栈的当前元素，它会覆盖前面 n-i 或 st.top()-previous 个元素。将当前 sum 值加入到 suffix 数组。

从前往后遍历时要完成的操作目的是一样的。

最后，选出 suffix[i]+prefix[i]-maxHeights[i] 最大的值。

#include<iostream>
#include<stack>
#include<vector>
#include<math.h>
using namespace std;
typedef long long ll;
long long maximumSumOfHeights(vector<int>& maxHeights) {int n = maxHeights.size();vector<ll> suffix(n);stack<int> st;ll sum = 0;for (int i = n - 1; i >= 0; i--) {while (!st.empty() && maxHeights[i] <= maxHeights[st.top()]) {int previous = st.top();st.pop();if (st.empty()) {sum -= (ll)maxHeights[previous] * (n - previous);}else {sum -= (ll)maxHeights[previous] * (st.top() - previous);}}if (st.empty()) {sum += (ll)maxHeights[i] * (n - i);}else {sum += (ll)maxHeights[i] * (st.top() - i);}suffix[i] = sum;st.push(i);}st = stack<int>();sum = 0;vector<ll> prefix(n);for (int i = 0; i < n; i++) {while (!st.empty() && maxHeights[i] <= maxHeights[st.top()]) {int previous = st.top();st.pop();if (st.empty()) {sum -= (ll)maxHeights[previous] * (previous + 1);}else {sum -= (ll)maxHeights[previous] * (previous - st.top());}}if (st.empty()) {sum += (ll)maxHeights[i] * (i + 1);}else {sum += (ll)maxHeights[i] * (i-st.top());}prefix[i] = sum;st.push(i);}ll maxSum = 0;for (int i = 0; i < n; i++) {maxSum = max(maxSum, prefix[i] + suffix[i] - maxHeights[i]);}return maxSum;
}
int main() {vector<int> maxHeights = {5, 3, 4, 1, 1};cout << maximumSumOfHeights(maxHeights);
}

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 <= 10^5
• edges.length == n - 1
• edges[i].length == 2
• 1 <= ui, vi <= n
• 输入保证 edges 形成一棵合法的树。

const int MAX_NUM = 1e5;
bool isNonPrime[MAX_NUM + 1]; // 非质数=true，质数=falseint initialize = []() {isNonPrime[1] = true;for (int num = 2; num * num <= MAX_NUM; num++) {if (!isNonPrime[num]) {for (int multiple = num * num; multiple <= MAX_NUM; multiple += num) {isNonPrime[multiple] = true;}}}return 0;
}();class Solution {
public:long long countPaths(int numNodes, vector<vector<int>> &edges) {// 创建邻接列表表示图的结构vector<vector<int>> adjacencyList(numNodes + 1);for (auto &edge : edges) {int node1 = edge[0], node2 = edge[1];adjacencyList[node1].push_back(node2);adjacencyList[node2].push_back(node1);}// 用于记录DFS遍历的节点vector<int> visitedNodes;// 定义DFS函数，遍历与当前节点相关的非质数节点function<void(int, int)> dfs = [&](int currentNode, int parentNode) {visitedNodes.push_back(currentNode);for (int adjacentNode : adjacencyList[currentNode]) {if (adjacentNode != parentNode && isNonPrime[adjacentNode]) {dfs(adjacentNode, currentNode);}}};// 用于记录每个节点所在子树的节点数量vector<int> subtreeSize(numNodes + 1);long long result = 0;for (int currentNode = 1; currentNode <= numNodes; currentNode++) {if (isNonPrime[currentNode]) continue; // 跳过非质数节点int nonPrimeNodesSum = 0;for (int adjacentNode : adjacencyList[currentNode]) {if (!isNonPrime[adjacentNode]) continue; //跳过质数节点if (subtreeSize[adjacentNode] == 0) {visitedNodes.clear();// 执行DFS遍历，记录子树中的节点dfs(adjacentNode, -1);for (int node : visitedNodes) {subtreeSize[node] = visitedNodes.size();}}// 计算与当前节点相关的路径数量result += (long long)subtreeSize[adjacentNode] * nonPrimeNodesSum;nonPrimeNodesSum += subtreeSize[adjacentNode];}// 加上从当前节点出发的路径数量result += nonPrimeNodesSum;}return result;}
};