标签： medium

目标

给你一个整数数组 nums，和一个整数 k 。

对于每个下标 i（0 <= i < nums.length），将 nums[i] 变成 nums[i] + k 或 nums[i] - k 。

nums 的 分数 是 nums 中最大元素和最小元素的差值。

在更改每个下标对应的值之后，返回 nums 的最小 分数 。

示例 1：

输入：nums = [1], k = 0
输出：0
解释：分数 = max(nums) - min(nums) = 1 - 1 = 0 。

示例 2：

输入：nums = [0,10], k = 2
输出：6
解释：将数组变为 [2, 8] 。分数 = max(nums) - min(nums) = 8 - 2 = 6 。

示例 3：

输入：nums = [1,3,6], k = 3
输出：3
解释：将数组变为 [4, 6, 3] 。分数 = max(nums) - min(nums) = 6 - 3 = 3 。

说明：

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

思路

这道题与 908.最小差值I 的区别是对于每个元素操作是 必选的，增加或减少的值 固定 为 k 而不是区间 [-k, k]。

每个元素都可以取 nums[i] + k 或 nums[i] - k，如果枚举所有可能的数组，然后再取最大最小值差的最小值显然是不可能的。不考虑重复元素的情况下，可能的数组有 2^n 种。

可以先排序，增大小的值，减少大的值，枚举二者的边界，比如前 i 个元素 [0, i - 1] 加 k，剩余元素减 k，这时上界为 Math.max(nums[i - 1] + k, nums[n - 1] - k) ，下界为 Math.min(nums[0] + k, nums[i] - k)，取上下界的最小值即可。

代码

/**
 * @date 2024-10-21 9:57
 */
public class SmallestRangeII910 {

    public int smallestRangeII(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int res = nums[n - 1] - nums[0];
        for (int i = 1; i < n; i++) {
            int max = Math.max(nums[i - 1] + k, nums[n - 1] - k);
            int min = Math.min(nums[0] + k, nums[i] - k);
            res = Math.min(res, max - min);
        }
        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;
    }

}

性能

目标

给你 2 枚相同 的鸡蛋，和一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都 会碎 ，从 f 楼层或比它低 的楼层落下的鸡蛋都 不会碎 。

每次操作，你可以取一枚 没有碎 的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例 1：

输入：n = 2
输出：2
解释：我们可以将第一枚鸡蛋从 1 楼扔下，然后将第二枚从 2 楼扔下。
如果第一枚鸡蛋碎了，可知 f = 0；
如果第二枚鸡蛋碎了，但第一枚没碎，可知 f = 1；
否则，当两个鸡蛋都没碎时，可知 f = 2。

示例 2：

输入：n = 100
输出：14
解释：
一种最优的策略是：
- 将第一枚鸡蛋从 9 楼扔下。如果碎了，那么 f 在 0 和 8 之间。将第二枚从 1 楼扔下，然后每扔一次上一层楼，在 8 次内找到 f 。总操作次数 = 1 + 8 = 9 。
- 如果第一枚鸡蛋没有碎，那么再把第一枚鸡蛋从 22 层扔下。如果碎了，那么 f 在 9 和 21 之间。将第二枚鸡蛋从 10 楼扔下，然后每扔一次上一层楼，在 12 次内找到 f 。总操作次数 = 2 + 12 = 14 。
- 如果第一枚鸡蛋没有再次碎掉，则按照类似的方法从 34, 45, 55, 64, 72, 79, 85, 90, 94, 97, 99 和 100 楼分别扔下第一枚鸡蛋。
不管结果如何，最多需要扔 14 次来确定 f 。

说明：

• 1 <= n <= 1000

思路

有一个 1 ~ n 层楼的建筑，存在一个楼层 f，任何大于 f 层落下的鸡蛋都会摔碎。现在有两个鸡蛋，每次操作可以从任意楼层向下扔鸡蛋，如果鸡蛋碎了则无法再使用，求确定 f 值的最小操作次数。

为了确保能够找到 f，如果第一个尝试的鸡蛋碎了，那么另一个鸡蛋只能从已知的安全楼层一层一层向上尝试。

观察示例2，可以从 n 开始 减 1 2 3 …… i 直到小于等于零，返回 i - 1即可。

看了题解，这样做可行的逻辑是这样的：

假设已知最小操作次数 k，我们扔第一枚鸡蛋选第几层？显然，应该选第 k 层，因为如果第一枚鸡蛋碎了，只需要从 1 ~ k - 1 枚举即可。

如果第一枚鸡蛋没碎，那么下一次选第几层？现在还剩下 k - 1 次尝试，所以应该选 k + 1 + (k - 2) = k + (k - 1) 层，因为如果在该层扔鸡蛋碎了，只需从 k + 1 ~ k + k - 2 枚举即可，共 k - 2 次，再加上前面尝试的 2 次，总次数为 k。

以此类推，我们可以确定总层数 n = k + (k - 1) + (k - 2) + …… + 2 + 1 = k * (k + 1)/2，解方程得 k = (sqrt(1+8*n) - 1)/2，结果需要向上取整。

代码

/**
 * @date 2024-10-13 19:30
 */
public class TwoEggDrop1884 {

