admin – 第 23 页 – shelterofly

目标

给你一个二进制数组 nums 。

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

选择数组中任意连续 3 个元素，并将它们全部反转。

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

请你返回将 nums 中所有元素变为 1 的最少操作次数。如果无法全部变成 1 ，返回 -1 。

示例 1：

输入：nums = [0,1,1,1,0,0]
输出：3
解释：
我们可以执行以下操作：
选择下标为 0 ，1 和 2 的元素并反转，得到 nums = [1,0,0,1,0,0] 。
选择下标为 1 ，2 和 3 的元素并反转，得到 nums = [1,1,1,0,0,0] 。
选择下标为 3 ，4 和 5 的元素并反转，得到 nums = [1,1,1,1,1,1] 。

示例 2：

输入：nums = [0,1,1,1]
输出：-1
解释：
无法将所有元素都变为 1 。

说明：

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

思路

有一个二进制数组 nums，每一次操作可以将其中连续的三个元素取反，求将其中的所有元素置为 1 的最少操作次数，如果无法将所有元素都变为 1，返回 -1。

直觉告诉我遇到 0 就执行一次操作就是最少的操作次数。

如果 nums[0] == 0，将它变成 1 的唯一方法是对其进行操作，即反转 nums[0] nums[1] nums[2]。将同样的逻辑应用于接下来的 1 ~ n - 1，换句话说 结果是注定的，最少操作方式也是唯一的。

代码


/**
 * @date 2024-10-18 8:53
 */
public class MinOperations3191 {

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

}

性能

目标

给你一个整数 n 和一个二维数组 requirements ，其中 requirements[i] = [endi, cnti] 表示这个要求中的末尾下标和逆序对的数目。

整数数组 nums 中一个下标对 (i, j) 如果满足以下条件，那么它们被称为一个逆序对：

i < j 且 nums[i] > nums[j]

请你返回 [0, 1, 2, ..., n - 1] 的排列 perm 的数目，满足对所有的 requirements[i] 都有 perm[0..endi] 恰好有 cnti 个逆序对。

由于答案可能会很大，将它对 10^9 + 7 取余后返回。

示例 1：

输入：n = 3, requirements = [[2,2],[0,0]]
输出：2
解释：
两个排列为：
[2, 0, 1]
前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2] 的逆序对数目为 0 个。
[1, 2, 0]
前缀 [1, 2, 0] 的逆序对为 (0, 2) 和 (1, 2) 。
前缀 [1] 的逆序对数目为 0 个。

示例 2：

输入：n = 3, requirements = [[2,2],[1,1],[0,0]]
输出：1
解释：
唯一满足要求的排列是 [2, 0, 1] ：
前缀 [2, 0, 1] 的逆序对为 (0, 1) 和 (0, 2) 。
前缀 [2, 0] 的逆序对为 (0, 1) 。
前缀 [2] 的逆序对数目为 0 。

示例 3：

输入：n = 2, requirements = [[0,0],[1,0]]
输出：1
解释：
唯一满足要求的排列为 [0, 1] ：
前缀 [0] 的逆序对数目为 0 。
前缀 [0, 1] 的逆序对为 (0, 1) 。

说明：

2 <= n <= 300
1 <= requirements.length <= n
requirements[i] = [endi, cnti]
0 <= endi <= n - 1
0 <= cnti <= 400
输入保证至少有一个 i 满足 endi == n - 1 。
输入保证所有的 endi 互不相同。

思路

数组 nums 的每一个子数组 [0, endi] 有一个 cnti，求这些子数组的排列中逆序对个数恰好为对应的 cnti 的个数。注意同一个排列需要满足所有的要求。

// todo

代码

性能

目标

你有一个初始为空的浮点数数组 averages。另给你一个包含 n 个整数的数组 nums，其中 n 为偶数。

你需要重复以下步骤 n / 2 次：

从 nums 中移除最小的元素 minElement 和最大的元素 maxElement。
将 (minElement + maxElement) / 2 加入到 averages 中。

