LeetCode Contest 405

欢迎大家加QQ群：623375442，可以方便群里面交流。

100339. Find the Encrypted String

给你一个字符串 s 和一个整数 k。请你使用以下算法加密字符串：

• 对于字符串 s 中的每个字符 c，用字符串中 c 后面的第 k 个字符替换 c（以循环方式）。

返回加密后的字符串。

测试样例：

输入：s = "dart", k = 3

输出："tdar"

解释：

• 对于 i = 0，'d' 后面的第 3 个字符是 't'。
• 对于 i = 1，'a' 后面的第 3 个字符是 'd'。
• 对于 i = 2，'r' 后面的第 3 个字符是 'a'。
• 对于 i = 3，'t' 后面的第 3 个字符是 'r'。

解答：凯撒密码，暴力替换。

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

100328. Generate Binary Strings Without Adjacent Zeros

给你一个正整数 n。

如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

测试样例：

输入： n = 3

输出： ["010","011","101","110","111"]

解释：最长的有效子序列是 [1, 2, 3, 4]。

解答：题目贴心的把n = 1的情况写出来了，可以记录一下这个情况。其他数字暴力生成所有结果，然后check是否满足要求就行了。

class Solution {
    public List<String> validStrings(int n) {
        if (n == 1) {
            return Arrays.asList("0","1");
        }
        List<String> res = new ArrayList<>();
        int max = (1 << n);
        for (int i = 1; i < max; ++i) {
            boolean isValid = true;
            for (int j = 1; j < n; ++j) {
                if (!(isMark(i, j) || isMark(i, j - 1))) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; ++j) {
                    if (isMark(i, j)) {
                        sb.append(1);
                    } else {
                        sb.append(0);
                    }
                }
                res.add(sb.toString());
            }
        }
        return res;
    }

    private boolean isMark(int num, int offset) {
        int tmp = (num >> offset) & 1;
        return tmp == 1;
    }
}

100359. Count Submatrices With Equal Frequency of X and Y

给你一个二维字符矩阵 grid，其中 grid[i][j] 可能是 'X'、'Y' 或 '.'，返回满足以下条件的子矩阵数量：

• 包含 grid[0][0]
• 'X' 和 'Y' 的频数相等。
• 至少包含一个 'X'。

测试样例：

输入：grid = [["X","Y","."],["Y",".","."]]

输出：3

解答：三维的前缀和，计算各个前缀X和Y的数量。然后按照题意判断。

class Solution {
    public int numberOfSubmatrices(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] countX = new int[n], countY = new int[n];

        int res = 0;
        for (int i = 0; i < m; ++i) {
            int rowX = 0, rowY = 0;
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'X') {
                    ++rowX;
                } else if (grid[i][j] == 'Y') {
                    ++rowY;
                }
                countX[j] += rowX;
                countY[j] += rowY;
                if (countX[j] == countY[j] && countX[j] > 0) {
                    ++res;
                }
            }
        }
        return res;
    }
}

100350. Construct String with Minimum Cost

给你一个字符串 target、一个字符串数组 words 以及一个整数数组 costs，这两个数组长度相同。

设想一个空字符串 s。

你可以执行以下操作任意次数（包括零次）：

• 选择一个在范围 [0, words.length - 1] 的索引 i。
• 将 words[i] 追加到 s。
• 该操作的成本是 costs[i]。

返回使 s 等于 target 的 最小 成本。如果不可能，返回 -1。

测试样例：

输入：target = "abcdef", words = ["abdef","abc","d","def","ef"], costs = [100,1,1,10,5]

输出：7

解释：

• 选择索引 1 并以成本 1 将 "abc" 追加到 s，得到 s = "abc"。
• 选择索引 2 并以成本 1 将 "d" 追加到 s，得到 s = "abcd"。
• 选择索引 4 并以成本 5 将 "ef" 追加到 s，得到 s = "abcdef"。

解答：没想到这道题目居然用Trie树配合动态规划能过。。。感觉会被rejudge。先贴一下周赛中能过的答案吧。

class Solution {
    private class TrieNode {
        HashMap<Character, TrieNode> next;
        int cost;

        public TrieNode() {
            next = new HashMap<>();
            cost = Integer.MAX_VALUE;
        }
    }

    private class Data {
        TrieNode root;
        String target;
        int[] dp;

        public Data(String target, String[] words, int[] costs) {
            root = new TrieNode();
            for (int i = 0; i < words.length; ++i) {
                TrieNode tmp = root;
                for (int j = 0; j < words[i].length(); ++j) {
                    if (!tmp.next.containsKey(words[i].charAt(j))) {
                        tmp.next.put(words[i].charAt(j), new TrieNode());
                    }
                    tmp = tmp.next.get(words[i].charAt(j));
                }
                tmp.cost = Math.min(tmp.cost, costs[i]);
            }

            this.target = target;
            this.dp = new int[target.length() + 1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[target.length()] = 0;
        }
    }

    public int minimumCost(String target, String[] words, int[] costs) {
        Data data = new Data(target, words, costs);
        return dfs(data, 0);
    }

    private int dfs(Data data, int pos) {
        if (data.dp[pos] == Integer.MAX_VALUE) {
            TrieNode tmp = data.root;
            for (int i = pos; i < data.target.length(); ++i) {
                if (!tmp.next.containsKey(data.target.charAt(i))) {
                    break;
                } else {
                    tmp = tmp.next.get(data.target.charAt(i));
                }
                if (tmp.cost != Integer.MAX_VALUE) {
                    int t = dfs(data, i + 1);
                    if (t != -1) {
                        data.dp[pos] = Math.min(data.dp[pos], t + tmp.cost);
                    }
                }
            }
            if (data.dp[pos] == Integer.MAX_VALUE) {
                data.dp[pos] = -1;
            }
        }
        return data.dp[pos];
    }
}