标签： hard

目标

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

说明:

• 3 <= n <= 10^5
• 1 <= queries.length <= 10^5
• queries[i].length == 2
• 0 <= queries[i][0] < queries[i][1] < n
• 1 < queries[i][1] - queries[i][0]
• 查询中不存在重复的道路。
• 不存在两个查询都满足 i != j 且 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。

思路

有 n 个城市，刚开始每一个城市 i 有一条单项道路通向城市 i + 1，有一个二维数组 queries，queries[i] 表示增加一条从 queries[i][0] 到 queries[i][1] 的单项道路，返回 answer 数组，answer[i] 表示增加了 queries[i] 之后从城市 0 到城市 n - 1 的最短路径。增加的路径保证不会出现相交的情况。

比昨天的题 3243.新增道路查询后的最短距离I 多了一个条件，新增的路径不会交叉。昨天首先考虑的就是今天这个思路，因为起点与终点是固定的，可以通过查询区间的关系来减小最短路径。当时考虑的差分数组解决不了区间包含的关系。

定义区间数组 interval，interval[i] = j, 表示 i -> j 有直达道路。如果发现查询的路径 [l, r] 已经被包含，直接略过。否则，循环记录区间 (l, r) 内的路径数，保存下一跳的城市 next = interval[l]，将 interval[l] 置为 r，l = next 直到 l >= r。注意最后一跳到 r 是没有计数的，相当于减去了将前面多余的步数，与直达的效果一样。 interval[l] = r 是第一次进入循环必须进行的操作，幸运的是它并不影响我们标记其它区间内的元素，当有更大的查询路径时，直接在 l 处就跳过了。

核心点是如何表示区间，如何判断区间是否重合，如何针对大区间减少的路径计数。

代码

/**
 * @date 2024-11-20 10:10
 */
public class ShortestDistanceAfterQueries3244 {

    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        int ql = queries.length;
        int[] res = new int[ql];
        int[] interval = new int[n - 1];
        Arrays.setAll(interval, i -> i + 1);
        int shortestPath = n - 1;
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            while (interval[l] < r) {
                int next = interval[l];
                interval[l] = r;
                l = next;
                shortestPath--;
            }
            res[i] = shortestPath;
        }
        return res;
    }

}

性能

目标

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数数组 answer ，其中 answer[i] 表示 s[li..ri] 中满足 k 约束 的 子字符串 的数量。

示例 1：

输入：s = "0001111", k = 2, queries = [[0,6]]
输出：[26]
解释：
对于查询 [0, 6]， s[0..6] = "0001111" 的所有子字符串中，除 s[0..5] = "000111" 和 s[0..6] = "0001111" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]
输出：[15,9,3]
解释：
s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

说明：

• 1 <= s.length <= 10^5
• s[i] 是 '0' 或 '1'
• 1 <= k <= s.length
• 1 <= queries.length <= 10^5
• queries[i] == [li, ri]
• 0 <= li <= ri < s.length
• 所有查询互不相同

思路

定义二进制字符串满足 k 约束的条件是字符串中 0 的个数 或者 1 的个数都不超过 k。求给定字符串满足 k 约束的子字符串数量。子字符串 是字符串中 连续 的 非空 字符序列。

这道题与昨天的 3258.统计满足K约束的子字符串数量I 相比多了一个查询数组，并且字符串的长度也来到了 10^5，返回结果是 long[]，暴力枚举会超时。

滑动窗口的时间复杂度为 O(n)，不可能对每一次查询都重新滑动一遍。显然需要在滑动的过程中记录下查询的结果。每次滑动我们可以得到一个区间 [l, r]，这个区间的所有子数组是合法的。

使用一维数组记录这个区间，使用下标与值的映射，我们有两种选择：

• 记录的左端点的最大右端点，即 left[l] = r
• 记录的右端点的最小左端点，即 right[r] = l

对于查询区间 [ql, qr]，它与我们已知的合法区间存在两种关系，被包含或者部分相交。

• 如果是被包含的关系，那么查询区间的所有子数组均合法，子数组个数为 (qr - ql + 1) * (qr - ql + 2) / 2。
• 如果是相交的关系，说明 ql < r，[ql, r] 的所有子数组是合法的，剩下的 [r + 1, qr] 的合法子数组如何求？可以在滑动过程中记录以每个元素为终点的合法子数组个数，以前缀和的形式保存。

