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

柔情只为你懂 2023-09-28 23:01 5阅读 0赞

#### 目录 ####

*  1. 和相等的子数组
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  2. 严格回文的数字
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  3. 被列覆盖的最多行数
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度
 *  4.预算内的最多机器人数目
 *   *  1）题目描述
     *  2）原题链接
     *  3）思路解析
     *  4）模板代码
     *  5）算法与时间复杂度

## 1. 和相等的子数组 ##

### 1）题目描述 ###

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

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

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

### 2）原题链接 ###

[LeetCode.6171. 和相等的子数组][LeetCode.6171.]

### 3）思路解析 ###

*   ( 1 ) (1) (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;
        }
    }

### 5）算法与时间复杂度 ###

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

## 2. 严格回文的数字 ##

### 1）题目描述 ###

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

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

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

### 2）原题链接 ###

[LeetCode.6172. 严格回文的数字][LeetCode.6172.]

### 3）思路解析 ###

*   ( 1 ) (1) (1)`Java`中自带转进制的函数，我们直接暴力枚举判断即可。`Integer.toString(a,b)`将`a`转换为`b`进制。
 *   ( 2 ) (2) (2)数字  4 4 4 在二进制下不是回文的。对于  n ≥ 5 n≥5 n≥5，它们的  ( n − 2 ) (n - 2) (n−2) 进制表示都是  12 12 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;
        }
    }

class Solution {
        
        public boolean isStrictlyPalindromic(int n) {
        
            return false;
        }
    }

### 5）算法与时间复杂度 ###

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

## 3. 被列覆盖的最多行数 ##

### 1）题目描述 ###

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

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

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

### 2）原题链接 ###

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

### 3）思路解析 ###

*   ( 1 ) (1) (1)观察数据范围，发现`n`和`m`最大只有`12`，说明我们可以直接暴力枚举所有的情况，最多只有 2 12 2^\{12\} 212种情况，我们可以二进制枚举，也可以使用`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;
        }
    }

**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);
        }
    }

### 5）算法与时间复杂度 ###

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

## 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. 预算内的最多机器人数目][LeetCode.6143.]

### 3）思路解析 ###

*   ( 1 ) (1) (1)要注意到我们选择的机器人，必须是连续的子数组，所以我们可以进行二分，二分选择的长度。
 *   ( 2 ) (2) (2)二分得到判断的区间长度后，我们需要获取这个窗口内的最大值以及总和，求最大值我们可以使用单调队列，求总和可以使用前缀和。
 *   ( 3 ) (3) (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;
            }
        }
    }

### 5）算法与时间复杂度 ###

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

[LeetCode.6171.]: https://leetcode.cn/problems/find-subarrays-with-equal-sum/
[LeetCode.6172.]: https://leetcode.cn/problems/strictly-palindromic-number/
[LeetCode.6173.]: https://leetcode.cn/problems/maximum-rows-covered-by-columns/
[LeetCode.6143.]: https://leetcode.cn/problems/maximum-number-of-robots-within-budget/