返回 averages 中的最小元素。

示例 1：

输入： nums = [7,8,3,4,15,13,4,1]
输出： 5.5
解释：
步骤 nums               averages
0   [7,8,3,4,15,13,4,1] []
1   [7,8,3,4,13,4]      [8]
2   [7,8,4,4]           [8,8]
3   [7,4]               [8,8,6]
4   []                  [8,8,6,5.5]
返回 averages 中最小的元素，即 5.5。

示例 2：

输入： nums = [1,9,8,3,10,5]
输出： 5.5
解释：
步骤 nums           averages
0   [1,9,8,3,10,5]  []
1   [9,8,3,5]       [5.5]
2   [8,5]           [5.5,6]
3   []              [5.5,6,6.5]

示例 3：

输入： nums = [1,2,3,7,8,9]
输出： 5.0
解释：
步骤 nums           averages
0   [1,2,3,7,8,9]   []
1   [2,3,7,8]       [5]
2   [3,7]           [5,5]
3   []              [5,5,5]

说明：

2 <= n == nums.length <= 50
n 为偶数。
1 <= nums[i] <= 50

思路

有一个数组 nums，元素个数为偶数，取其最大值与最小值的平均数加入 averages 浮点数数组，并将其从 nums 中删除。求 averages 数组的最小值。

先将数组 nums 排序，然后取前后两个元素计算平均数，取最小值即可。

代码


/**
 * @date 2024-10-16 8:49
 */
public class MinimumAverage3194 {

    public double minimumAverage(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int end = n / 2;
        n = n - 1;
        double res = Double.MAX_VALUE;
        for (int i = 0; i < end; i++) {
            res = Math.min(res, (nums[i] + nums[n - i]) / 2.0);
        }
        return res;
    }
}

性能

目标

给你两个整数 red 和 blue，分别表示红色球和蓝色球的数量。你需要使用这些球来组成一个三角形，满足第 1 行有 1 个球，第 2 行有 2 个球，第 3 行有 3 个球，依此类推。

每一行的球必须是相同颜色，且相邻行的颜色必须不同。

返回可以实现的三角形的最大高度。

示例 1：

输入： red = 2, blue = 4
输出： 3
解释：
上图显示了唯一可能的排列方式。

示例 2：

输入： red = 2, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

示例 3：

输入： red = 1, blue = 1
输出： 1

示例 4：

输入： red = 10, blue = 1
输出： 2
解释：
上图显示了唯一可能的排列方式。

说明：

1 <= red, blue <= 100

思路

有红球 red 个，蓝球 blue 个，使用这两种球组成三角形，要求每一行只能由同一种颜色的球组成，且相邻行球的颜色不同，问三角形的最大高度。

三角形第 i 行球的个数为 i，奇数行的总个数为 1 + 3 + 5 + …… 偶数行的总个数为 2 + 4 + 6 + ……，根据等差数列求和公式，奇数行所需球的总个数为 oddRowCnt^2，偶数行所需球的总个数为 evenRowCnt^2 + evenRowCnt。

假设 red 放在奇数行，代入可得 redOddRowCnt = sqrt(red)，如果放在偶数行，则 redEvenRowCnt = (sqrt(1 + 4 * red) - 1) / 2。同理可求出 blueOddRowCnt blueEvenRowCnt。

接下来分两种情况讨论：

红色球放第一行：如果 |redOddRowCnt - blueEvenRowCnt| > 1，取 Math.min(redOddRowCnt, blueEvenRowCnt) * 2 + 1，否则取 Math.min(redOddRowCnt, blueEvenRowCnt) * 2。
蓝色球放第一行：如果 |blueOddRowCnt - redEvenRowCnt| > 1，取 Math.min(blueOddRowCnt, redEvenRowCnt) * 2 + 1，否则取 Math.min(blueOddRowCnt, redEvenRowCnt) * 2。