    public int twoEggDrop_v1(int n) {
        return (int) Math.ceil((Math.sqrt(1 + 8 * n) - 1) / 2);
    }

    public int twoEggDrop(int n) {
        int i = 1;
        while (n > 0){
            n -= i++;
        }
        return i - 1;
    }
}

性能

目标

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

说明：

• 1 <= time.length <= 10^5
• 1 <= time[i], totalTrips <= 10^7

思路

一趟旅行可以选择 n 辆公交车，time[i] 表示第 i 辆公交完成旅途的时间，同一时间每辆公交车可以独立地运行，完成一趟旅途后立刻开始下一趟。问完成 totalTrips 次旅途最少需要花费多少时间。

使用二分法尝试最少花费的时间 least，完成旅途的次数为 sum(least/time[i])。查找的上界为 10^14（当只有一辆车，且它完成一趟旅行需要耗时 10^7，总共需要完成 10^7 趟旅行）。

可以优化的点是上下界的取值，我们可以求出公交车完成旅行所需时间的最大与最小值，假设所有公交完成时间均为最小值 min，那么平均每辆车需要完成 ⌈totalTrips / n⌉ 次旅途，时间的下界为⌈totalTrips / n⌉ * min，同理，上界为 ⌈totalTrips / n⌉ * max。

代码

/**
 * @date 2024-10-05 21:34
 */
public class MinimumTime2187 {

    public long minimumTime_v1(int[] time, int totalTrips) {
        int n = time.length;
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i : time) {
            min = Math.min(i, min);
            max = Math.max(i, max);
        }
        long average = ((long) totalTrips - 1) / n + 1;
        long l = average * min;
        long r = average * max;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    public long minimumTime(int[] time, int totalTrips) {
        long l = 0L, r = 100000000000000L;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    private boolean check(int[] time, int totalTrips, long least) {
        long cnt = 0L;
        for (int i : time) {
            cnt += least / i;
            if (cnt >= totalTrips) {
                return true;
            }
        }
        return false;
    }
}

性能

优化上下界并没有明显的差距，并且还增加了编码的复杂度。

目标

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

• 例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 10^7 ，且 hour 的 小数点后最多存在两位数字 。

示例 1：

输入：dist = [1,3,2], hour = 6
输出：1
解释：速度为 1 时：
- 第 1 趟列车运行需要 1/1 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 = 3 小时。
- 由于是在整数时间到达，可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 = 2 小时。
- 你将会恰好在第 6 小时到达。

示例 2：

输入：dist = [1,3,2], hour = 2.7
输出：3
解释：速度为 3 时：
- 第 1 趟列车运行需要 1/3 = 0.33333 小时。
- 由于不是在整数时间到达，故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 = 1 小时。
- 由于是在整数时间到达，可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 = 0.66667 小时。
- 你将会在第 2.66667 小时到达。

示例 3：

输入：dist = [1,3,2], hour = 1.9
输出：-1
解释：不可能准时到达，因为第 3 趟列车最早是在第 2 小时发车。

说明：

• n == dist.length
• 1 <= n <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hours 中，小数点后最多存在两位数字

思路

从家到办公室需要依次乘坐 n 趟列车，列车只在整点发车，已知每趟车的行驶距离 dist[i]，问在给定通勤时间 hour 内到达办公室，列车的最低时速是多少，取正整数，如果无法按时到达返回 -1。

我们假设时速为 v，那么到达办公室的时间为 cost = Σ⌈dist[i]/v⌉ + dist[n-1]/v 前面 n - 1 趟车通勤时间需要考虑等车时间，所以要向上取整，最后一趟车则不需要向上取整。我们只需要满足cost <= hour 即可。由于时速需要取正整数，那么 v 也应该向上取整。

这道题的难点在于如何在 v 未知的情况下，向上取整后再求和，没办法直接计算。只能搜索解空间了，我们可以估算出 v 的取值范围，然后使用二分查找代入式子计算并与 hour 比较。v 的下界为 Σdist[i]/hour，上界是 max(dist[i]) * 100，这相当于是一趟车最大的距离除以最小的时间，如果这个速度还赶不上，那就赶不上了。

求和的时间复杂度为 O(n)，n 最大 10^5 ，距离最大 10^5 有可能溢出，应使用 long 类型。二分查找的复杂度为 O(nlogv)，v 最大值为 10^10， log2(10^10) ≈ 33.2，总的规模为 10 ^ 6 可行。

代码

/**
 * @date 2024-10-02 21:44
 */
public class MinSpeedOnTime1870 {

    public int minSpeedOnTime(int[] dist, double hour) {
        long sum = 0;
        for (int value : dist) {
            sum += value;
        }
        int v = (int) Math.ceil(sum / hour - 0.5);
        long l = v, r = 200 * sum, m = l + (r - l) / 2;
        while (l <= r) {
            if (check(dist, hour, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l > 200 * sum ? -1 : (int)l;
    }

    private boolean check(int[] dist, double hour, long m) {
        int n = dist.length;
        double cost = 0;
        for (int i = 0; i < n - 1; i++) {
            cost += Math.ceil((double) dist[i] / m);
        }
        cost += (double) dist[n - 1] / m;
        return cost <= hour;
    }

}

性能