leetcode 周赛 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

swap(s, i, j);
j++;
i++;
1
2
3

如果一开始 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
#include
#include
#include
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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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，质数=false

int 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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63