删除子数组的最大得分
删除子数组的最大得分
双指针
class Solution {
public int maximumUniqueSubarray(int[] nums) {
int res=0;
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();
int ans=Integer.MIN_VALUE;
for(int i=0,j=0;i<nums.length;i++){
res+=nums[i];
while(cnt.getOrDefault(nums[i],0)>0){
res-=nums[j];
cnt.put(nums[j],cnt.get(nums[j])-1);
if(cnt.get(nums[j])==0){
cnt.remove(nums[j]);
}
j++;
}
cnt.put(nums[i],cnt.getOrDefault(nums[i],0)+1);
ans=Math.max(ans,res);
}
return ans;
}
}
三等分字符串的方案数
三等分字符串的方案数
通过列表记录所有的1出现的位置,可以在O(1)时间获得每一个1的位置
class Solution {
public int numWays(String s){
int MOD=1000000007;
List<Integer> ones=new ArrayList<Integer>();
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='1'){
ones.add(i);
}
}
int m=ones.size();
if(m%3!=0){
return 0;
}
int n=s.length();
if(m==0){//分割成非空字符串
long ways=(long)(n-1)*(n-2)/2;
return (int)(ways%MOD);
}else{
int index1=m/3;int index2=m/3*2;
int count1=ones.get(index1)-ones.get(index1-1);
int count2=ones.get(index2)-ones.get(index2-1);
long res=(long)count1*count2;
return (int)(res%MOD);
}
}
}
三指针
三指针
通过三指针维护target
i,j,k
class Solution {
public int threeSumMulti(int[] arr,int target){
int MOD=1000000007;
long res=0;
int n=arr.length;
Arrays.sort(arr);
//通过三指针方式
for(int i=0;i<n;i++){
int next_target=target-arr[i];
int j=i+1;int k=arr.length-1;
//对于
while(j<k){
if(arr[j]+arr[k]<next_target){
j++;
}else if(arr[j]+arr[k]>next_target){
k--;
}else if(arr[j]!=arr[k]){
//中间可能存在不满足于的元素
int left_count=1;int right_count=1;
while(j+1<k&&arr[j]==arr[j+1]){
j++;
left_count++;
}
while(k-1>j&&arr[k]==arr[k-1]){
k--;
right_count++;
}
res=res%MOD+left_count%MOD*right_count%MOD;
//对于不同的arr[j]+arr[k]
j++;k--;
}else{
//直接将中间的元素进行选择
res=res+(k-j+1)*(k-j)/2;
res%=MOD;
break;
}
}
}
return (int)res%MOD;
}
}
爱生气的书店老板
爱生气的书店老板
通过双指针维护固定大小窗口
for(int i=0;i<n;i++){
sum+=arr[i];
//如果对应的指针超过对应的长度
if(i>=windowlength){
sum-=arr[i];//维护窗口大小
}
}
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
//通过双指针进行维护
int res=0;
int n=customers.length;
//新增加的
int sum=0;
for(int i=0;i<n;i++){
sum+=grumpy[i]*customers[i];
if(i>=minutes){
sum-=grumpy[i-minutes]*customers[i-minutes];
}
res=Math.max(res,sum);
}
for(int i=0;i<n;i++){
if(grumpy[i]==0){
res+=customers[i];
}
}
return res;
}
}