目录
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;}
}