标签： hard

目标

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须 完整 地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值 最大和 。

示例 1：

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

示例 2：

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

示例 3：

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。

说明：

• 1 <= k <= events.length
• 1 <= k * events.length <= 10^6
• 1 <= startDayi <= endDayi <= 10^9
• 1 <= valuei <= 10^6

思路

从 n 个会议中选择 k 个日期不冲突的参加，求参加会议的最大价值之和。

与 1353.最多可以参加的会议数目 不同之处在于必须从头到尾全程参会，并且最多参加 k 个。

定义 dp[i][k] 表示前 i - 1 个会议至多参加 k 个所能获得的最大价值。i == 0 表示没有参加任何会议。

按照结束时间排序，如果选择当前会议，则需要找到最后一个结束时间小于当前开始时间的下标 j，可以使用二分查找。

代码

/**
 * @date 2025-07-08 8:47
 */
public class MaxValue1751 {

    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        int n = events.length;
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i < n; i++) {
            int prev = find(events, events[i][0]);
            for (int j = 1; j <= k; j++) {
                dp[i + 1][j] = Math.max(dp[i][j], dp[prev + 1][j - 1] + events[i][2]);
            }
        }
        return dp[n][k];
    }

    public int find(int[][] events, int target) {
        int r = events.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (events[mid][1] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            mid = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

Alice 和 Bob 正在玩一个游戏。最初，Alice 有一个字符串 word = "a"。

给定一个正整数 k 和一个整数数组 operations，其中 operations[i] 表示第 i 次操作的类型。

现在 Bob 将要求 Alice 按顺序执行 所有 操作：

• 如果 operations[i] == 0，将 word 的一份 副本追加 到它自身。
• 如果 operations[i] == 1，将 word 中的每个字符 更改 为英文字母表中的 下一个 字符来生成一个新字符串，并将其 追加 到原始的 word。例如，对 "c" 进行操作生成 "cd"，对 "zb" 进行操作生成 "zbac"。

在执行所有操作后，返回 word 中第 k 个字符的值。

注意，在第二种类型的操作中，字符 'z' 可以变成 'a'。

示例 1:

输入：k = 5, operations = [0,0,0]
输出："a"
解释：
最初，word == "a"。Alice 按以下方式执行三次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "aa" 附加到 "aa"，word 变为 "aaaa"。
将 "aaaa" 附加到 "aaaa"，word 变为 "aaaaaaaa"。

示例 2:

输入：k = 10, operations = [0,1,0,1]
输出："b"
解释：
最初，word == "a"。Alice 按以下方式执行四次操作：
将 "a" 附加到 "a"，word 变为 "aa"。
将 "bb" 附加到 "aa"，word 变为 "aabb"。
将 "aabb" 附加到 "aabb"，word 变为 "aabbaabb"。
将 "bbccbbcc" 附加到 "aabbaabb"，word 变为 "aabbaabbbbccbbcc"。

说明：

• 1 <= k <= 10^14
• 1 <= operations.length <= 100
• operations[i] 可以是 0 或 1。
• 输入保证在执行所有操作后，word 至少有 k 个字符。

思路

开始的时候有一个字符 a，根据操作数组 operations 执行以下操作：

• 当 operations[i] == 0 时，将现有的所有字母拼接到当前字符后面。
• 当 operations[i] == 1 时，将现有的所有字母替换为它在字母表中的下一个字母（z 的下一个字母为 a），拼接到当前字符后面。

返回执行所有操作之后的第 k 个字母。

计算 tail = ceil(log2(k)) 表示操作次数的上界，如果 k <= 1 << tail，说明在左半边无需操作，否则在右半边，需要操作，它是从左半边的第 k - (1 << tail) 个元素转移而来，需要根据 operations[tail] 来确定字母是否变化。按照这个逻辑递归，直到 tail < 0，返回字母 a。

代码

/**
 * @date 2025-07-04 9:19
 */
public class KthCharacter3307 {

    public char kthCharacter(long k, int[] operations) {
        return kthCharacter(k, operations, 63 - Long.numberOfLeadingZeros(k - 1));
    }

    public char kthCharacter(long k, int[] operations, int tail) {
        if (tail < 0) {
            return 'a';
        }
        long p = 1L << tail;
        if (k <= p) {
            return (char) ('a' + ((kthCharacter(k, operations, tail - 1) - 'a') % 26));
        }
        return (char) ('a' + (kthCharacter(k - p, operations, tail - 1) - 'a' + operations[tail]) % 26);
    }

}

性能

目标

Alice 正在她的电脑上输入一个字符串。但是她打字技术比较笨拙，她 可能 在一个按键上按太久，导致一个字符被输入 多次 。

给你一个字符串 word ，它表示 最终 显示在 Alice 显示屏上的结果。同时给你一个 正 整数 k ，表示一开始 Alice 输入字符串的长度 至少 为 k 。

请你返回 Alice 一开始可能想要输入字符串的总方案数。

由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：word = "aabbccdd", k = 7
输出：5
解释：
可能的字符串包括："aabbccdd" ，"aabbccd" ，"aabbcdd" ，"aabccdd" 和 "abbccdd" 。

示例 2：

输入：word = "aabbccdd", k = 8
输出：1
解释：
唯一可能的字符串是 "aabbccdd" 。

示例 3：

输入：word = "aaabbb", k = 3
输出：8

说明：

• 1 <= word.length <= 5 * 10^5
• word 只包含小写英文字母。
• 1 <= k <= 2000

思路

有一个字符串，其中可能存在字符由于按键失灵没有及时抬起，导致该字符被输入多次。求原始字符串的总方案数，已知原字符串长度至少为 k。

与 3330.找到初始输入字符串I 相比取消了至多一个错误的限制，增加了原始字符的长度限制。

// todo

代码

性能

目标

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

说明:

• 1 <= k <= n <= 10^9

思路

求 1 ~ n 的所有数字按字典序排列后的第 k 个数字。

本来想要参考 386.字典序排数 取第 k 个数字。但是数据范围太大，O(n) 的解法不可行。

题目标签显示的是字典树。想象一棵 10 叉树，根为 0，从第一个孩子 1 开始，如果其子树大小小于剩余的数字个数，直接跳过，访问兄弟节点 2，否则进入下一层，从第一个孩子 10 开始，计算其子树大小，如果小于剩余数字个数，访问兄弟节点 11，否则进入下一层。以此类推。

如何统计子树的大小？可以将当前根节点 l 与兄弟节点 r 一起向下计算，当前层的节点个数 = Math.min(r, n + 1) - 1 - l + 1 即 Math.min(r, n + 1) - l。比如，l == 100, r == 200，计算 100 ~ 200 - 1 的数字个数。注意 r 与 n + 1 取最小值，因为要减 1 所以比较的是 n + 1。

代码

/**
 * @date 2025-06-09 8:44
 */
public class FindKthNumber440 {

    public int findKthNumber(int n, int k) {
        int i = 1;
        k--;
        while (k > 0) {
            int cnt = subTreeNodesCnt(i, n);
            if (cnt <= k) {
                k -= cnt;
                i++;
            } else {
                k--;
                i *= 10;
            }
        }

        return i;
    }

    public int subTreeNodesCnt(int root, int n) {
        int cnt = 0;
        long l = root;
        long r = root + 1;
        while (l <= n) {
            cnt += Math.min(r, n + 1) - l;
            l *= 10;
            r *= 10;
        }
        return cnt;
    }
}

性能