标签： medium

目标

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个数组的 能量值 定义为：

• 如果 所有 元素都是依次 连续 且 上升 的，那么能量值为 最大 的元素。
• 否则为 -1 。

你需要求出 nums 中所有长度为 k 的 子数组 的能量值。

请你返回一个长度为 n - k + 1 的整数数组 results ，其中 results[i] 是子数组 nums[i..(i + k - 1)] 的能量值。

示例 1：

输入：nums = [1,2,3,4,3,2,5], k = 3
输出：[3,4,-1,-1,-1]
解释：
nums 中总共有 5 个长度为 3 的子数组：
[1, 2, 3] 中最大元素为 3 。
[2, 3, 4] 中最大元素为 4 。
[3, 4, 3] 中元素 不是 连续的。
[4, 3, 2] 中元素 不是 上升的。
[3, 2, 5] 中元素 不是 连续的。

示例 2：

输入：nums = [2,2,2,2,2], k = 4
输出：[-1,-1]

示例 3：

输入：nums = [3,2,3,2,3,2], k = 2
输出：[-1,3,-1,3,-1]

说明：

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

思路

有一个整数数组 nums，如果其子数组中的元素是连续且递增的，即公差为 1 的数列，定义子数组的能量值为子数组的最大元素，否则能量为 -1。返回所有长度为 k 的子数组的能量值。

显然需要使用滑动窗口，关键在于元素移入移出后如何判断是否连续且递增。我们可以使用队列记录不满足规则元素的 前一个 元素下标。当元素移入窗口时，判断元素与前一个元素是否满足规则，不满足则将前一个元素下标加入队列。窗口滑动时，先判断被移出的元素下标是否与队首相同，如果相同将队首元素删除。最后判断队列是否为空，如果为空则能量为新加入的元素，否则为 -1。

官网题解使用一个计数器记录连续递增的元素个数，初始化结果数组元素为 -1，当计数器大于等于 k 时，记录 i - k + 1 位置上的能量值为当前元素，否则将计数器重置为 1。

代码

/**
 * @date 2024-11-06 5:50
 */
public class ResultsArray3254 {

    public int[] resultsArray(int[] nums, int k) {
        int n = nums.length;
        if (k == 1) {
            return nums;
        }
        int[] res = new int[n - k + 1];
        Queue<Integer> q = new ArrayDeque<>();
        int l = 0, i = 0;
        for (int r = 1; r < n; r++) {
            int prev = r - 1;
            if (nums[r] - nums[prev] != 1) {
                q.offer(prev);
            }
            if (r - l + 1 > k) {
                if (!q.isEmpty() && l == q.peek()) {
                    q.poll();
                }
                l++;
            }
            if (r - l + 1 == k) {
                if (q.isEmpty()) {
                    res[i++] = nums[r];
                } else {
                    res[i++] = -1;
                }
            }
        }
        return res;
    }

}

性能

目标

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来 最大化 你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的 最大 总强化能量。

注意 你可以选择从饮用任意一种能量饮料开始。

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：
要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
输出：7
解释：
第一个小时饮用能量饮料 A。
切换到能量饮料 B ，在第二个小时无法获得强化能量。
第三个小时饮用能量饮料 B ，并获得强化能量。

说明：

• n == energyDrinkA.length == energyDrinkB.length
• 3 <= n <= 10^5
• 1 <= energyDrinkA[i], energyDrinkB[i] <= 10^5

思路

有 energyDrinkA 和 energyDrinkB 两个数组，表示饮料 A 和 B 在第 i 小时可以提供的能量，现在需要每一小时饮用饮料 A 或 B 来获取能量，可以暂停一小时来切换饮料，求能够获得的最大能量。

定义 dp[i][j] 表示第 i 小时选择饮料 j 所能获取的最大能量，假设 j = 0 表示饮料 A，j = 1 表示饮料 B，那么状态转移方程为 dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0] + energyDrinkA)，dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + energyDrinkB)，最终返回 Math.max(dp[n - 1][0], dp[n - 1][1])。初始条件 dp[0][0] = energyDrinkA[0] dp[0][1] = energyDrinkA[1]。

由于只与前面的状态有关，因此可以进行存储优化，使用两个变量保存前一个小时饮用 A B 的最大能量即可。

代码

/**
 * @date 2024-11-01 0:37
 */
public class MaxEnergyBoost3259 {