这里区间的划分与结果集的构成是非常有讲究的。前缀和记录的是以元素为 终点 的合法子数组，如果我们在滑动的过程中根据查询区间终点匹配当前元素，即 qr == r，那么可能的情况为 ql >= l 查询区间被完全包含。如果 ql < l 则查询区间与合法区间相交。如果这时使用前缀和计算 [ql, l]，使用公式计算 [l, r] 就错了。因为后面区间使用公式计算的子数组并不包括以前面区间内的元素为起点的子数组，并且前缀和记录的子数组的起点可能在查询的左边界之外。而反过来前面使用公式计算，后面使用前缀和计算，被减去的那部分子数组个数中就包含了以 前面区间所有元素 为终点的子数组，也就是前面使用公式计算的子数组个数。我们不用担心后面通过前缀和计算的子数组的起点超出左边界，如果超出的话，一定是被包含的关系。

核心点在于想清楚这两部分集合的关系， [i, j] 的所有子数组包括了以 b ∈ [i, j] 为终点，a ∈ [i, b] 为起点的子数组。而使用前缀和相减计算的是所有以 c ∈ [m, n] 为终点的合法子数组，起点可以不在该区间，但是不会超出 ql。

代码

/**
 * @date 2024-11-13 0:25
 */
public class CountKConstraintSubstrings3261 {

    public long[] countKConstraintSubstrings_v1(String s, int k, int[][] queries) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] cnt = new int[2];
        long[] res = new long[queries.length];
        long[] prefix = new long[n + 1];
        int[] right = new int[n];
        Arrays.fill(right, n);
        int l = 0;
        for (int i = 0; i < n; i++) {
            cnt[chars[i] - '0']++;
            while (l <= i && cnt[0] > k && cnt[1] > k) {
                right[l] = i;
                cnt[chars[l++] - '0']--;
            }
            prefix[i + 1] += prefix[i] + i - l + 1;
        }
        for (int i = 0; i < queries.length; i++) {
            int ql = queries[i][0];
            int qr = queries[i][1];
            int r = Math.min(right[ql], qr + 1);
            res[i] = (r - ql + 1L) * (r - ql) / 2 + prefix[qr + 1] - prefix[r];

        }
        return res;
    }

}

性能

目标

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

示例 1：

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。

说明：

• 2 <= n <= 10^6
• 1 <= cuts.length <= min(n - 1, 100)
• 1 <= cuts[i] <= n - 1
• cuts 数组中的所有整数都 互不相同

提示：

• Build a dp array where dp[i][j] is the minimum cost to achieve all the cuts between i and j.
• When you try to get the minimum cost between i and j, try all possible cuts k between them, dp[i][j] = min(dp[i][k] + dp[k][j]) + (j - i) for all possible cuts k between them.

思路

有一个长度为 n 的木棍，刻度从 0 ~ n，有一个整数数组 cuts，cuts[i] 表示需要在刻度 i 处进行切割，切割的成本为该刻度所在棍子的长度，求切割棍子的最小成本。

许多算法书上引入动态规划经常举的一个例子是钢条切割问题。已知特定长度钢条的价值，问怎样切可以使价值最大。而本题是给出必须要切的点，问按照什么顺序切成本最小。

定义 dp[i][j] 表示完成 (i, j) 之间所有切割点所需要的最小成本，dp[0][n] 就是答案。状态转移方程为 dp[i][j] = min(dp[i][k] + dp[k][j]) + j - i)。根据定义 dp 数组应该初始化为 0，因为无法切割时成本为 0。

但是由于切割点的范围太大 2 ~ 10^6，如果直接定义的话会超出内存限制。可以先将切割点排序，定义 i，j 为切点的下标，切点个数 m 最大为 100，时间复杂度为 O(m^3)。

考虑到切点本身不包含木棍的两个端点 0 和 n，我们定义端点 endpoint 数组，将这两个端点加进来，dp[0][m - 1] 即为所求。状态转移方程为 dp[i][j] = min(dp[i][k] + dp[k][j]) + endpoint[j] - endpoint[i]。

特别需要注意的是 dp 数组的遍历的顺序。当我们计算 dp[i][j] 时需要已经计算出 dp[k][j]，枚举起点 i 应该倒序，因为 k > i，同理还需要计算出 dp[i][k]，枚举终点 j 应该正序，因为 k > y。枚举 k 正序倒序都可以。

枚举 i，j 的先后顺序也是可以交换的。

代码

/**
 * @date 2024-11-11 10:07
 */
public class MinCost1547 {

