https://leetcode-cn.com/contest/weekly-contest-250/
可以输入的最大单词数
https://leetcode-cn.com/problems/maximum-number-of-words-you-can-type/
描述
键盘出现了一些故障，有些字母键无法正常工作。而键盘上所有其他键都能够正常工作。
给你一个由若干单词组成的字符串 text ，单词间由单个空格组成（不含前导和尾随空格）；另有一个字符串 brokenLetters ，由所有已损坏的不同字母键组成，返回你可以使用此键盘完全输入的 text 中单词的数目。
- 1 <= text.length <= 104
- 0 <= brokenLetters.length <= 26
- text 由若干用单个空格分隔的单词组成，且不含任何前导和尾随空格
- 每个单词仅由小写英文字母组成
- brokenLetters 由 互不相同 的小写英文字母组成
样例
示例 1：
输入：text = "hello world", brokenLetters = "ad"
输出：1
解释：无法输入 "world" ，因为字母键 'd' 已损坏。
示例 2：
输入：text = "leet code", brokenLetters = "lt"
输出：1
解释：无法输入 "leet" ，因为字母键 'l' 和 't' 已损坏。
示例 3：
输入：text = "leet code", brokenLetters = "e"
输出：0
解释：无法输入任何单词，因为字母键 'e' 已损坏。
解题思路
简单的模拟题，记录哪些字母坏了，然后判断每个单词能否能够输入。
AC代码
public int canBeTypedWords(String text, String brokenLetters) {
// 记录坏掉的字母
boolean[] flag = new boolean[200];
for (char ch : brokenLetters.toCharArray()) {
flag[ch] = true;
}
String[] s = text.split(" ");
int count = 0;
// 遍历单词
for (String str : s) {
boolean check = true;
for (char c : str.toCharArray()) {
// 判断单词能否输入
if (flag[c]) {
check = false;
break;
}
}
// 单词能够输入，计数加一
if (check) {
++count;
}
}
return count;
}
新增的最少台阶数
https://leetcode-cn.com/problems/add-minimum-number-of-rungs/
描述
给你一个 严格递增 的整数数组 rungs ，用于表示梯子上每一台阶的 高度 。当前你正站在高度为 0 的地板上，并打算爬到最后一个台阶。
另给你一个整数 dist 。每次移动中，你可以到达下一个距离你当前位置（地板或台阶）不超过 dist 高度的台阶。当然，你也可以在任何正 整数 高度处插入尚不存在的新台阶。
返回爬到最后一阶时必须添加到梯子上的 最少 台阶数。
-
1 <= rungs.length <= 10
-
1 <= rungs[i] <= 10
-
1 <= dist <= 10
-
rungs
严格递增
样例
示例 1：
输入：rungs = [1,3,5,10], dist = 2
输出：2
解释：
现在无法到达最后一阶。
在高度为 7 和 8 的位置增设新的台阶，以爬上梯子。
梯子在高度为 [1,3,5,7,8,10] 的位置上有台阶。
示例 2：
输入：rungs = [3,6,8,10], dist = 3
输出：0
解释：
这个梯子无需增设新台阶也可以爬上去。
示例 3：
输入：rungs = [3,4,6,7], dist = 2
输出：1
解释：
现在无法从地板到达梯子的第一阶。
在高度为 1 的位置增设新的台阶，以爬上梯子。
梯子在高度为 [1,3,4,6,7] 的位置上有台阶。
示例 4：
输入：rungs = [5], dist = 10
输出：0
解释：这个梯子无需增设新台阶也可以爬上去。
解题思路
因为数组是严格递增的，所以我只要考虑从当前台阶上到下一个台阶时需不需要加梯子
- 当前台阶据下一个台阶不超过 dist ：不用加梯子
- 当前台阶据下一个台阶超过 dist：不断加梯子，知道距离不超过dist
AC代码
public int addRungs(int[] rungs, int dist) {
// 所需要梯子数
int tizi = 0;
// 当前台阶高度
int height = 0;
// 遍历台阶
for (int num : rungs) {
// 当前台阶不能抵达下一个台阶
while (num - height > dist) {
// 计算差距
int diff = num - height;
// 计算到达下一个台阶需要多少个梯子
int x = diff / dist;
// 差距是 dist 的整数可以少一个梯子
if (diff % dist == 0) {
--x;
}
// 加上所需的梯子数
tizi += x;
// 更新台阶高度
height = height + x * dist;
}
// 可以抵达下一个台阶
height = num;
}
return tizi;
}
扣分后的最大得分
https://leetcode-cn.com/problems/maximum-number-of-points-with-cost/
描述
给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。
你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分 增加 points[r][c] 。
然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m – 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分 减少 abs(c1 – c2) 。
请你返回你能得到的 最大 得分。
abs(x) 定义为：
- 如果 x >= 0 ，那么值为 x 。
- 如果 x < 0 ，那么值为 -x 。
- m == points.length
- n == points[r].length
- 1 <= m, n <= 105
- 1 <= m * n <= 105
- 0 <= points[r][c] <= 105
样例
解题思路
开始想了一个动规方程
f[i][j] = Math.
max
(f[i][j], f[i – 1][k] – Math.
abs
(j – k)) + points[i][j]
然后
最后一个超时。因为没有优化，动规是O(nmm)，m是一行的长度；碰上最大数据，妥妥地超时。然后一直想怎么优化优化优化~。然后就时间到了。。渣渣如我
赛后打开题解：https://leetcode-cn.com/problems/maximum-number-of-points-with-cost/solution/dp-you-hua-ji-qiao-chai-xiang-qian-hou-z-5vvc/
把我上面的动规方程中的 | j – k | 去掉绝对值就可以发现一片新天地啊！！
这样只要能够知道 max(f[i – 1][k] + k) (k <= j)，max(f[i – 1][k] – k)(k > j) 就可以在O(1)的时间内获取结果，时间复杂度就降到了O(nm)。
所以我们先记录上一层的 f[i – 1][k] + k，f[i – 1][k] – k；然后因为是遍历数组，所以 k <= j 是可以在遍历的时候得出来max(f[i – ][k] + k)，所以用辅助数组计算上一层的 max(f[i – 1][k] – k)，就可以在O(1)的时间内得到结果啦。
灵老师yyds。
AC代码
public long maxPoints(int[][] points) {
// 记录
long ans = 0;
int n = points.length, m = points[0].length;
// 记录当前层的 f[i - 1][k] + k 和 f[i - 1][k] - k 值。
long[][] f = new long[m][2];
// 记录max( f[i - 1][k] - k;
long[] help = new long[m];
for (int i = 0; i < n; ++i) {
if (i == 0) {
// 初始化第一行
for (int j = 0; j < m; j++) {
int x = points[i][j];
ans = Math.max(ans, x);
f[j][0] = x + j;
f[j][1] = x - j;
}
} else {
// 记录 max( f[i - 1][k] + k )
long preMax = Integer.MIN_VALUE;
// 动规过程
for (int j = 0; j < m; j++) {
// 更新preMax
preMax = Math.max(preMax, f[j][0]);
int x = points[i][j];
long now = Math.max(x - j + preMax, x + j + help[j]);
// 更新答案
ans = Math.max(ans, now);
f[j][0] = now + j;
f[j][1] = now - j;
}
}
// 辅助函数记录max(f[i - 1][k] - k)
help[m - 1] = f[m - 1][1];
for (int j = m - 2; j >= 0; --j) {
help[j] = Math.max(help[j + 1], f[j][1]);
}
}
return ans;
}
查询最大基因差
https://leetcode-cn.com/problems/maximum-genetic-difference-query/
描述
给你一棵 n 个节点的有根树，节点编号从 0 到 n – 1 。每个节点的编号表示这个节点的 独一无二的基因值 （也就是说节点 x 的基因值为 x）。两个基因值的 基因差 是两者的 异或和 。给你整数数组 parents ，其中 parents[i] 是节点 i 的父节点。如果节点 x 是树的 根 ，那么 parents[x] == -1 。
给你查询数组 queries ，其中 queries[i] = [nodei, vali] 。对于查询 i ，请你找到 vali 和 pi 的 最大基因差 ，其中 pi 是节点 nodei 到根之间的任意节点（包含 nodei 和根节点）。更正式的，你想要最大化 vali XOR pi 。
请你返回数组 ans ，其中 ans[i] 是第 i 个查询的答案。
2 <= parents.length <= 105
对于每个 不是 根节点的 i ，有 0 <= parents[i] <= parents.length – 1 。
- parents[root] == -1
- 1 <= queries.length <= 3 * 104
- 0 <= nodei <= parents.length – 1
- 0 <= vali <= 2 * 105
样例
解题思路
渣渣洲还不会。有空再做。题解都是离线+字典树