【力扣周赛#334】6369. 左右元素和的差值 + 6368. 找出字符串的可整除数组 + 6367. 求出最多标记下标

目录

6369. 左右元素和的差值 - 前缀后缀和 ac

6368. 找出字符串的可整除数组 - 操作余数ac

6367. 求出最多标记下标 - 二分答案 + 贪心

---

6369. 左右元素和的差值 - 前缀后缀和 ac

class Solution {public int[] leftRigthDifference(int[] nums) {int n=nums.length;int[] res=new int[n];int[] l=new int[1010],r=new int[1010];int[] s=new int[1010],t=new int[1010];for(int i=1;i<=n;i++) s[i]=s[i-1]+nums[i-1];for(int i=n;i>=1;i--) t[i]=t[i+1]+nums[i-1];for(int i=0;i<n;i++) l[i]=s[i];int cnt=0;for(int i=2;i<=n+1;i++) r[cnt++]=t[i];for(int i=0;i<n;i++) res[i]=Math.abs(r[i]-l[i]);return res;}
}

6368. 找出字符串的可整除数组 - 操作余数ac

6368. 找出字符串的可整除数组

思路：

暴力取字符串每一段，组合成的数最大有10^5位，肯定tle

所以我们对每一位取余，把余数*10加到下一个数上

如果%m为0，说明0~i位可以整除，否则不能

class Solution {public int[] divisibilityArray(String s, int m) {int n=s.length();int[] res=new int[n];long x=0;for(int i=0;i<n;i++){int t=s.charAt(i)-'0';x=(t+10*x)%m;if(x==0) res[i]=1;else res[i]=0;}return res;}
}

 

6367. 求出最多标记下标 - 二分答案 + 贪心

6367. 求出最多标记下标

题目：

思路：

如果可以匹配k对，则将答案放大，直到不能满足匹配条件，则能二分出最大值

想要匹配对数最大，则nums[i]越小，nums[j]越大越好

则就是排序后，最小的k个数和最大的k个数匹配

nums[0]跟nums[n-k]匹配，则nums[i]跟nums[n-k+i]匹配

二分答案，如果该k对都能一一满足条件，则答案放大，否则放小

最后答案就是2*k

class Solution {public int maxNumOfMarkedIndices(int[] nums) {Arrays.sort(nums);int l=0,r=nums.length/2;while(l<r){int mid=l+r+1>>1;if(ck(nums,mid)) l=mid;else r=mid-1;}return l*2;}public boolean ck(int[] nums,int k){for(int i=0;i<k;i++)if(nums[i]*2>nums[nums.length-k+i]) return false;return true;}
}