标签： todo

目标

给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。

这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得 pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。

比方说，给你 questions = [[3, 2], [4, 3], [4, 4], [2, 5]] ：

• 如果问题 0 被解决了， 那么你可以获得 3 分，但你不能解决问题 1 和 2 。
• 如果你跳过问题 0 ，且解决问题 1 ，你将获得 4 分但是不能解决问题 2 和 3 。

请你返回这场考试里你能获得的 最高 分数。

示例 1：

输入：questions = [[3,2],[4,3],[4,4],[2,5]]
输出：5
解释：解决问题 0 和 3 得到最高分。
- 解决问题 0 ：获得 3 分，但接下来 2 个问题都不能解决。
- 不能解决问题 1 和 2
- 解决问题 3 ：获得 2 分
总得分为：3 + 2 = 5 。没有别的办法获得 5 分或者多于 5 分。

示例 2：

输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
输出：7
解释：解决问题 1 和 4 得到最高分。
- 跳过问题 0
- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
- 不能解决问题 2 和 3
- 解决问题 4 ：获得 5 分
总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

说明：

• 1 <= questions.length <= 10^5
• questions[i].length == 2
• 1 <= pointsi, brainpoweri <= 10^5

思路

有一个二维数组 questions 表示一场考试里的一系列题目，questions[i][0] 表示解决第 i 题能获得的分数，questions[i][1] 表示解决该题需要消耗的脑力，即解决了第 i 题后，i 后面的 questions[i][1] 个题目都无法解决。返回在该场考试所能获得的最高分。

这个题有许多值得思考的地方，有空整理一下。//todo

代码

/**
 * @date 2025-04-01 8:47
 */
public class MostPoints2140 {

    public long mostPoints(int[][] questions) {
        int n = questions.length;
        long[] dp = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            int j = Math.min(i + questions[i][1] + 1, n);
            dp[i] = Math.max(dp[i + 1], dp[j] + questions[i][0]);
        }
        return dp[0];
    }

}

性能

目标

给你一个整数 n ，表示下标从 0 开始的内存数组的大小。所有内存单元开始都是空闲的。

请你设计一个具备以下功能的内存分配器：

1. 分配 一块大小为 size 的连续空闲内存单元并赋 id mID 。
2. 释放 给定 id mID 对应的所有内存单元。

注意：

• 多个块可以被分配到同一个 mID 。
• 你必须释放 mID 对应的所有内存单元，即便这些内存单元被分配在不同的块中。

实现 Allocator 类：

• Allocator(int n) 使用一个大小为 n 的内存数组初始化 Allocator 对象。
• int allocate(int size, int mID) 找出大小为 size 个连续空闲内存单元且位于 最左侧 的块，分配并赋 id mID 。返回块的第一个下标。如果不存在这样的块，返回 -1 。
• int freeMemory(int mID) 释放 id mID 对应的所有内存单元。返回释放的内存单元数目。

示例：

输入
["Allocator", "allocate", "allocate", "allocate", "freeMemory", "allocate", "allocate", "allocate", "freeMemory", "allocate", "freeMemory"]
[[10], [1, 1], [1, 2], [1, 3], [2], [3, 4], [1, 1], [1, 1], [1], [10, 2], [7]]
输出
[null, 0, 1, 2, 1, 3, 1, 6, 3, -1, 0]

解释
Allocator loc = new Allocator(10); // 初始化一个大小为 10 的内存数组，所有内存单元都是空闲的。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 0 。内存数组变为 [1, , , , , , , , , ]。返回 0 。
loc.allocate(1, 2); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,2, , , , , , , , ]。返回 1 。
loc.allocate(1, 3); // 最左侧的块的第一个下标是 2 。内存数组变为 [1,2,3, , , , , , , ]。返回 2 。
loc.freeMemory(2); // 释放 mID 为 2 的所有内存单元。内存数组变为 [1, ,3, , , , , , , ] 。返回 1 ，因为只有 1 个 mID 为 2 的内存单元。
loc.allocate(3, 4); // 最左侧的块的第一个下标是 3 。内存数组变为 [1, ,3,4,4,4, , , , ]。返回 3 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 1 。内存数组变为 [1,1,3,4,4,4, , , , ]。返回 1 。
loc.allocate(1, 1); // 最左侧的块的第一个下标是 6 。内存数组变为 [1,1,3,4,4,4,1, , , ]。返回 6 。
loc.freeMemory(1); // 释放 mID 为 1 的所有内存单元。内存数组变为 [ , ,3,4,4,4, , , , ] 。返回 3 ，因为有 3 个 mID 为 1 的内存单元。
loc.allocate(10, 2); // 无法找出长度为 10 个连续空闲内存单元的空闲块，所有返回 -1 。
loc.freeMemory(7); // 释放 mID 为 7 的所有内存单元。内存数组保持原状，因为不存在 mID 为 7 的内存单元。返回 0 。

