LeetCode第 86 场双周赛

前言

之后会参与leetcode周赛、双周赛，希望自己能够坚持下来，并以此来督促检验、提升自己的算法能力，加油！

第86场双周赛情况

地址：第86场双周赛

战绩：

第三题案例还差两个过了：

最后的情况：真太菜了

目前竞赛分数：

题目复盘+题解

题1：6171. 和相等的子数组【easy】

题目链接：6171. 和相等的子数组

题目内容：

给你一个下标从 0 开始的整数数组 nums ，判断是否存在 两个 长度为 2 的子数组且它们的 和 相等。注意，这两个子数组起始位置的下标必须 不相同 。
如果这样的子数组存在，请返回 true，否则返回 false 。
子数组 是一个数组中一段连续非空的元素组成的序列。

示例 1：
输入：nums = [4,2,4]
输出：true
解释：元素为 [4,2] 和 [2,4] 的子数组有相同的和 6 。

示例 2：
输入：nums = [1,2,3,4,5]
输出：false
解释：没有长度为 2 的两个子数组和相等。

示例 3：
输入：nums = [0,0,0]
输出：true
解释：子数组 [nums[0],nums[1]] 和 [nums[1],nums[2]] 的和相等，都为 0 。
注意即使子数组的元素相同，这两个子数组也视为不相同的子数组，因为它们在原数组中的起始位置不同。

提示：
2 <= nums.length <= 1000
-109 <= nums[i] <= 109
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

复盘：当时题目没有读清楚，其实就是连续子数组两个 + 两数和相等不同情况，最终就是求方案数。我耗费了一大堆时间就是因为题目没有理解清楚。

思路：

1、利用哈希

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

class Solution {
    
