凡客网站建立,长春站建了多少年,网站空间1,小程序制作费用多少参考视频#xff1a; 单调栈【力扣周赛 364】 文章目录 8048. 最大二进制奇数100049. 美丽塔 I100048. 美丽塔 II100047. 统计树中的合法路径数目 8048. 最大二进制奇数
题目链接
给你一个 二进制 字符串 s #xff0c;其中至少包含一个 1 。
你必须按某种方式 重新排列 字…参考视频 单调栈【力扣周赛 364】 文章目录 8048. 最大二进制奇数100049. 美丽塔 I100048. 美丽塔 II100047. 统计树中的合法路径数目 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] 最大的值。
#includeiostream
#includestack
#includevector
#includemath.h
using namespace std;
typedef long long ll;
long long maximumSumOfHeights(vectorint maxHeights) {int n maxHeights.size();vectorll suffix(n);stackint 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 stackint();sum 0;vectorll 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() {vectorint 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, vectorvectorint edges) {// 创建邻接列表表示图的结构vectorvectorint 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遍历的节点vectorint visitedNodes;// 定义DFS函数遍历与当前节点相关的非质数节点functionvoid(int, int) dfs [](int currentNode, int parentNode) {visitedNodes.push_back(currentNode);for (int adjacentNode : adjacencyList[currentNode]) {if (adjacentNode ! parentNode isNonPrime[adjacentNode]) {dfs(adjacentNode, currentNode);}}};// 用于记录每个节点所在子树的节点数量vectorint 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;}
};