说明：

• 1 <= n, size, mID <= 1000
• 最多调用 allocate 和 free 方法 1000 次

提示:

• Can you simulate the process?
• Use brute force to find the leftmost free block and free each occupied memory unit

思路

设计一个内存分配器来管理大小为 n 的内存数组，要求实现初始化、分配与释放方法。内存分配方法返回大小为 size 的连续空闲内存的最左侧下标，并为这些内存分配标识 mID。内存释放则是释放 mID 的所有内存单元。

有网友使用链表来维护空间的分配状态，定义节点属性：起点、大小、是否已分配、下一个节点、mID。分配空间时挨个查找，释放空间类似。使用节点对象表示区间，空间合并起来比较方便。

提示说可以使用暴力解法，暴力解的时间复杂度为 O(qn)。

// todo 线段树

代码

/**
 * @date 2025-02-25 10:03
 */
class Allocator {

    private int[] flag;
    private int n;

    public Allocator(int n) {
        this.flag = new int[n];
        this.n = n;
    }

    public int allocate(int size, int mID) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (flag[i] != 0) {
                cnt = 0;
                continue;
            } else {
                cnt++;
            }
            if (cnt == size) {
                int start = i - size + 1;
                for (; i >= start; i--) {
                    flag[i] = mID;
                }
                return start;
            }
        }
        return -1;
    }

    public int freeMemory(int mID) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (flag[i] == mID) {
                flag[i] = 0;
                cnt++;
            }
        }
        return cnt;
    }
}

性能

目标

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时，则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时（例如三个日程安排都在同一时间内），就会产生 三重预订。

事件能够用一对整数 startTime 和 endTime 表示，在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类：

• MyCalendarTwo() 初始化日历对象。
• boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订，返回 true。否则，返回 false 并且不要将该日程安排添加到日历中。

示例 1：

输入：
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, true, true, true, false, true, true]
解释：
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 返回 True，能够预定该日程。
myCalendarTwo.book(50, 60); // 返回 True，能够预定该日程。
myCalendarTwo.book(10, 40); // 返回 True，该日程能够被重复预定。
myCalendarTwo.book(5, 15);  // 返回 False，该日程导致了三重预定，所以不能预定。
myCalendarTwo.book(5, 10); // 返回 True，能够预定该日程，因为它不使用已经双重预订的时间 10。
myCalendarTwo.book(25, 55); // 返回 True，能够预定该日程，因为时间段 [25, 40) 将被第三个日程重复预定，时间段 [40, 50) 将被单独预定，而时间段 [50, 55) 将被第二个日程重复预定。

说明：

• 0 <= start < end <= 10^9
• 最多调用 book 1000 次。

思路

本题与 729.我的日程安排表I 的区别是允许相交一次。

使用差分数组记录区间元素被覆盖的次数，由于数据范围太大，这里使用 TreeMap 计数。

// todo 线段树

代码

/**
 * @date 2025-01-03 10:32
 */
public class MyCalendarTwo {

    TreeMap<Integer, Integer> cnt = new TreeMap<>();

    public MyCalendarTwo() {

    }

    public boolean book(int startTime, int endTime) {
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1);
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1);
        int appearanceCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (key >= endTime) {
                break;
            }
            appearanceCnt += value;
            if (appearanceCnt > 2) {
                cnt.put(startTime, cnt.getOrDefault(startTime, 0) - 1);
                cnt.put(endTime, cnt.getOrDefault(endTime, 0) + 1);
                return false;
            }
        }
        return true;
    }
}

性能