8048. Maximum Odd Binary Number
给你一个 二进制 字符串 s ，其中至少包含一个 '1' 。
你必须按某种方式 重新排列 字符串中的位，使得到的二进制数字是可以由该组合生成的 最大二进制奇数 。
以字符串形式，表示并返回可以由给定组合生成的最大二进制奇数。
注意 返回的结果字符串 可以 含前导零。
测试样例：
输入：s = "010"
输出："001"
解释：
因为字符串 s 中仅有一个 '1' ，其必须出现在最后一位上。所以答案是 "001" 。
解答：计算一下string中，1的个数。然后用贪婪。
class Solution {
public String maximumOddBinaryNumber(String s) {
int one = 0;
for (int i = 0; i < s.length(); ++i) {
if (s.charAt(i) == '1') {
++one;
}
}
StringBuilder res = new StringBuilder();
for (int i = 0; i < s.length(); ++i) {
if (i != s.length() - 1) {
if (one > 1) {
res.append(1);
--one;
} else {
res.append(0);
}
} else {
res.append(1);
}
}
return res.toString();
}
}
100049. Beautiful Towers I
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
- 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]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
测试样例：
输入：maxHeights = [5,3,4,1,1]
输出：13
解释：
和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。
解答：这道题目和这周第三题其实是一样的，只是范围不一样。这里就直接用第三题的思路来做了。因为需要变成山状数组，那么我们可以选定一个数作为山峰。如果能快速计算出作为山峰时，当前数组的结果，那么就可以得到答案了。接下来的重点就是怎么快速计算结果。
我们可以利用前缀和的方法来计算。维护一个单调栈，保持单调栈一直是递增状态。然后计算前缀和。
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
int[] arr = new int[maxHeights.size()];
int len = 0;
for (int n : maxHeights) {
arr[len++] = n;
}
long[] left = new long[len];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; ++i) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
left[i] = arr[i] * (i + 1L);
} else {
long h = arr[i];
left[i] = left[stack.peek()] + h * (i - stack.peek());
}
stack.push(i);
}
long res = 0;
stack = new Stack<>();
long[] right = new long[len];
for (int i = len - 1; i >= 0; --i) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
right[i] = (arr[i] * ((long) len - i));
res = Math.max(res, left[i] + arr[i] * (len - i - 1L));
} else {
long h = arr[i];
right[i] = right[stack.peek()] + arr[i] * ((long) stack.peek() - i);
res = Math.max(res, left[i] + right[stack.peek()] + arr[i] * ((long) stack.peek() - i - 1));
}
stack.push(i);
}
return res;
}
}100048. Beautiful Towers II
给你一个长度为 n 下标从 0 开始的整数数组 maxHeights 。
你的任务是在坐标轴上建 n 座塔。第 i 座塔的下标为 i ，高度为 heights[i] 。
如果以下条件满足，我们称这些塔是 美丽 的：
- 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]
请你返回满足 美丽塔 要求的方案中，高度和的最大值 。
测试样例：
输入：maxHeights = [5,3,4,1,1]
输出：13
解释：
和最大的美丽塔方案为 heights = [5,3,3,1,1] ，这是一个美丽塔方案，因为：
- 1 <= heights[i] <= maxHeights[i]
- heights 是个山状数组，峰值在 i = 0 处。
13 是所有美丽塔方案中的最大高度和。
解答：这道题目和这周第三题其实是一样的，只是范围不一样。这里就直接用第三题的思路来做了。因为需要变成山状数组，那么我们可以选定一个数作为山峰。如果能快速计算出作为山峰时，当前数组的结果，那么就可以得到答案了。接下来的重点就是怎么快速计算结果。
我们可以利用前缀和的方法来计算。维护一个单调栈，保持单调栈一直是递增状态。然后计算前缀和。
class Solution {
public long maximumSumOfHeights(List<Integer> maxHeights) {
int[] arr = new int[maxHeights.size()];
int len = 0;
for (int n : maxHeights) {
arr[len++] = n;
}
long[] left = new long[len];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < len; ++i) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
left[i] = arr[i] * (i + 1L);
} else {
long h = arr[i];
left[i] = left[stack.peek()] + h * (i - stack.peek());
}
stack.push(i);
}
long res = 0;
stack = new Stack<>();
long[] right = new long[len];
for (int i = len - 1; i >= 0; --i) {
while (!stack.isEmpty() && arr[i] < arr[stack.peek()]) {
stack.pop();
}
if (stack.isEmpty()) {
right[i] = (arr[i] * ((long) len - i));
res = Math.max(res, left[i] + arr[i] * (len - i - 1L));
} else {
long h = arr[i];
right[i] = right[stack.peek()] + arr[i] * ((long) stack.peek() - i);
res = Math.max(res, left[i] + right[stack.peek()] + arr[i] * ((long) stack.peek() - i - 1));
}
stack.push(i);
}
return res;
}
}100047. Count Valid Paths in a Tree
给你一棵 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) 视为 同一条 路径，且只计入答案 一次 。
测试样例
输入：n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]
输出：4
恰好有一个质数编号的节点路径有：
- (1, 2) 因为路径 1 到 2 只包含一个质数 2 。
- (1, 3) 因为路径 1 到 3 只包含一个质数 3 。
- (1, 4) 因为路径 1 到 4 只包含一个质数 2 。
- (2, 4) 因为路径 2 到 4 只包含一个质数 2 。
只有 4 条合法路径。
解答：最近几周的第四题都是一个套路：在树上遍历记录历史结果，第二次遍历再更新一次。
这次也是类似的，我们先假设1是root，从1开始遍历，计算当前节点到最近的质数的所有路径数。第二次遍历，假设当前节点是质数，那么我们计算当前质数节点所有遍历可能。
class Solution {
private int[] isPrime;
private long[] mem;
private List<Integer>[] edges;
private long res;
public long countPaths(int n, int[][] _edges) {
this.edges = new List[n + 1];
isPrime = new int[n + 1];
for (int i = 0; i <= n; ++i) {
edges[i] = new ArrayList<>();
isPrime[i] = -1;
}
for (int[] e : _edges) {
edges[e[0]].add(e[1]);
edges[e[1]].add(e[0]);
}
mem = new long[n + 1];
initialTree(1, -1);
res = 0;
dfsResult(1, -1, 0);
return res;
}
private long initialTree(int cur, int last) {
long decent = 0;
for (int n : edges[cur]) {
if (n != last) {
decent += initialTree(n, cur);
}
}
mem[cur] = isPrime(cur) ? 0 : decent + 1;
return mem[cur];
}
private void dfsResult(int cur, int last, long lastVal) {
long sum = lastVal;
for (int n : edges[cur]) {
if (n != last) {
sum += mem[n];
}
}
if (isPrime(cur)) {
long sumDup = sum;
for (int n : edges[cur]) {
long tmp;
if (n == last) {
tmp = lastVal;
} else {
tmp = mem[n];
}
sumDup -= tmp;
res += tmp * sumDup;
res += tmp;
}
for (int n : edges[cur]) {
if (n != last) {
dfsResult(n, cur, 0);
}
}
} else {
for (int n : edges[cur]) {
if (n != last) {
dfsResult(n, cur, sum - mem[n] + 1);
}
}
}
}
private boolean isPrime(int n) {
if (isPrime[n] == -1) {
if (n == 1) {
isPrime[n] = 1;
} else {
isPrime[n] = 0;
for (int t = 2; t * t <= n; ++t) {
if (n % t == 0) {
isPrime[n] = 1;
break;
}
}
}
}
return isPrime[n] == 0;
}
}