    //连续的子数组
    public boolean findSubarrays(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < nums.length; i++) {
            int val = nums[i - 1] + nums[i];
            if (set.contains(val)) {
                return true;
            }
            set.add(val);
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题2：6172. 严格回文的数字【medium】

题目链接：6172. 严格回文的数字

题目内容：

如果一个整数 n 在 b 进制下（b 为 2 到 n - 2 之间的所有整数）对应的字符串 全部 都是 回文的 ，那么我们称这个数 n 是 严格回文 的。
给你一个整数 n ，如果 n 是 严格回文 的，请返回 true ，否则返回 false 。
如果一个字符串从前往后读和从后往前读完全相同，那么这个字符串是 回文的 。

示例 1：
输入：n = 9
输出：false
解释：在 2 进制下：9 = 1001 ，是回文的。
在 3 进制下：9 = 100 ，不是回文的。
所以，9 不是严格回文数字，我们返回 false 。
注意在 4, 5, 6 和 7 进制下，n = 9 都不是回文的。

示例 2：
输入：n = 4
输出：false
解释：我们只考虑 2 进制：4 = 100 ，不是回文的。
所以我们返回 false 。
 
提示：
4 <= n <= 105
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

思路：

1、左右拆分

复杂度分析：时间复杂度O(n)；空间复杂度O(1)

class Solution {
    
    //n表示[2, n - 2]进制，判断是否是回文
    public boolean isStrictlyPalindromic(int n) {
        //i表示几位进制数
        for (int i = 2; i < n - 1; i++) {
            if (n % i == 0) {
                return false;
            }
            //拆成左右两边
            int leftVal = n / 2;
            int rightVal = n - leftVal;
            if (leftVal % i == 0 || rightVal % i == 0) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2、数学证明（推荐）

参考：数学证明-灵茶山艾府

思路：

根据题目得知：2 <= b <= n-2，b表示的是进制数，而n表示的是某个数字，对应范围n给出了4 <= n <= 105
对于在任意进制b的情况下我们都可以使用一个公式来表示：n = q*b + r，并且其中的0 <= r < b
我们来列举一些案例：
n = 4
  b = 2   =>  100 （不成立）

n = 5
  b = 2   =>  101 （成立）
  b = 3   =>  12 （不成立）

n = 6
  b = 2   =>  110（不成立）
  b = 3   =>  20（不成立）
  b = 4   =>  12（不成立）

n = 7
  b = 2   =>  111（成立）
  b = 3   =>  21（不成立）
  b = 4   =>  13（不成立）
  b = 5   =>  12（不成立）

n = 8
  b = 2   =>  1000（不成立）
  b = 3   =>  22（不成立）
  b = 4   =>  20（不成立）
  b = 5   =>  13（不成立）
  b = 6   =>  12（不成立）
  
你发现了什么，当n>4的时候，当b进制为n-2时，每个数的b进制数都是12，那么可以得出结论
当n > 4时，b=n-2时结果值为12，不是回文数
当n = 4时，不是回文数

由此，我们最后无需进行进制运算，最后直接返回false即可。
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
32
33

复杂度分析：时间复杂度O(1)；空间复杂度O(1)

class Solution {
    public boolean isStrictlyPalindromic(int n) {
        return false;
    }
}
1
2
3
4
5

题3：6173. 被列覆盖的最多行数【medium】

题目链接：6173. 被列覆盖的最多行数

题目内容：

给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。
如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。
请你返回在选择 cols 列的情况下，被覆盖 的行数 最大 为多少。
1
2
3

复盘：在调试过程中，我为了过一个例子，竟然加了一个校验条件，导致我最后两个案例没过，其实最后的全排列函数中我的代码是没有问题的，之后再进行调试时不能乱加一些无意义的校验代码，说多了都是累啊，本来第三题也能过的！

思路：

1、全排列+哈希表+回溯

复杂度分析：时间复杂度O(n!*m*n)，空间复杂度O(n!)

class Solution {
    
    public int maximumRows(int[][] mat, int cols) {
        if (mat.length == cols) {
            return cols;
        }
        quanpailie(mat, cols, 0, new HashSet<>());
        return max;
    }
    
    private int max = -1;
    
    //res存储的是对应的列方案
    public void quanpailie(int[][] mat, int cols, int col, Set<Integer> res) {
if (res.size() == cols) {
            int num = 0;
            //实际来进行处理操作
            for (int i = 0; i < mat.length; i++) {
                boolean flag = true;
                for (int j = 0; j < mat[0].length; j++) {
                    if (!res.contains(j) && mat[i][j] == 1) {
                        flag = false;
                        break;
                    }
                }
                if (flag) num++;
            }
            if (num > max) max = num;
            return;
        }
        for (int i = col; i < mat[0].length; i++) {
            res.add(i);
            quanpailie(mat, cols, i + 1, res);
            res.remove(i);
        }
    }
}
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
32
33
34
35
36
37

题4：预算内的最多机器人数目【hard】

题目链接：6143. 预算内的最多机器人数目

题目内容：

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ，其中 max(chargeTimes) 是这 k 个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

示例 1：
输入：chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出：3
解释：
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人，可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ，小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人，所以我们返回 3 。

示例 2：
输入：chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出：0
解释：即使运行任何一个单个机器人，还是会超出 budget，所以我们返回 0 。

提示：
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

思路：

1、大顶堆+双指针

复杂度分析：时间复杂度O(n)；空间复杂度O(n)

class Solution {

    //chargeTimes  充电时间
    //runningCosts 运行时间
    //开销  max(chargeTimes) + k * sum(runningCosts)
    //budget 运算
    //考虑问题：连续n个数中的最大值（优先队列，大顶堆） +  双指针
    public int maximumRobots(int[] chargeTimes, int[] runningCosts, long budget) {
        int ans = 0;
        long cost = 0, sum = 0;
        int n = chargeTimes.length;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1, o2)->o2 - o1);
        for (int l = 0, r = 0; r < n; r++) {
            while (cost > budget) {
                //减去当前的
                sum -= runningCosts[l];
                maxHeap.remove(chargeTimes[l]);
                l++;
                if (!maxHeap.isEmpty()) {
                    cost = maxHeap.peek() + sum * (r - l + 1);
                }else {
                    cost = 0;
                }
            }
            //重新计算新的值
            sum += runningCosts[r];
            maxHeap.add(chargeTimes[r]);
            cost = maxHeap.peek() + sum * (r - l + 1);
            if (cost <= budget) {
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}
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
32
33
34
35

参考资料

[1]. 【力扣双周赛 86】位运算黑科技 | 单调队列 | LeetCode 算法刷题