Weekly-Contest-2

周赛好题（2）

2896. Apply Operations to Make Two Strings Equal

从头到尾，dp思路：

• done: all 0
• one: exactly one 1 in [0,i-2]
• last: only the last(i-1) is 1
• two: one + last, not the same position

public int minOperations(String s1, String s2, int x) {
    int n=s1.length();
    int[] diff=new int[n];
    for (int i = 0; i < n; i++) {
        if(s1.charAt(i)!=s2.charAt(i)){
            diff[i]=1;
        }
    }
    int inf=100000;
    int done=0;
    int one=inf;
    int last=inf;
    int two=inf;
    for (int i = 0; i < n; i++) {
        if(s1.charAt(i)==s2.charAt(i)){
            //do nothing
            //one=one;
            //switch i and i-1
            last=last+1;
            //switch i and i-1
            two=two+1;
        }else{
            //last: i-1 is different, i is different
            //one: another, i is different
            //two: another, i-1, i is different
            //either one: flip i-1, i; or done: flip i
            int preOne=one;
            int preLast=last;
            one=Math.min(done,two+1);
            last=Math.min(done,two+x);
            done=Math.min(preOne+x,preLast+1);
            two=preOne;
        }
    }
    return done<inf ? done : -1;
}

2897. Apply Operations on Array to Maximize Sum of Squares

注意：

• “and or”之后，”1”数量不变，只是位置变了

• 无限次”and or”，总能把每一个”1”都放到最优的位置

public int maxSum(List<Integer> nums, int k) {
    //00 -> 00, 01 -> 10, 10 -> 10, 11 -> 11
    //1 bit remain the same amount, only change positions
    //let 1s greedily fall
    int n=nums.size();
    int mod=(int)1e9+7;
    int[] bits=new int[32];
    int[] arr=new int[n];
    for (Integer num : nums) {
        for(int i=0; i<32; i++){
            if((num&(1<<i))!=0){
                arr[bits[i]]+=((1<<i)%mod);
                arr[bits[i]]%=mod;
                bits[i]++;
            }
        }
    }
    int res=0;
    for(int i=0; i<k; i++){
        res+=(long)arr[i]*arr[i]%mod;
        res%=mod;
    }
    return res;
}

2905. Find Indices With Index and Value Difference II

思路：

• two pointers, i in front, j in back
• search for a given j, if a valid i exists

public int[] findIndices(int[] nums, int indexDifference, int valueDifference) {

    int n= nums.length;
    TreeMap<Integer,Integer> map=new TreeMap<>();
    int i=0;
    map.put(nums[i],i);
    i++;
    for(int j=indexDifference;j<n; j++){
        //[0,j-idxD]

        //[num-valD,num+valD]
        //<=num-valD or >=num+valD
        Integer val=map.floorKey(nums[j]-valueDifference);
        if(val!=null){
            int idx=map.get(val);
            return new int[]{idx,j};
        }
        val=map.ceilingKey(nums[j]+valueDifference);
        if(val!=null){
            int idx=map.get(val);
            return new int[]{idx,j};
        }
        if(i<n && !map.containsKey(nums[i])){
            map.put(nums[i],i);
        }
        i++;
    }
    return new int[]{-1,-1};
}

2906. Construct Product Matrix

经典空间换时间，use extra space for precomputation

public int[][] constructProductMatrix(int[][] grid) {
    int row=grid.length;
    int col=grid[0].length;
    int mod=12345;
    int[][] pre=new int[row][col];
    int[][] suf=new int[row][col];
    long p=1;
    for (int i = 0; i < row; i++) {
        Arrays.fill(pre[i],1);
        for (int j = 0; j < col; j++) {
            pre[i][j]=(int)p;
            p*=grid[i][j];
            p%=mod;
        }
    }
    long s=1;
    for (int i = row-1; i >= 0; i--) {
        Arrays.fill(suf[i],1);
        for (int j = col-1; j >= 0; j--) {
            suf[i][j]=(int)s;
            s*=grid[i][j];
            s%=mod;
        }
    }
    int[][] res=new int[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            res[i][j]=pre[i][j]*suf[i][j]%mod;
        }
    }
    return res;
}

2430. Maximum Deletions on a String

思路：

1. dp + substring.equals， 113 / 129 test cases passed.
2. dp + substring dp, use another dp array

//Time Limit Exceeded
public int deleteString(String s) {
    int n=s.length();
    int[] dp=new int[n]; //max of [i,n-1];
    dp[n-1]=1;
    for(int i=n-2; i>=0; i--){
        dp[i]=1;
        for(int j=i; j<n; j++){
            //j-i+1
            //[i,j] [j+1,2j-i+1]
            int c=2*j-i+1;
            if(c>=n){
                break;
            }
            if(s.substring(i,j+1).equals(s.substring(j+1,c+1))){
                dp[i]=Math.max(dp[i],dp[j+1]+1);
            }
        }
    }
    return dp[0];
}

public int deleteString(String s) {
    int n=s.length();
    int[] dp=new int[n];
    //the longest equal substring starting from s[i] and s[j]
    int[][] sub=new int[n+1][n+1];
    for (int i = n-1; i >= 0; i--) {
        dp[i]=1;
        for (int j = i+1; j < n; j++) {
            if(s.charAt(i)==s.charAt(j)){
                sub[i][j]=sub[i+1][j+1]+1;
            }
            //[i,j-1] [j,2*j-i-1]
            if(sub[i][j]>=j-i){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
    }
    return dp[0];
}

2919. Minimum Increment Operations to Make Array Beautiful

思路：

• 直接用dp存储最终结果不好transit，不如用dp存储中间结果
  • dp[i] means the minimum increments to make num[0,i] beautiful && make num[i]>=k

public long minIncrementOperations(int[] nums, int k) {
    int n=nums.length;
    long[] dp=new long[n];
    dp[0]=Math.max(0,k-nums[0]);
    dp[1]=Math.max(0,k-nums[1]);
    dp[2]=Math.max(0,k-nums[2]);
    for (int i = 3; i < n; i++) {
        //[i-2,i] is covered
        //to cover [0,i-3],
        //choose one from dp[i-3], dp[i-2], dp[i-1]
        dp[i]=Math.max(0,k-nums[i])+Math.min(dp[i-1],Math.min(dp[i-2],dp[i-3]));
    }
    return Math.min(dp[n-1],Math.min(dp[n-2],dp[n-3]));
}