double-weekly-contest-35
-
本次双周赛重要知识点为前缀和，之前不了解前缀和相关知识点，导致题目做的磕磕绊绊
-
连续子数组问题往往可以通过前缀和来解决
1/5503. 所有奇数长度子数组的和
- 暴力枚举所有奇数长度子数组并且求和，时间复杂度O(n^3)
class Solution {
public int sumOddLengthSubarrays(int[] arr) {
int len = arr.length;
int res = 0;
for(int i=0;i<len;i++){
for(int j=i;j<len;j++){
if((j-i)%2==0){
res+= add(arr,i,j);
}
}
}
return res;
}
public int add(int[] arr, int start, int end){
int res = 0;
for(int i=start; i<=end; i++){
res += arr[i];
}
return res;
}
}
- 使用前缀和数组预计算数组子区间的和，prefix[j]-prefix[i-1]等于从 i 到 j 的元素和，时间复杂度缩减到O(n^2)
// 前缀和
// 在解法一中，add函数是计算数组从start到end的和，数组被反复计算多次，这里可以使用前缀和预先计算
class Solution{
public int sumOddLengthSubarrays(int[] arr){
int len = arr.length;
int res = 0;
int[] prefix = new int[len];
prefix[0] = arr[0];
for(int i=1; i<len; i++){
prefix[i] = prefix[i-1] + arr[i];
}
for(int i=0;i<len;i++){
for(int j=i;j<len;j+=2){
if(i==0)
res+= prefix[j];
else
res+= prefix[j]-prefix[i-1];
}
}
return res;
}
}
2/5504. 使数组和能被 P 整除
- 第一个想到的是使用循环遍历删除（代码里写的DFS，但实际上不是DFS），枚举nums数组中的每个数字，从该数字开始删除，如果删除后的数字能被p整除，则更新一个最短删除子数组，这样的做法时间复杂度高，超时
class Solution {
// 子数组连续
// 只能删除一个子数组
// 回溯，每次只删除一个元素，下一步删除下一个元素
// 当删除结果可以被p整除时将该结果更新到minDelete中
// 回溯完全部分支后能得到最小删除数组
int minDel;
int p;
public int minSubarray(int[] nums, int p) {
long numsSum = 0;
minDel = Integer.MAX_VALUE;
this.p = p;
for(int i=0;i<nums.length;i++){
numsSum += nums[i];
}
//不需要删除任何元素，和已经能被p整除
if(numsSum%p==0)return 0;
for(int i=0; i<nums.length;i++){
deleteDFS(nums, numsSum-nums[i], i,i);
}
//当minDel为Integer.MAX_VALUE时，回溯中没有进行任何一次删除，即任何方案都不能使得和被整除
return minDel==Integer.MAX_VALUE?-1:minDel;
}
public void deleteDFS(int[] nums, long left, int delBegin, int cur){
if(left<p)return;
//当前删除已可以被整除时，不需要判断下一个，下一个minDel一定比当前minDel大
if(left%p==0){
minDel = Math.min(minDel, cur-delBegin+1);
return;
}
if(cur+1<nums.length)
deleteDFS(nums, left-nums[cur+1], delBegin, cur+1);
}
}
- 由于取模对加减法有分配律，所以可以通过计算前缀和以及对前缀和进行取模来计算子数组区间，当区间取模的结果等于总和取模的结果时，将该区间删除，剩余的数组和就能够被p整除
- 在实现上可以使用一个哈希表（HashMap）储存距离当前位置最近的targetmod，具体细节见代码
class Solution{
// 取模前缀和
public int minSubarray(int[] nums, int p){
long sum =0;
for(int num:nums){
sum+=num;
}
int mod = (int)(sum%p);
System.out.println(mod);
if(mod==0)return 0;
int res = nums.length;
// key-value : curmod-index
HashMap<Integer,Integer> map = new HashMap<>();
// 当curmod==mod的时候，该前缀和求模等于总和求模，所以该前缀全部可以删除
// 此时的target==0
map.put(0,-1);
sum=0;
for(int i=0; i<nums.length;i++){
sum += nums[i];
int curmod = (int)(sum%p);
int targetmod = curmod>=mod? curmod-mod: curmod-mod+p;
if(map.containsKey(targetmod)){
res = Math.min(res, i-map.get(targetmod));
}
map.put(curmod, i);
}
return res==nums.length?-1:res;
}
}
3/5505. 所有排列中的最大和
- 自己解答的时候使用的是两个哈希函数来计算查询次数，start放置区间开始的位置和次数，end放置区间结束的位置和次数，通过start-end动态计算count就能判断当前位置被查询过多少次。
- 在看了题解后发现还可以通过使用差分数组计算区间累加的数组
class Solution {
// 使用requests计算每个位置被查询的次数，查询次数最多的位置放置数组最大值，第二多的放数组第二大值
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int res = 0;
int[] times = new int[nums.length];
HashMap<Integer,Integer> start = new HashMap<>();
HashMap<Integer,Integer> end = new HashMap<>();
for(int[] request:requests){
start.put(request[0], start.getOrDefault(request[0],0)+1);
end.put(request[1], end.getOrDefault(request[1],0)+1);
}
// System.out.println(end);
int count=0;
for(int i=0;i<nums.length; i++){
if(start.containsKey(i)){
count+=start.get(i);
}
times[i] = count;
if(end.containsKey(i)){
count-=end.get(i);
}
}
// System.out.println(Arrays.toString(times));
Arrays.sort(times);
Arrays.sort(nums);
for(int i=0; i<nums.length; i++){
// if(nums[i]==0)break;
res += times[i]*nums[i];
res %= 1000000007;
}
return res;
}
}
- 使用差分数组
class Solution {
// 使用requests计算每个位置被查询的次数，查询次数最多的位置放置数组最大值，第二多的放数组第二大值
public int maxSumRangeQuery(int[] nums, int[][] requests) {
int res = 0;
int[] fre = new int[nums.length+1];
for(int[] request:requests){
fre[request[0]] ++;
fre[request[1]+1] --;
}
for(int i=1; i<nums.length; i++){
fre[i] += fre[i-1];
}
//System.out.println(Arrays.toString(fre));
Arrays.sort(fre);
Arrays.sort(nums);
for(int i=nums.length; i>=1 && fre[i]>0; i--){
// if(nums[i]==0)break;
res += fre[i]*nums[i-1];
res %= 1000000007;
}
return res;
}
}
4/5506. 奇怪的打印机 II
- 判断出颜色与颜色之间的关系，一个颜色只能出现一次，所以每个颜色有严格的染色顺序，当B被包括在A矩阵中时，A要先于B被染色，即建立A->B的有向边。整个矩阵targetGrid全部建立完边之后，判断图是否满足拓扑排序，如果不满足则存在环。
class Solution {
// 建立有向图，对每个颜色建立边
// 图必须存在拓扑排序，即一个颜色必须在另一个颜色之后进行染色
public boolean isPrintable(int[][] targetGrid) {
int rows= targetGrid.length, cols = targetGrid[0].length;
// 初始化每个颜色矩阵的边界
int[] top= new int[61],bottom= new int[61],left= new int[61],right = new int[61];
Arrays.fill(top,61);
Arrays.fill(left,61);
Arrays.fill(bottom,-1);
Arrays.fill(right,-1);
int color = 0;
// 建立每个颜色的矩阵边界
for(int i=0;i<rows;i++){
for(int j=0; j<cols; j++){
color = targetGrid[i][j];
top[color] = Math.min(top[color], i);
bottom[color] = Math.max(bottom[color], i);
left[color] = Math.min(left[color], j);
right[color] = Math.max(right[color], j);
}
}
// 根据矩阵建立有向图，遍历targetGrid，
// 当前位置颜色X在某个矩阵A中但是不为矩阵A的颜色时，建立从A到X的边
// X可以存在于多个矩阵中
// 变量：是否存在边-防止重复建立边；入度，便于后期判断是否拓扑排序；邻接表，从i出发到达的点
boolean[][] hasEdge= new boolean[61][61];
int[] inDegree = new int[61];
List<List<Integer>> adjs = new ArrayList<>();
for(int i=0;i<=60;i++){
adjs.add(new ArrayList<Integer>());
}
int curColor = 0;
// 建立图
for(int i=0;i<rows;i++){
for(int j=0; j<cols; j++){
curColor = targetGrid[i][j];
for(color=1; color<=60; color++){
if(i>=top[color] && i<=bottom[color] && j>=left[color] && j<=right[color])
if(curColor!=color && !hasEdge[color][curColor]){
adjs.get(color).add(curColor);
inDegree[curColor]++;
hasEdge[color][curColor] = true;
}
}
}
}
// 寻找入度为0的颜色点，减小该点连结的点的入度，直到所有点的入度都为0
ArrayList<Integer> zeroC = new ArrayList<>();
while(true){
int i;
for(i=1;i<=60;i++){
if(inDegree[i]==0){
zeroC.add(i);
for(Integer pointTo:adjs.get(i)){
inDegree[pointTo]--;
}
inDegree[i]=-1;
break;
}
}
if(i==61)break;
}
return zeroC.size()==60;
}
}