Leetcode第419周赛 溢出导致第三题GG

第一题

计算子数组的 x-sum I

老规矩，第一题直接暴力，截取每一个子数组，然后对子数组的字符存储，然后排序，只能过第一题。本质上这题应该是和滑动窗口有关。

class Solution {
    public int[] findXSum(int[] nums, int k, int x) {
int n = nums.length;

        int[] result = new int[n - k + 1]; 
        for(int i=0;i<=n-k;i++){
            int[] sub = Arrays.copyOfRange(nums, i, i + k);
            Map<Integer, Integer> freqMap = new HashMap<>();
            for(int num:sub){
                freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
            }
            List<Map.Entry<Integer, Integer>> freqList = new ArrayList<>(freqMap.entrySet());
            freqList.sort((a, b) -> {
                if (b.getValue().equals(a.getValue())) {
                    return b.getKey() - a.getKey();  
                } else {
                    return b.getValue() - a.getValue(); 
                }
            });
  
            int xSum = 0;
            for (int j = 0; j < Math.min(x, freqList.size()); j++) {
                xSum += freqList.get(j).getKey() * freqList.get(j).getValue();
            }
            
            result[i] = xSum;
        }
        return result;
    }
}

第二题

3319. 第 K 大的完美二叉子树的大小

一个树型DP，采用dfs的方式解决。只需要判断left子树和right子树是否相同，如果相同返回left+right+当前结点，否则返回-1（刚开始写的0，几个样例不能通过，因为左右不同的时候的长度会有当前节点）

class Solution {
   Map<TreeNode, Integer> map;
    public int kthLargestPerfectSubtree(TreeNode root, int k) {
        map = new HashMap<>();
        dfs(root);
        List<Map.Entry<TreeNode, Integer>> entries = new ArrayList<>(map.entrySet());
         // 按值从大到小排序
        entries.sort((a, b) -> b.getValue() - a.getValue());
        if (k > entries.size()) {
            return -1;
        }
        return entries.get(k - 1).getValue();
    }
    int dfs(TreeNode node){
        if(node==null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        if(left==right){
            int sum = left+right+1;
            map.put(node, sum);
            return sum;
        }
        return -1;
    }
}

第三题

3320. 统计能获胜的出招序列数

结束之后发现：不能 res += dfs() %Mod 要 res = res + dfs() %Mod 了 ，溢出最后几十个样例错误，痛失6分

这题实际上就是记忆化搜索，只需要将题目转发一下，就是一个每次选拿个的问题。

class Solution {
  int n;
    int[][][] memo;
    char[] ch;
    static final  int MOD = 1000000007;
     char[] ssc = new char[]{'F','W','E'};

    public int countWinningSequences(String s) {
        n = s.length();
        ch = s.toCharArray();
        memo = new int[n][3][2 * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k <= 2 * n; k++) {
                    memo[i][j][k] = -1;
                }
            }
        }
        int result = 0;
        for (int bobMove = 0; bobMove < 3; bobMove++) {
            result =  (result + dfs(n - 2, bobMove, getScore(n-1,bobMove))) % MOD;
        }
        return (int)result;
    }
    int dfs(int i, int j, int target){
        int x = target + n;
        
        if( i < 0) {
            return target > 0 ? 1 : 0;
        }
        if(memo[i][j][x] != -1)return memo[i][j][x];
        int result = 0;
        for(int z=0;z<3;z++){
            if(z==j )continue;
            result = (result +  dfs(i - 1, z, target  + getScore(i,z))) % MOD;
        }
        memo[i][j][x] = result;
        return result % MOD;

    }

    int getScore(int i, int j) {
        char c = ssc[j];
        char d = ch[i];
        if (d == c) return 0;
        if (d == 'F' && c == 'W') return 1;
        if (d == 'W' && c == 'E') return 1;
        if (d == 'E' && c == 'F') return 1;
        return -1;
    }
}

第四题

哈哈，三题选手从来不考虑四题的事