leetcode 周赛 364
参考视频：
单调栈【力扣周赛 364】
文章目录
- 8048. 最大二进制奇数
- 100049. 美丽塔 I
- 100048. 美丽塔 II
- 100047. 统计树中的合法路径数目
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 <= 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 <= n == maxHeights <= 10^31 <= 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 <= 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 <= n == maxHeights <= 10^51 <= 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^5edges.length == n - 1edges[i].length == 21 <= 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;}
};