shelterofly

目标

给你一个正整数 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;
    }

}

性能

目标

给你一个整数数组 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;
    }

}

性能