取上面两种情况的最大值即可。

代码


/**
 * @date 2024-10-15 9:25
 */
public class MaxHeightOfTriangle3200 {

    public int maxHeightOfTriangle(int red, int blue) {
        int redOddRowCnt = (int) Math.sqrt(red);
        int redEvenRowCnt = (int) ((Math.sqrt(1 + 4 * red) - 1) / 2);
        int blueOddRowCnt = (int) Math.sqrt(blue);
        int blueEvenRowCnt = (int) ((Math.sqrt(1 + 4 * blue) - 1) / 2);
        int r, b;
        if (redOddRowCnt - blueEvenRowCnt >= 1) {
            r = 2 * blueEvenRowCnt + 1;
        } else {
            r = 2 * redOddRowCnt;
        }
        if (blueOddRowCnt - redEvenRowCnt >= 1) {
            b = 2 * redEvenRowCnt + 1;
        } else {
            b = 2 * blueOddRowCnt;
        }
        return Math.max(r, b);
    }

}

性能

目标

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

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

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

示例 1：

输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

示例 2：

输入：k = 2, n = 6
输出：3

示例 3：

输入：k = 3, n = 14
输出：4

提示：

1 <= k <= 100
1 <= n <= 10^4

思路

参考1884.鸡蛋掉落-两枚鸡蛋，这次是 k 枚鸡蛋。

//todo

代码

性能

目标

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

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

请你计算并返回要确定 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;
    }
}

性能

目标

给你一个数组 nums ，数组中的数字要么出现一次，要么出现两次。

请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。

示例 1：

输入：nums = [1,2,1,3]
输出：1
解释：
nums 中唯一出现过两次的数字是 1 。

示例 2：

输入：nums = [1,2,3]
输出：0
解释：
nums 中没有数字出现两次。

示例 3：

输入：nums = [1,2,2,1]
输出：3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3 。

说明：

1 <= nums.length <= 50
1 <= nums[i] <= 50
nums 中每个数字要么出现过一次，要么出现过两次。

思路

有一个数组 nums，其中的元素要么出现一次，要么出现两次。求出现两次的元素的异或值，如果没有则返回 0。

由于 nums[i] <= 50，可以使用数组记录元素是否出现过，如果它第二次出现则计算异或值。

网友题解则使用了 long 型变量作为 bitmap 标识是否已经出现过。空间复杂度降为 O(1)。

代码


/**
 * @date 2024-10-12 8:46
 */
public class DuplicateNumbersXOR3158 {

    public int duplicateNumbersXOR(int[] nums) {
        // nums[i] <= 50
        boolean[] seen = new boolean[51];
        int res = 0;
        for (int num : nums) {
            if (seen[num]) {
                res ^= num;
            } else {
                seen[num] = true;
            }
        }
        return res;
    }
}

性能

目标

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回优质数对的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。

说明：

1 <= n, m <= 10^5
1 <= nums1[i], nums2[j] <= 10^6
1 <= k <= 10^3

思路

这与昨天 3162.优质数对的总数I 的区别是数据范围变大了，暴力解法不可行。

枚举因子的时间复杂度为 O(n * sqrt(max1/k) + m)，代入计算 10^5 * 10^3 + 10^5 大约 10^8，耗时560ms。

枚举倍数的时间复杂度为 O(n + m + max1/k * log(m))，10^5 + 10^5 + 10^6 * ln(10^5) ≈ 10^5 + 10^5 + 10^6 * 11.51，10^7，耗时 88ms。

代码


/**
 * @date 2024-10-11 8:40
 */
public class NumberOfPairs3164 {

