Leetcode421周赛 （Mod处理）

第一题思路没错，但做太久了。第二题做完快没时间了，选了第二题类似的第四做（结果最后几个样例过不了， 第三题结束之后发现更加简单一点。本周很多题都是涉及到MoD处理。

第一题

3334. 数组的最大因子得分

简单来说就是分别求lcm和gcd的前缀和，后缀和，其它思路和除本身以外的乘积一样。

class Solution {
    public long maxScore(int[] nums) {
        if(nums.length == 0)return 0;
        if(nums.length == 1)return (long)nums[0]*nums[0];
        long[] gcd_1 = new long[nums.length];
        long[] gcd_2 = new long[nums.length];
        long[] lcm_1 = new long[nums.length];
        long[] lcm_2 = new long[nums.length];
        
        gcd_1[0] = nums[0];
        lcm_1[0] = nums[0];
        
        gcd_2[nums.length-1] = nums[nums.length-1];        
        lcm_2[nums.length-1] = nums[nums.length-1];
        
        
        for(int i = 1;i<nums.length;i++){
            gcd_1[i] = gcd(gcd_1[i-1], nums[i]);
            lcm_1[i] = lcm(lcm_1[i-1], nums[i]);
        }
        
        for(int i = nums.length-2;i>=0;i--){
            gcd_2[i] = gcd(gcd_2[i+1], nums[i]);
            lcm_2[i] = lcm(lcm_2[i+1], nums[i]);
        }
        
        long[] max = new long[nums.length];
        long ans = 0;
        
        for(int i=0;i<nums.length;i++){
            if(i==0){
                ans = Math.max(ans , gcd_2[1] * lcm_2[1]);
            }else if(i==nums.length-1){
                ans = Math.max(ans , gcd_1[nums.length-2] * lcm_1[nums.length-2]);
            }else{
                ans = Math.max(gcd(gcd_1[i-1] , gcd_2[i+1]) * lcm(lcm_1[i-1], lcm_2[i+1]), ans);
            }
        }
        return Math.max(gcd_1[nums.length-1]*lcm_1[nums.length-1] , ans);
    }
    long gcd(long a , long b){
        while(b!=0){
            long tmp = b;
            b = a % b;
            a =tmp;
        }
        return a;
    }
    long lcm(long a, long b){
        return (a/gcd(a,b))*b;
    }
}

第二题

3335. 字符串转换后的长度 I

这题刚开始写的模拟思路，即每次更改之后将字符串修改，再次迭代，超时。最后模拟将字符串抽象成26位数组，逐次迭代， 时间复杂度 26*N

class Solution {
    static final  int MOD = 1000000007;
    public int lengthAfterTransformations(String s, int t) {
        long count = 0;
        long[] index  = new long[26];
        for(char c: s.toCharArray()){
            index[c-'a']++;
        }
        
        for(int i=0;i<t;i++){
            long tmp = index[25];
            for(int x=25;x>0;x--){
                index[x] = index[x-1];
            }
            index[0] = tmp;
            index[1] = (index[1] + tmp)  % MOD;
        }
        for(int i=0;i<26;i++){
            count = (count + index[i] ) % MOD;
        }
        return (int)count;
    }
}

第三题

3336. 最大公约数相等的子序列数量

记忆化搜索，从数组最后一位开始，seq1和seq2 可以同时不选当前位，或者seq1选， 或者seq2选

class Solution {
    int[] nums;
     private static final int MOD = 1_000_000_007;
    int[][][] memo;
    public int subsequencePairCount(int[] nums) {
        this.nums = nums;
        Arrays.sort(nums);
        memo = new int[nums.length+2][nums[nums.length-1]+2][nums[nums.length-1]+2];
        for(int[][] mem : memo){
            for(int[] me:mem){
                Arrays.fill(me, -1);
            }
        }
        return (dfs(nums.length - 1, 0, 0) - 1 +   MOD)  % MOD;
    }
    int dfs(int index, int seq1, int seq2){
        if(index<0) return seq1==seq2?1:0;
        if(memo[index][seq1][seq2]!=-1)return memo[index][seq1][seq2];
        int num = nums[index];
        long res = (long) dfs(index-1, seq1, seq2) + 
                dfs(index - 1, gcd(num, seq1), seq2) + 
                dfs(index -1,  seq1, gcd(num, seq2));
        return memo[index][seq1][seq2] = (int) (res % MOD);
    }
    int gcd(int a , int b){
        while(b!=0){
            int tmp = b;
            b = a % b;
            a = tmp;
        }
        return a;
    }
}

常用MOD方式

一般来说Mod都是10^9 + 7

// 定义：
static final  int MOD = 1000000007;
// ans  += dfs()
ans = ( ans + dfs()) % MOD
// int  --> long --> int
long res = (long) dfs()
ans = (int) (res % MOD)
// - 1 防止溢出  ( dfs() -1 ) % MOD
ans = (dfs() - 1 + MOD) % MOD