Leetcode - 周赛405

目录

一，3210. 找出加密后的字符串

二，3211. 生成不含相邻零的二进制字符串

三，3212. 统计 X 和 Y 频数相等的子矩阵数量

---

一，3210. 找出加密后的字符串

本题是一道模拟题，代码如下：

class Solution {
    public String getEncryptedString(String s, int k) {
        StringBuilder res = new StringBuilder();
        int n = s.length();
        for(int i=0; i<n; i++){
            res.append(s.charAt((i+k)%n));
        }
        return res.toString();
    }
}

二，3211. 生成不含相邻零的二进制字符串

本题可以使用dfs暴力枚举每一位的数字，代码如下：

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> validStrings(int n) {
        char[] t = new char[n];
        dfs(n,0,t);
        return res;
    }
    void dfs(int n, int i, char[] t){
        if(i == n){
            res.add(new String(t));
            return;
        } 
        if(i==0 || t[i-1]=='1'){
            t[i] = '1';
            dfs(n, i+1, t);
            t[i] = '0';
            dfs(n, i+1, t);
        }else{
            t[i] = '1';
            dfs(n, i+1, t);
        }
    }
}

这里再贴一个位运算的写法，代码如下：

class Solution {
    public List<String> validStrings(int n) {
        List<String> ans = new ArrayList<>();
        int mask = (1<<n) - 1;
        for(int i=0; i<(1<<n); i++){
            int x = mask ^ i;//i取反
            if(((x>>1)&x) == 0){//取反没有相邻的1，那么i就没有相邻的0
                ans.add(Integer.toBinaryString((1<<n)|i).substring(1));
            }
        }
        return ans;
    }
}

三，3212. 统计 X 和 Y 频数相等的子矩阵数量

本题使用二维前缀和来做，不会的可以看周赛387题解，这里不再讲解原理。

代码如下：

class Solution {
    public int numberOfSubmatrices(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        int[][][] f = new int[n+1][m+1][2];
        int ans = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                f[i+1][j+1][0] = f[i][j+1][0] + f[i+1][j][0] - f[i][j][0] + (grid[i][j]=='X'?1:0);
                f[i+1][j+1][1] = f[i][j+1][1] + f[i+1][j][1] - f[i][j][1] + (grid[i][j]=='Y'?1:0);
                if(f[i+1][j+1][0] > 0 && f[i+1][j+1][0] == f[i+1][j+1][1]) 
                    ans++;
            }
        }
        return ans;
    }
}

第四题有时间在补上~