【周赛复盘】力扣第 86 场双周赛

1. 和相等的子数组

1）题目描述

给你一个下标从 0 开始的整数数组 nums ，判断是否存在 两个 长度为 2 的子数组且它们的 和 相等。注意，这两个子数组起始位置的下标必须 不相同 。

如果这样的子数组存在，请返回 true，否则返回 false 。

子数组 是一个数组中一段连续非空的元素组成的序列。

2）原题链接

LeetCode.6171. 和相等的子数组

3）思路解析

• $(1)$存下任意两个相邻元素的和，存入到set中，在遍历过程中如果发现有重复的，那么直接返回true，否则返回false。

4）模板代码

class Solution {
   public boolean findSubarrays(int[] arr) {
        Set<Long> set=new HashSet<>();
        int n=arr.length;
        for (int i = 0; i <n-1; i++) {
            long s=arr[i]+arr[i+1];
            if (set.contains(s)) return true;
            set.add(s);
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

5）算法与时间复杂度

  算法：哈希
  时间复杂度:$O(n)$。

2. 严格回文的数字

1）题目描述

如果一个整数 n 在 b 进制下（b 为 2 到 n - 2 之间的所有整数）对应的字符串 全部 都是 回文的 ，那么我们称这个数 n 是 严格回文 的。

给你一个整数 n ，如果 n 是 严格回文 的，请返回 true ，否则返回 false 。

如果一个字符串从前往后读和从后往前读完全相同，那么这个字符串是 回文的 。

2）原题链接

LeetCode.6172. 严格回文的数字

3）思路解析

• $(1)$Java中自带转进制的函数，我们直接暴力枚举判断即可。Integer.toString(a,b)将a转换为b进制。
• $(2)$数字 $4$ 在二进制下不是回文的。对于 $n\ge 5$，它们的 $(n-2)$ 进制表示都是 $12$，因此也都不是回文的。直接返回 false 即可

4）模板代码

class Solution {
     public boolean isStrictlyPalindromic(int n) {
        for (int i = 2; i <=n-2; i++) {
            String x=Integer.toString(n,i);
            if (!check(x)) return false;
        }
        return true;
    }
    static boolean check(String s){
        int l=0,r=s.length()-1;
        while (l<r){
            if (s.charAt(l)!=s.charAt(r)) return false;
            l++;r--;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

5）算法与时间复杂度

  算法：脑筋急转弯
  时间复杂度:$O(1)$。

3. 被列覆盖的最多行数

1）题目描述

给你一个下标从 0 开始的 m x n 二进制矩阵 mat 和一个整数 cols ，表示你需要选出的列数。

如果一行中，所有的 1 都被你选中的列所覆盖，那么我们称这一行 被覆盖 了。

请你返回在选择cols列的情况下，被覆盖 的行数 最大 为多少。

2）原题链接

LeetCode.6173. 被列覆盖的最多行数

3）思路解析

• $(1)$观察数据范围，发现n和m最大只有12，说明我们可以直接暴力枚举所有的情况，最多只有$2^{12}$种情况，我们可以二进制枚举，也可以使用dfs。

4）模板代码

二进制枚举

class Solution {
   int max=0;
    public int maximumRows(int[][] arr, int cols) {
       int n=arr.length;
       int m=arr[0].length;
        for (int i = 0; i <(1<<m); i++) {
            if (Integer.bitCount(i)!=cols) continue;
            int ans=0;
            for (int j = 0; j < n; j++) {
                boolean f=true;
                for (int k = 0; k < m; k++) {
                    int x=m-1-k;
                    if (arr[j][k]==1&&((i>>x)&1)!=1){
                        f=false;
                        break;
                    }
                }
                if (f)ans++;
            }
            max=Math.max(max,ans);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

dfs

class Solution {
    int n, m;
    int ans = 0;
    int x;

    public int maximumRows(int[][] arr, int cols) {
        n = arr.length;
        m = arr[0].length;
        this.x = cols;
        dfs(arr, new LinkedList<>(), 0);
        return ans;
    }

    void dfs(int[][] arr, List<Integer> list, int v) {
        if (list.size() == m) {
            if (v!=x) return;
            int res = 0;
            for (int i = 0; i < n; i++) {
                boolean f = true;
                for (int j = 0; j < m; j++) {
                    if (arr[i][j] == 1 && list.get(j) != 1) {
                        f = false;
                        break;
                    }
                }
                if (f) res++;
            }
            ans = Math.max(ans, res);
            return;
        }
        //如果选
        list.add(1);
        dfs(arr, list, v + 1);
        list.remove(list.size() - 1);
        //如果不选
        list.add(0);
        dfs(arr, list, v);
        list.remove(list.size() - 1);
    }
}
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
38
39
40

5）算法与时间复杂度

  算法：深度优先搜索 二进制枚举
  时间复杂度:$O(2^{12})$。

4.预算内的最多机器人数目

1）题目描述

你有 n 个机器人，给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ，两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间，花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。

运行 k 个机器人 总开销 是max(chargeTimes) + k * sum(runningCosts)，其中 max(chargeTimes) 是这 k个机器人中最大充电时间，sum(runningCosts) 是这 k 个机器人的运行时间之和。

请你返回在 不超过 budget 的前提下，你 最多 可以 连续 运行的机器人数目为多少。

2）原题链接

LeetCode.6143. 预算内的最多机器人数目

3）思路解析

• $(1)$要注意到我们选择的机器人，必须是连续的子数组，所以我们可以进行二分，二分选择的长度。
• $(2)$二分得到判断的区间长度后，我们需要获取这个窗口内的最大值以及总和，求最大值我们可以使用单调队列，求总和可以使用前缀和。
• $(3)$当然求区间最大值我们也可以使用st表以及线段树等数据结构，比赛时为了方便我粘贴了线段树的板子。

4）模板代码

class Solution {
    static int N=500010;
    static int[] a=new int[N];
    static Node[] tr=new Node[N*4];
    long[] s;
    int n;
    long ggg;
    public int maximumRobots(int[] c, int[] rr, long budget) {
        n=c.length;
        ggg=budget;
        for (int i = 1; i<=n; i++) {
            a[i]=c[i-1];
        }
        s=new long[n+10];
        for (int i = 1; i <=n; i++) {
            s[i]=s[i-1]+rr[i-1];
        }
        build(1,1,n);
        int l=0,r=n;
        while (l<r){
            int mid=l+r+1>>1;
            if (check(mid)) l=mid;
            else r=mid-1;
        }
        
        return r;
    }
    boolean check(int x){
        for (int i = 0; i+x-1<n; i++) {
            int r=i+x-1;
            //System.out.println((s[r+1]-s[i])*x+query(1,i+1,r+1));
             if ((s[r+1]-s[i])*x+query(1,i+1,r+1)<=ggg) return true;
        }
        return false;
    }
    static void build(int u,int l,int r){
        if (l==r){
            tr[u]=new Node(l,r,a[r]);
        }else{
            tr[u]=new Node(l,r,0);
            int mid=l+r>>1;
            build(u<<1,l,mid);
            build(u<<1|1,mid+1,r);
            pushup(u);
        }
    }
    static int query(int u,int l,int r){
        if (tr[u].l>=l&&tr[u].r<=r) return tr[u].max;
        else{
            int mid=tr[u].l+tr[u].r>>1;
            int max=-0x3f3f3f3f;
            if (l<=mid) max=query(u<<1,l,r);
            if (r>mid) max=Math.max(query(u<<1|1,l,r),max);
            return max;
        }
    }
    static void pushup(int u){
        tr[u].max=Math.max(tr[u<<1].max,tr[u<<1|1].max);
    }
    static class Node{
        int l,r,max;
        public Node(int l, int r, int max) {
            this.l = l;
            this.r = r;
            this.max = max;
        }
        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

5）算法与时间复杂度

  算法：二分 前缀和 线段树 单调队列
  时间复杂度:$O(nlogn)$。