    /**
     * 枚举因子 560ms
     */
    public long numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> factorCnt = new HashMap<>();
        for (int num : nums1) {
            if (num % k != 0) {
                continue;
            }
            num /= k;
            for (int i = 1; i * i <= num; i++) {
                if (num % i != 0) {
                    continue;
                }
                factorCnt.merge(i, 1, Integer::sum);
                if (i * i < num) {
                    factorCnt.merge(num / i, 1, Integer::sum);
                }
            }
        }
        long res = 0L;
        for (int num : nums2) {
            res += factorCnt.getOrDefault(num, 0);
        }
        return res;
    }

    /**
     * 枚举倍数 88ms
     */
    public long numberOfPairs(int[] nums1, int[] nums2, int k) {
        Map<Integer, Integer> map1 = new HashMap<>(nums1.length);
        Map<Integer, Integer> map2 = new HashMap<>(nums2.length);
        int max1 = 0;
        for (int num : nums1) {
            map1.merge(num, 1, Integer::sum);
            max1 = Math.max(max1, num);
        }
        for (int num : nums2) {
            map2.merge(num, 1, Integer::sum);
        }
        long res = 0L;
        for (int num : map2.keySet()) {
            int multiple = num * k;
            for (int i = multiple; i <= max1; i += multiple) {
                if (map1.containsKey(i)) {
                    res += (long) map1.get(i) * map2.get(num);
                }
            }
        }
        return res;
    }

}

性能

目标

给你两个整数数组 nums1 和 nums2，长度分别为 n 和 m。同时给你一个正整数 k。

如果 nums1[i] 可以被 nums2[j] * k 整除，则称数对 (i, j) 为优质数对（0 <= i <= n - 1, 0 <= j <= m - 1）。

返回优质数对的总数。

示例 1：

输入：nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出：5
解释：
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。

示例 2：

输入：nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出：2
解释：
2个优质数对分别是 (3, 0) 和 (3, 1)。

说明：

1 <= n, m <= 50
1 <= nums1[i], nums2[j] <= 50
1 <= k <= 50

思路

有两个数组 nums1 nums2，计算满足 nums1[i] % (nums2[j] * k) == 0 的数对 (i, j) 的个数。

数据量不大直接枚举即可。可以优化的点是提前判断 nums[i] 能否整除 k，如果不能，则必然也无法整除 nums2[j] * k，省去了内部循环乘以 k 的计算。

官网题解的非暴力做法是使用两个哈希表 map1 map2 分别统计 nums1 nums2 中元素出现的次数，同时找出 nums1 中的最大值 max1，然后枚举 map2 的 keyset，内层循环初值与步长为 nums2[j] * k，判断倍数是否在 map1 中，直到 倍数 <= max1。这样做的好处是寻找数对的时间复杂度由原来的 O(mn) 变成了 O(n + m + max1/k * log(m))。

这里的 log(max2) 是一个近似的估计，针对每一个外层循环的值 a，内层循环的次数为 max1 / (a * k)，假设 nums2 的元素值为 1 2 …… max2，那么总的循环次数为 (max1/k)Σ(1/a) 这是调和级数的形式，即 1 + 1/2 + 1/3 + …… + 1/max2 + ……，调和级数的部分和 Hn 近似为 ln(max2)，这里 max2 其实是 nums2 的个数 m。当 nums2 中的元素都是 1 时，map2.keySet 中的元素个数也为 1，进化为 O(n + m + max1/k)，当 nums2 中的元素都是 max2 时，进化为 O(n + m + max1/(max2 * k))。

代码


/**
 * @date 2024-10-10 8:56
 */
public class NumberOfPairs3162 {

    public int numberOfPairs_v1(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] % k != 0) {
                continue;
            }
            int tmp = nums1[i] / k;
            for (int j = 0; j < nums2.length; j++) {
                if (tmp % nums2[j] == 0) {
                    res++;
                }
            }
        }
        return res;
    }

    public int numberOfPairs(int[] nums1, int[] nums2, int k) {
        int res = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                if (nums1[i] % (nums2[j] * k) == 0){
                    res++;
                }
            }
        }
        return res;
    }

}

性能

3171.找到按位或最接近K的子数组

目标

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

}

2025 年 5 月
一	二	三	四	五	六	日
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31