标签： 差分数组

目标

给你一个下标从 0 开始且长度为 n 的整数数组 differences ，它表示一个长度为 n + 1 的 隐藏 数组 相邻 元素之间的 差值 。更正式的表述为：我们将隐藏数组记作 hidden ，那么 differences[i] = hidden[i + 1] - hidden[i] 。

同时给你两个整数 lower 和 upper ，它们表示隐藏数组中所有数字的值都在 闭 区间 [lower, upper] 之间。

比方说，differences = [1, -3, 4] ，lower = 1 ，upper = 6 ，那么隐藏数组是一个长度为 4 且所有值都在 1 和 6 （包含两者）之间的数组。
[3, 4, 1, 5] 和 [4, 5, 2, 6] 都是符合要求的隐藏数组。
[5, 6, 3, 7] 不符合要求，因为它包含大于 6 的元素。
[1, 2, 3, 4] 不符合要求，因为相邻元素的差值不符合给定数据。
请你返回 符合 要求的隐藏数组的数目。如果没有符合要求的隐藏数组，请返回 0 。

示例 1：

输入：differences = [1,-3,4], lower = 1, upper = 6
输出：2
解释：符合要求的隐藏数组为：
- [3, 4, 1, 5]
- [4, 5, 2, 6]
所以返回 2 。

示例 2：

输入：differences = [3,-4,5,1,-2], lower = -4, upper = 5
输出：4
解释：符合要求的隐藏数组为：
- [-3, 0, -4, 1, 2, 0]
- [-2, 1, -3, 2, 3, 1]
- [-1, 2, -2, 3, 4, 2]
- [0, 3, -1, 4, 5, 3]
所以返回 4 。

示例 3：

输入：differences = [4,-7,2], lower = 3, upper = 6
输出：0
解释：没有符合要求的隐藏数组，所以返回 0 。

说明：

• n == differences.length
• 1 <= n <= 10^5
• -10^5 <= differences[i] <= 10^5
• -10^5 <= lower <= upper <= 10^5

思路

已知某数组的差分数组 differences，以及数组元素值的上下界 lower upper，求有多少个满足条件的数组。

确定了第一个元素，后面整个数组就确定了。数组最大值与最小值的差是固定的，差值小于 upper - lower 就存在符合条件的数组，有 upper - lower - (max - min) + 1 个。注意求 max 与 min 时数据可能溢出，使用 long 类型。

代码

/**
 * @date 2025-04-21 0:19
 */
public class NumberOfArrays2145 {

    public int numberOfArrays(int[] differences, int lower, int upper) {
        int n = differences.length;
        long max = 0;
        long min = 0;
        long val = 0;
        for (int i = 0; i < n; i++) {
            val += differences[i];
            max = Math.max(max, val);
            min = Math.min(min, val);
        }
        long res = upper - lower - (max - min) + 1;
        return (int) Math.max(res, 0);
    }

}

性能

目标

当 k 个日程存在一些非空交集时（即, k 个日程包含了一些相同时间），就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ，请你在每个日程安排添加后，返回一个整数 k ，表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排，你可以一直添加新的日程安排。

• MyCalendarThree() 初始化对象。
• int book(int startTime, int endTime) 返回一个整数 k ，表示日历中存在的 k 次预订的最大值。

示例：

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]
解释：
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ，第一个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ，第二个日程安排可以预订并且不存在相交，所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ，第三个日程安排 [10, 40) 与第一个日程安排相交，所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ，剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

说明：

• 0 <= startTime < endTime <= 10^9
• 每个测试用例，调用 book 函数最多不超过 400次

思路

参考 731.我的日程安排表II，同样的思路，只不过求得是相交区间数量的最大值。

代码

/**
 * @date 2025-01-04 15:40
 */
public class MyCalendarThree {

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

    public MyCalendarThree() {

    }

    public int book(int startTime, int endTime) {
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1);
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1);
        int res = 0;
        int appearanceCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int value = entry.getValue();
            appearanceCnt += value;
            res = Math.max(appearanceCnt, res);
        }
        return res;
    }
}

性能

目标

给你一个二进制数组 nums 。

你可以对数组执行以下操作 任意 次（也可以 0 次）：

• 选择数组中 任意 一个下标 i ，并将从下标 i 开始一直到数组末尾 所有 元素 反转 。

反转 一个元素指的是将它的值从 0 变 1 ，或者从 1 变 0 。

请你返回将 nums 中所有元素变为 1 的 最少 操作次数。

示例 1：

输入：nums = [0,1,1,0,1]
输出：4
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [0,0,0,1,0] 。
选择下标 i = 0 执行操作，得到 nums = [1,1,1,0,1] 。
选择下标 i = 4 执行操作，得到 nums = [1,1,1,0,0] 。
选择下标 i = 3 执行操作，得到 nums = [1,1,1,1,1] 。

示例 2：

输入：nums = [1,0,0,0]
输出：1
解释：
我们可以执行以下操作：
选择下标 i = 1 执行操作，得到 nums = [1,1,1,1] 。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 1

思路

有一个二进制数组 nums，每一次操作可以将当前元素以及之后的元素反转，问将所有元素变为 1 的最少操作次数。

这与昨天的题目 3191.使二进制数组全部等于1的最少操作次数I 类似，那个是将当前元素及后面两个元素反转。

还沿用昨天的思路，遇到 0 就进行操作，每一次操作需要对大量元素进行取模运算，因此考虑使用差分数组。这里差分数组初始均为 0，每次操作是针对当前元素及以后的所有元素，无需考虑后续的减法操作，因此只需要一个变量计数即可。

网友最快的算法并非使用变量计数然后判断奇偶性，考虑到最终目标是将所有元素都变为 1，每一次操作会将自身与其后的元素反转，对于初始数组任意位置 i，如果它为 0，该位置一定需要执行奇数次操作，因为执行偶数次反转最后还是 0。同理，如果为 1，需要执行 偶数 次操作。实际上每个位置是否需要执行操作是 确定的。

只要有一个初始条件，向后遍历的时候直接根据前一个元素与当前元素的关系判断是否需要累加操作即可，具体来说，如果它们值相同则不需要操作，如果不同则需要操作，直接累加这两个元素的异或值即可。

代码

/**
 * @date 2024-10-19 17:30
 */
public class MinOperations3192 {

    public int minOperations_v2(int[] nums) {
        int n = nums.length;
        int prev = nums[0];
        int res = prev ^ 1;
        for (int i = 1; i < n; i++) {
            res += prev ^ nums[i];
            prev = nums[i];
        }
        return res;
    }

    public int minOperations_v1(int[] nums) {
        int n = nums.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (((res % 2 ^ nums[i]) == 0)) {
                res++;
            }
        }
        return res;
    }

}

性能