博客

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

样例

解题思路

渣渣洲还不会。有空再做。题解都是离线+字典树