    public long maxEnergyBoost_v1(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.length;
        long prevA = energyDrinkA[0];
        long prevB = energyDrinkB[0];
        for (int i = 1; i < n; i++) {
            long curA = Math.max(prevB,  prevA + energyDrinkA[i]);
            long curB = Math.max(prevA,  prevB + energyDrinkB[i]);
            prevA = curA;
            prevB = curB;
        }
        return Math.max(prevA, prevB);
    }

}

性能

目标

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的 子字符串 中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

示例 1：

输入： n = 3
输出： ["010","011","101","110","111"]
解释：
长度为 3 的有效字符串有："010"、"011"、"101"、"110" 和 "111"。

示例 2：

输入： n = 1
输出： ["0","1"]
解释：
长度为 1 的有效字符串有："0" 和 "1"。

说明：

• 1 <= n <= 18

思路

示例2让人困惑，字符串 0 并没有长度为 2 的子字符串，更别提包含至少一个 1 了，但它是有效字符串。

还是按照题目名称来做吧，生成长度为 n，不含相邻零的二进制字符串。直接回溯即可。

官网题解还提出了一种位运算的解法，主要思想就是将 二进制字符串 视为 数字的二进制表示，问题转化为 0 ~ 2^n - 1 的数字中不含相邻零的个数。由于超出 n 的位数不在我们的考虑范围，为了简化处理，可以直接将数字的低 n 位取反，x ^ ((1 << n) - 1))。1 << n 从 0 开始计向左移 n 位，再减 1，得到低 n 位全为 1 的数字，对它取异或相当于低 n 位取反。问题转换为 数字中是否存在连续的 1。针对每一个数字，无需遍历每一位，直接使用 x & (x >> 1) 是否等于 0 来判断是否含有相邻的 1。相当于将每一位与它前面的位相与，如果存在相邻的 1 就会存在某个位相与的结果为 1 使最终结果不为 0。

代码

/**
 * @date 2024-10-29 0:23
 */
public class ValidStrings3211 {
    List<String> res;
    char[] path;
    int n;

    public List<String> validStrings(int n) {
        res = new ArrayList<>();
        path = new char[n];
        this.n = n;
        backTracing('1', 0);
        return res;
    }

    public void backTracing(char prev, int i) {
        if (i == n) {
            res.add(new String(path));
            return;
        }
        path[i] = '1';
        int next = i + 1;
        backTracing('1', next);
        if (prev != '0') {
            path[i] = '0';
            backTracing('0', next);
        }
    }
}

性能

目标

给你一个整数数组 hours，表示以 小时 为单位的时间，返回一个整数，表示满足 i < j 且 hours[i] + hours[j] 构成 整天 的下标对 i, j 的数目。

整天 定义为时间持续时间是 24 小时的 整数倍 。

例如，1 天是 24 小时，2 天是 48 小时，3 天是 72 小时，以此类推。

示例 1：

输入： hours = [12,12,30,24,24]
输出： 2
解释：
构成整天的下标对分别是 (0, 1) 和 (3, 4)。

示例 2：

输入： hours = [72,48,24,3]
输出： 3
解释：
构成整天的下标对分别是 (0, 1)、(0, 2) 和 (1, 2)。

说明：

• 1 <= hours.length <= 5 * 10^5
• 1 <= hours[i] <= 10^9

思路

有一个整数数组 hours，返回 hours[i] + hours[j] % 24 == 0，i < j 的下标对的个数。

与昨天的题目 3184.构成整天的下标对数目I 相比，数据规模从 100 变成了 5 * 10^5。枚举下标对的时间复杂度为 O(C(n,2))，即 O(n^2)，肯定会超时。

题目并不要求输出具体的下标对，只需要计数即可。当枚举右端点时，如果可以直接获取到已访问过的元素中，能够与当前元素组成合法下标对的元素个数，那么整体的时间复杂度可以降为 O(n)。定义 cnt[m] 表示已访问过的元素中对 24 取余后值为 m 的元素个数。当枚举到元素 i 时，只需累加 cnt[24 - nums[i] % 24] 即可。

代码

/**
 * @date 2024-10-23 10:16
 */
public class CountCompleteDayPairs3185 {

    public long countCompleteDayPairs_v2(int[] hours) {
        long res = 0L;
        int[] cnt = new int[24];
        int zeroCnt = 0;
        for (int hour : hours) {
            int m = hour % 24;
            if (m == 0) {
                res += zeroCnt;
                zeroCnt++;
            } else {
                res += cnt[24 - m];
                cnt[m]++;
            }
        }
        return res;
    }

}

性能