文章目录
竞赛链接
https://leetcode.cn/contest/weekly-contest-360
Q1：8015. 距离原点最远的点（贪心）
https://leetcode.cn/problems/furthest-point-from-origin/
提示：
1 <= moves.length == n <= 50
moves 仅由字符 'L'、'R' 和 '_' 组成
抓住本质，R 和 L 是不能改变的，而 _ 是可以随意选择的，因此可以在最后决定 _ 往哪个方向走。
class Solution {
public int furthestDistanceFromOrigin(String moves) {
int ans = 0, cnt = 0, pos = 0;
for (char ch: moves.toCharArray()) {
if (ch == 'R') pos++;
else if (ch == 'L') pos--;
else cnt++;
}
return Math.abs(pos) + cnt;
}
}
Q2：8022. 找出美丽数组的最小和（贪心）
https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/
提示：
1 <= n <= 10^5
1 <= target <= 10^5
这道题目和 第 359 场周赛 中的 6450. k-avoiding 数组的最小总和 几乎一样。
我们还是用贪心来解决，从小到大，能选就选。
class Solution {
public long minimumPossibleSum(int n, int target) {
long ans = 0;
Set<Integer> s = new HashSet<>();
for (int i = 1; s.size() < n; ++i) {
if (!s.contains(target - i)) {
s.add(i);
ans += i;
}
}
return ans;
}
}
Q3：2835. 使子序列的和等于目标的最少操作次数（贪心）
https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/
提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 2^30
nums 只包含非负整数，且均为 2 的幂。
1 <= target < 2^31
思路
首先确定 sum >= target 则一定有解，否则一定无解。
竞赛时丑陋代码
class Solution {
static Map<Integer, Integer> m = new HashMap(), m2 = new HashMap();
static {
for (int i = 0, v = 1; i <= 30; ++i, v *= 2) {
m.put(v, i);
m2.put(i, v);
}
}
public int minOperations(List<Integer> nums, int target) {
long sum = 0;
int[] cnt = new int[31], cnt2 = new int[31];
for (int num: nums) {
sum += num;
cnt[m.get(num)]++;
}
if (sum < target) return -1;
for (int i = 30; i >= 0; --i) {
if (target >= m2.get(i)) {
cnt2[i]++;
target -= m2.get(i);
}
}
int v = 0, ans = 0, last = -1;
for (int i = 0; i <= 30; ++i) {
if (cnt[i] > cnt2[i]) {
if (last != -1) {
ans += i - last;
last = -1;
v += (cnt[i] - cnt2[i] - 1) * m2.get(i);
} else {
v += (cnt[i] - cnt2[i]) * m2.get(i);
}
} else if (cnt[i] < cnt2[i]) {
if (v >= (cnt2[i] - cnt[i]) * m2.get(i)) {
v -= (cnt2[i] - cnt[i]) * m2.get(i);
}
else if (last == -1) last = i;
}
}
return ans;
}
}
优雅代码
https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/solutions/2413344/tan-xin-by-endlesscheng-immn/
class Solution {
public int minOperations(List<Integer> nums, int target) {
long s = 0; // 求和
long[] cnt = new long[31]; // 统计2^i的数量
for (int x: nums) {
s += x;
cnt[Integer.numberOfTrailingZeros(x)]++;
}
if (s < target) return -1; // 无解的情况
int ans = 0, i = 0;
s = 0;
// 注意这里是1L，因为i 最大是 30，这是可以进循环的，但是加一后就变成 31 了，虽然一定不会进入循环，但是要在 while 那里判断一下。
while ((1L << i) <= target) {
s += cnt[i] << i;
int mask = (int) ((1L << ++i) - 1);
if (s >= (target & mask)) continue; // 检查当前和能否填补target部分
ans++; // 否则需要分解更大的数字
while (cnt[i] == 0) {
ans++;
i++;
}
}
return ans;
}
}
Q4：2836. 在传球游戏中最大化函数值（⭐⭐⭐⭐⭐树上倍增）
https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/
提示：
1 <= receiver.length == n <= 10^5
0 <= receiver[i] <= n - 1
1 <= k <= 10^10
解法——利用倍增算法
利用倍增算法，预处理每个节点 x 的第 2^i个祖先节点，以及从 x 的父节点到 x 的第 2^i 个祖先节点的节点编号之和。最后枚举起点 x，一边向上跳一边累加节点编号。
可以从代码模板中修改过来，多了要维护节点之间的和。
class Solution {
public long getMaxFunctionValue(List<Integer> receiver, long k) {
int n = receiver.size(); // 节点的个数
int m = 64 - Long.numberOfLeadingZeros(k); // k的二进制长度
int[][] pa = new int[n][m]; // 节点x的第2^i个祖宗节点的变好
long[][] sum = new long[n][m]; // 节点x的父节点到x的第2^i个祖宗节点的节点编号之和
// 初始化dp数组
for (int i = 0; i < n; ++i) {
pa[i][0] = receiver.get(i);
sum[i][0] = receiver.get(i);
}
// 递推dp数组（先枚举i，再枚举x）
for (int i = 0; i < m - 1; ++i) { // 注意这里的条件是 i < m - 1
for (int x = 0; x < n; ++x) {
int p = pa[x][i];
pa[x][i + 1] = p < 0? -1: pa[p][i];
// 合并节点的和
sum[x][i + 1] = sum[x][i] + sum[p][i];
}
}
long ans = 0;
// 枚举各个节点作为起始节点
for (int i = 0; i < n; ++i) {
long s = i;
int x = i;
for (long t = k; t > 0; t &= t - 1) {
int ctz = Long.numberOfTrailingZeros(t);
// 要先处理求和，再处理节点的变化
s += sum[x][ctz];
x = pa[x][ctz];
}
ans = Math.max(ans, s);
}
return ans;
}
}
受 cpu 缓存的影响，倍增的二维数组开成 log*n 会比 n*log 快很多。
二维数组开成 logn * n 的形状会比开成 n * logn 的形状快很多，是因为在计算机中，连续的内存访问比随机的内存访问更快。当我们按行访问一个二维数组时，我们可以利用缓存行的概念，即将一行的数据读入缓存中，这样下一次访问时就可以直接从缓存中读取数据，而不需要再次从内存中读取。如果我们按列访问二维数组，则每次访问都需要跨越多个缓存行，这样会导致缓存失效，从而降低程序的性能。因此，将二维数组按行存储可以提高程序的性能。
所以可以将代码修改成如下：
class Solution {
public long getMaxFunctionValue(List<Integer> receiver, long k) {
int n = receiver.size(); // 节点的个数
int m = 64 - Long.numberOfLeadingZeros(k); // k的二进制长度
int[][] pa = new int[m][n]; // 节点x的第2^i个祖宗节点的变好
long[][] sum = new long[m][n]; // 节点x的父节点到x的第2^i个祖宗节点的节点编号之和
// 初始化dp数组
for (int i = 0; i < n; ++i) {
pa[0][i] = receiver.get(i);
sum[0][i] = receiver.get(i);
}
// 递推dp数组（先枚举i，再枚举x）
for (int i = 0; i < m - 1; ++i) { // 注意这里的条件是 i < m - 1
for (int x = 0; x < n; ++x) {
int p = pa[i][x];
pa[i + 1][x] = p < 0? -1: pa[i][p];
// 合并节点的和
sum[i + 1][x] = sum[i][x] + sum[i][p];
}
}
long ans = 0;
// 枚举各个节点作为起始节点
for (int i = 0; i < n; ++i) {
long s = i;
int x = i;
for (long t = k; t > 0; t &= t - 1) {
int ctz = Long.numberOfTrailingZeros(t);
// 要先处理求和，再处理节点的变化
s += sum[ctz][x];
x = pa[ctz][x];
}
ans = Math.max(ans, s);
}
return ans;
}
}
执行用时从 237ms 加速到了 65ms 。
模板题——1483. 树节点的第 K 个祖先
https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/description/
提示：
1 <= k <= n <= 5 * 10^4
parent[0] == -1 表示编号为 0 的节点是根节点。
对于所有的 0 < i < n ，0 <= parent[i] < n 总成立
0 <= node < n
至多查询 5 * 10^4 次
https://leetcode.cn/problems/kth-ancestor-of-a-tree-node/solutions/2305895/mo-ban-jiang-jie-shu-shang-bei-zeng-suan-v3rw/
本质上是动态规划，记 pa[x][i] 为每个节点 x 的第 2^i 个祖先节点。（如果不存在则为 -1）。
计算方式如下：
pa[x][1] = pa[pa[x][0]][0] 的意思是，x 节点的爷爷是 x 节点的父亲的父亲。
一般的，有 pa[x][i + 1] = pa[pa[x][i]][i]。
class TreeAncestor {
int[][] pa;
// 使用原始数据将整个 pa 数组预处理出来
public TreeAncestor(int n, int[] parent) {
int m = 32 - Integer.numberOfLeadingZeros(n); // n的二进制长度
pa = new int[n][m]; // 表示节点i的2^j个祖宗节点
// 初始化dp数组，即填充每个节点的父亲节点
for (int i = 0; i < n; ++i) {
pa[i][0] = parent[i];
}
// 先枚举i，再枚举x
// 相当于先算出所有爷爷节点，再算出所有爷爷的爷爷节点
for (int i = 0; i < m - 1; i++) {
for (int x = 0; x < n; ++x) {
int p = pa[x][i]; // 取出x的第2^i个祖宗节点
// x的第2^(i+1)个祖宗节点 等于 x的第2^i个祖宗节点的第2^i个祖宗节点
pa[x][i + 1] = p < 0? -1: pa[p][i];
}
}
}
// 取出node节点的第k个祖宗节点
public int getKthAncestor(int node, int k) {
// 写法1 从低位到高位枚举
// int m = 32 - Integer.numberOfLeadingZeros(k); // k的二进制长度
// for (int i = 0; i < m; ++i) {
// if ((k >> i & 1) == 1) { // k的二进制当前位为1
// node = pa[node][i];
// if (node < 0) break;
// }
// }
// return node;
// 写法2 不断去掉k末尾的1
for (; k != 0 && node != -1; k &= k - 1) {
node = pa[node][Integer.numberOfTrailingZeros(k)];
}
return node;
}
}
/**
* Your TreeAncestor object will be instantiated and called as such:
* TreeAncestor obj = new TreeAncestor(n, parent);
* int param_1 = obj.getKthAncestor(node,k);
*/
成绩记录
最后一题实在是写不出来了。(不过还好好像大家也都写不出来）
