參考視頻：

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，這就重現(xiàn)了之前的步驟。

也就是說，j 一定會指向在 0 的位置，哪怕它一開始就指向在 1。于是，不會出現(xiàn) 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); // 釋放動態(tài)分配的內存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 值，減去出棧的，注意棧為空的情況。退出循環(huán)后，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. 統(tǒng)計樹中的合法路徑數目

題目鏈接

給你一棵 n 個節(jié)點的無向樹，節(jié)點編號為 1 到 n 。給你一個整數 n 和一個長度為 n - 1 的二維整數數組 edges ，其中 edges[i] = [ui, vi] 表示節(jié)點 ui 和 vi 在樹中有一條邊。

請你返回樹中的 合法路徑數目 。

如果在節(jié)點 a 到節(jié)點 b 之間 恰好有一個 節(jié)點的編號是質數，那么我們稱路徑 (a, b) 是 合法的 。

注意：

• 路徑 (a, b) 指的是一條從節(jié)點 a 開始到節(jié)點 b 結束的一個節(jié)點序列，序列中的節(jié)點 互不相同 ，且相鄰節(jié)點之間在樹上有一條邊。
• 路徑 (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) {// 創(chuàng)建鄰接列表表示圖的結構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遍歷的節(jié)點vector<int> visitedNodes;// 定義DFS函數，遍歷與當前節(jié)點相關的非質數節(jié)點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);}}};// 用于記錄每個節(jié)點所在子樹的節(jié)點數量vector<int> subtreeSize(numNodes + 1);long long result = 0;for (int currentNode = 1; currentNode <= numNodes; currentNode++) {if (isNonPrime[currentNode]) continue; // 跳過非質數節(jié)點int nonPrimeNodesSum = 0;for (int adjacentNode : adjacencyList[currentNode]) {if (!isNonPrime[adjacentNode]) continue; //跳過質數節(jié)點if (subtreeSize[adjacentNode] == 0) {visitedNodes.clear();// 執(zhí)行DFS遍歷，記錄子樹中的節(jié)點dfs(adjacentNode, -1);for (int node : visitedNodes) {subtreeSize[node] = visitedNodes.size();}}// 計算與當前節(jié)點相關的路徑數量result += (long long)subtreeSize[adjacentNode] * nonPrimeNodesSum;nonPrimeNodesSum += subtreeSize[adjacentNode];}// 加上從當前節(jié)點出發(fā)的路徑數量result += nonPrimeNodesSum;}return result;}
};