    public int minCost(int n, int[] cuts) {
        Arrays.sort(cuts);
        int m = cuts.length;
        int[] endpoint = new int[m + 2];
        System.arraycopy(cuts, 0, endpoint, 1, m);
        endpoint[m + 1] = n;

        m = endpoint.length;
        int[][] dp = new int[m][m];

        for (int i = m - 3; i >= 0; i--) {
            for (int j = i + 2; j < m; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    min = Math.min(dp[i][k] + dp[k][j], min);
                }
                dp[i][j] = min + endpoint[j] - endpoint[i];
            }
        }
        return dp[0][m - 1];
    }

}

性能

目标

给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。换言之，你需要选择一个子数组 nums[l..r] 满足 |k - (nums[l] OR nums[l + 1] ... OR nums[r])| 最小。

请你返回 最小 的绝对差值。

子数组 是数组中连续的 非空 元素序列。

示例 1：

输入：nums = [1,2,4,5], k = 3
输出：0
解释：
子数组 nums[0..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 3| = 0 。

示例 2：

输入：nums = [1,3,1,3], k = 2
输出：1
解释：
子数组 nums[1..1] 的按位 OR 运算值为 3 ，得到最小差值 |3 - 2| = 1 。

示例 3：

输入：nums = [1], k = 10
输出：9
解释：
只有一个子数组，按位 OR 运算值为 1 ，得到最小差值 |10 - 1| = 9 。

说明：

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

思路

寻找子数组使子数组元素按位或运算的值 or 尽可能地接近 k，即求 |k - or| 的最小值。

暴力求解的基本逻辑是，外层枚举右端点，内层从后向前枚举左端点，使用 nums[j] 保存 子数组 [j, i] 的或值，通过判断 (nums[j] | right) != nums[j] 决定 right 是否对或值有贡献，如果没有贡献，那么可以不再继续向前枚举左端点，因为前面的或值已经累加了后面的值，如果对子数组 [j, i] 的或值没有贡献，那么对前面的 [j - 1, i] 包含了 [j, i] 的或值更没有贡献。

代码

/**
 * @date 2024-10-09 8:59
 */
public class MinimumDifference3171 {

    public int minimumDifference_v1(int[] nums, int k) {
        int n = nums.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            int right = nums[i];
            for (int j = i - 1; j >= 0 && ((nums[j] | right) != nums[j]); j--) {
                nums[j] |= right;
                res = Math.min(res, Math.abs(nums[j] - k));
            }
            res = Math.min(res, Math.abs(right - k));
        }
        return res;
    }

}

性能

目标

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处，并且有 fueli 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

示例 1：

输入：target = 1, startFuel = 1, stations = []
输出：0
解释：可以在不加油的情况下到达目的地。

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]
输出：-1
解释：无法抵达目的地，甚至无法到达第一个加油站。

示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
输出：2
解释：
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后，从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠，所以返回 2 。

说明：

• 1 <= target, startFuel <= 10^9
• 0 <= stations.length <= 500
• 1 <= positioni < positioni+1 < target
• 1 <= fueli < 10^9

思路

已知汽车油耗为 1 英里/升，现在想要开车前往 target 英里外的目的地，出发时车中有 startFuel 升油，沿途有 stations.length 个加油站，stations[i][0] 表示加油站 i 距出发地的距离，stations[i][1] 表示加油站 i 的汽油总量。假设汽车油箱无限大，求到达目的地的最少加油次数，如果无法到达返回 -1。

可以将出发点、加油站、目的地画到数轴上，由于油耗为 1 英里/升，有多少升油就可以到达多远的距离。那么问题转化为从 n 个加油站中选取最少的个数，使油箱油量大于等于 target。要使选择的加油站最少，那么应该首选油量多的加油站，前提是能够抵达该加油站。我们可以使用大顶堆维护加油站油量，将能够抵达的加油站放入其中，然后将堆顶的油加入油箱，将新的能够抵达的加油站放入堆中，直到油箱中的油量大于等于 target。

代码

/**
 * @date 2024-10-07 21:09
 */
public class MinRefuelStops871 {

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        int n = stations.length;
        int i = 0;
        int res = 0;
        int fuel = startFuel;
        while (fuel < target) {
            while (i < n && fuel >= stations[i][0]) {
                q.offer(stations[i++][1]);
            }
            if (!q.isEmpty()) {
                fuel += q.poll();
                res++;
                if (fuel >= target) {
                    return res;
                }
            } else if (i == n || fuel < stations[i][0]) {
                // 没有剩余的加油站或者无法抵达
                return -1;
            }
        }
        return res;
    }

}

性能