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

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

目录

• 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. 和相等的子数组

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 (ains(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. 严格回文的数字

3）思路解析

• ( 1 ) (1) (1)Java中自带转进制的函数，我们直接暴力枚举判断即可。将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&#String(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. 被列覆盖的最多行数

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 && (j) != 1) {f = false;break;}}if (f) res++;}ans = Math.max(ans, res);return;}//如果选list.add(1);dfs(arr, list, v + 1);ve(list.size() - 1);//如果不选list.add(0);dfs(arr, list, v);ve(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. 预算内的最多机器人数目

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)。