标签： hard

目标

给你一个下标从 0 开始的整数数组 nums ，它包含 3 * n 个元素。

你可以从 nums 中删除 恰好 n 个元素，剩下的 2 * n 个元素将会被分成两个 相同大小 的部分。

• 前面 n 个元素属于第一部分，它们的和记为 sumfirst 。
• 后面 n 个元素属于第二部分，它们的和记为 sumsecond 。

两部分和的 差值 记为 sumfirst - sumsecond 。

• 比方说，sumfirst = 3 且 sumsecond = 2 ，它们的差值为 1 。
• 再比方，sumfirst = 2 且 sumsecond = 3 ，它们的差值为 -1 。

请你返回删除 n 个元素之后，剩下两部分和的 差值的最小值 是多少。

示例 1：

输入：nums = [3,1,2]
输出：-1
解释：nums 有 3 个元素，所以 n = 1 。
所以我们需要从 nums 中删除 1 个元素，并将剩下的元素分成两部分。
- 如果我们删除 nums[0] = 3 ，数组变为 [1,2] 。两部分和的差值为 1 - 2 = -1 。
- 如果我们删除 nums[1] = 1 ，数组变为 [3,2] 。两部分和的差值为 3 - 2 = 1 。
- 如果我们删除 nums[2] = 2 ，数组变为 [3,1] 。两部分和的差值为 3 - 1 = 2 。
两部分和的最小差值为 min(-1,1,2) = -1 。

示例 2：

输入：nums = [7,9,5,8,1,3]
输出：1
解释：n = 2 。所以我们需要删除 2 个元素，并将剩下元素分为 2 部分。
如果我们删除元素 nums[2] = 5 和 nums[3] = 8 ，剩下元素为 [7,9,1,3] 。和的差值为 (7+9) - (1+3) = 12 。
为了得到最小差值，我们应该删除 nums[1] = 9 和 nums[4] = 1 ，剩下的元素为 [7,5,8,3] 。和的差值为 (7+5) - (8+3) = 1 。
观察可知，最优答案为 1 。

说明：

• nums.length == 3 * n
• 1 <= n <= 10^5
• 1 <= nums[i] <= 10^5

思路

有一个长度为 3n 的数组，删除其中的 n 个元素，使得剩余的 2n 个元素中，前 n 个元素的和 减去 后 n 个元素和 最小。

将数组划分为长度不小于 k 的两部分，枚举分界线，进行前后缀分解，计算左侧前 k 小元素的和，以及右侧前 k 大元素的和。

可以使用长度为 k 的优先队列来维护第 k 大/小元素，根据加入与移出的元素，可以知道队列所有元素的和的变化。

代码

/**
 * @date 2025-07-18 8:43
 */
public class MinimumDifference2163 {

    public long minimumDifference(int[] nums) {
        int l = nums.length;
        int n = l / 3;
        long[] suffix = new long[l + 1];
        long[] prefix = new long[l + 1];
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
            suffix[l - i] = suffix[l - i + 1] + nums[l - i];
        }
        PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a);
        PriorityQueue<Integer> right = new PriorityQueue<>();
        for (int i = 0; i < 2 * n; i++) {
            left.add(nums[i]);
            if (left.size() > n) {
                Integer num = left.poll();
                prefix[i + 1] = prefix[i] + nums[i] - num;
            }
        }
        for (int i = l - 1; i >= n; i--) {
            right.add(nums[i]);
            if (right.size() > n) {
                Integer num = right.poll();
                suffix[i] = suffix[i + 1] + nums[i] - num;
            }
        }
        long res = Long.MAX_VALUE;
        for (int i = n; i <= 2 * n; i++) {
            res = Math.min(res, prefix[i] - suffix[i]);
        }
        return res;
    }

}

性能

目标

给你一个 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

代码

性能