前后缀分解
class Solution {
public int waysToPartition(int[] nums, int k) {
//前后缀分解
int n=nums.length;
int sum = Arrays.stream(nums).sum();
Map<Integer,Integer> prefix=new HashMap<Integer,Integer>();
Map<Integer,Integer> subfix=new HashMap<Integer,Integer>();
//将所有的后缀加入subfix
int rsum=0;
for(int i=n-1;i>=1;i--){
rsum+=nums[i];
subfix.put(rsum,subfix.getOrDefault(rsum,0)+1);
}
int res=0;
if(sum%2==0){
res=subfix.getOrDefault(sum/2,0);//初始化
}
//替换每一个元素
int lsum=0;
for(int i=0;i<n;i++){
int change=k-nums[i];
int new_sum=sum+change;
if(new_sum%2==0){
//可以划分计算
res=Math.max(res,prefix.getOrDefault(new_sum/2,0)+subfix.getOrDefault(new_sum/2,0));
}
if(i!=n-1){//最后一次可以不许计算
//维护前后缀
lsum+=nums[i];
prefix.put(lsum,prefix.getOrDefault(lsum,0)+1);
subfix.put(sum-lsum,subfix.getOrDefault(sum-lsum,0)-1);
if(subfix.get(sum-lsum)==0){
subfix.remove(sum-lsum);
}
}
}
return res;
}
}
形成目标数组的子数组最少操作次数
形成目标数组的子数组最少操作次数
通过差分数组进行分析,每次操作最多将一个正数减一
class Solution {
public int minNumberOperations(int[] target) {
int res=target[0];
for(int i=1;i<target.length;i++){
res+=Math.max(target[i]-target[i-1],0);
}
return res;
}
}
拼车
拼车
通过差分数组模拟 trip[2]下车,所以每次对区间[trip[1],trip[2]-1]进行区间操作
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
//创建差分数组
int[] nums=new int[1010];
for(int[] trip:trips){
nums[trip[1]]+=trip[0];
nums[trip[2]]-=trip[0];
}
int sum=0;
for(int i=0;i<nums.length;i++){
if(sum>capacity){
return false;
}
sum+=nums[i];
}
return true;
}
}
前缀异或
class Solution {
public int[] xorQueries(int[] arr,int[][] queries){
int n=arr.length;
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]^arr[i];
}
int[] res=new int[queries.length];
int index=0;
for (int[] query : queries) {
int left=query[0];int right=query[1];
res[index++]=prefix[right+1]^prefix[left];
}
return res;
}
}
所有排列中的最大和
所有排列中的最大和
通过差分数组维护区间修改结果与次数
class Solution {
public int maxSumRangeQuery(int[] nums,int[][] requests){
int n=nums.length;
int MOD=1000000007;
long[] count=new long[n];
//维护差分数组
for (int[] request : requests) {
int start=request[0];int end=request[1];
count[start]++;
if(end+1<n){
count[end+1]--;
}
}
//将所有的次数计算前缀
for(int i=1;i<n;i++){
count[i]+=count[i-1];
}
long res=0;
Arrays.sort(count);
Arrays.sort(nums);
for(int i=n-1;i>=0&&count[i]>0;i--){
res=res%MOD+nums[i]%MOD*count[i]%MOD;
}
return (int)res%MOD;
}
}
前后缀分解 两个固定长度非重叠子数组的最大和
前后缀分解
枚举第二个区间的起点,作为前后缀的分界点
class Solution {
public int maxSumTwoNoOverlap(int[] nums, int firstLen, int secondLen) {
//预处理前缀和
int n=nums.length;
int[] prefix=new int[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+nums[i];
}
int res1=0;int temp=0;
for(int i=firstLen;i+secondLen-1<n;i++){//枚举第二段起点
temp=Math.max(temp,prefix[i]-prefix[i-firstLen]);
res1=Math.max(res1,temp+prefix[i+secondLen]-prefix[i]);
}
int res2=0;temp=0;
for(int i=secondLen;i+firstLen-1<n;i++){
temp=Math.max(temp,prefix[i]-prefix[i-secondLen]);
res2=Math.max(res2,temp+prefix[i+firstLen]-prefix[i]);
}
return Math.max(res1,res2);
}
}