LeetCode Contest 385

今天是节后工作第一天，还是祝大家龙年吉祥万事如意，还有开工大吉！然后第一题和最后一题一样，我就只放最后一题的题解，跳过第一题了。

100229. Find the Length of the Longest Common Prefix

给你两个 正整数 数组 arr1 和 arr2 。

正整数的 前缀 是其 最左边 的一位或多位数字组成的整数。例如，123 是整数 12345 的前缀，而 234 不是 。

设若整数 c 是整数 a 和 b 的 公共前缀 ，那么 c 需要同时是 a 和 b 的前缀。例如，5655359 和 56554 有公共前缀 565 ，而 1223 和 43456 没有 公共前缀。

你需要找出属于 arr1 的整数 x 和属于 arr2 的整数 y 组成的所有数对 (x, y) 之中最长的公共前缀的长度。

返回所有数对之中最长公共前缀的长度。如果它们之间不存在公共前缀，则返回 0 。

测试样例：

输入：arr1 = [1,10,100], arr2 = [1000]

输出：3

解释：存在 3 个数对 (arr1[i], arr2[j]) ：

• (1, 1000) 的最长公共前缀是 1 。
• (10, 1000) 的最长公共前缀是 10 。
• (100, 1000) 的最长公共前缀是 100 。

最长的公共前缀是 100 ，长度为 3 。

解答：寻找频次最高的前缀，最容易计算的数据结构是Trie树。利用Trie树可以记录arr1所有数字，然后再遍历arr2寻找最长前缀。

class Solution {
    private class TrieNode {
        HashMap<Character, TrieNode> next;
        boolean isEnd;

        public TrieNode() {
            next = new HashMap<>();
            isEnd = false;
        }
    }

    private void addStr(TrieNode node, String w) {
        for (int i = 0; i < w.length(); ++i) {
            char c = w.charAt(i);
            if (!node.next.containsKey(c)) {
                node.next.put(c, new TrieNode());
            }
            node = node.next.get(c);
        }
        node.isEnd = true;
    }

    private int findLen(TrieNode node, String w) {
        int add = 0;
        for (int i = 0; i < w.length(); ++i) {
            char c = w.charAt(i);
            if (!node.next.containsKey(c)) {
                break;
            }
            node = node.next.get(c);
            ++add;
        }
        return add;
    }

    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        TrieNode root = new TrieNode();
        for (int n : arr1) {
            addStr(root, String.valueOf(n));
        }

        int res = 0;
        for (int n : arr2) {
            String tmp = String.valueOf(n);
            res = Math.max(res, findLen(root, tmp));
        }
        return res;
    }
}

100217. Most Frequent Prime

给你一个大小为 m x n 、下标从 0 开始的二维矩阵 mat 。在每个单元格，你可以按以下方式生成数字：

• 最多有 8 条路径可以选择：东，东南，南，西南，西，西北，北，东北。
• 选择其中一条路径，沿着这个方向移动，并且将路径上的数字添加到正在形成的数字后面。
• 注意，每一步都会生成数字，例如，如果路径上的数字是 1, 9, 1，那么在这个方向上会生成三个数字：1, 19, 191 。

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的素数；如果不存在这样的素数，则返回 -1 。如果存在多个出现频率最高的素数，那么返回其中最大的那个。

注意：移动过程中不允许改变方向。

测试样例：

输入：mat = [[1,1],[9,9],[1,1]]

输出：19

解释：从单元格 (0,0) 出发，有 3 个可能的方向，这些方向上可以生成的大于 10 的数字有：

• 东方向: [11], 东南方向: [19], 南方向: [19,191] 。
• 从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有：[19,191,19,11] 。
• 从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有：[99,91,91,91,91] 。
• 从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有：[91,91,99,91,91] 。
• 从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,191,19] 。
• 从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有：[11,19,19,191] 。

在所有生成的数字中，出现频率最高的素数是 19 。

解答：这道题目有点Hard Code，就是各个位置强行遍历一下。需要增加的算法只有判断一个数是否是质数。因为怕数据量比较大（其实不大。。。），我加了一个HashSet来缓存所有遍历过的数字和它是否是质数的情况。

class Solution {
    private static final int[][] moves = {{0,1},{0,-1},{1,0},{1,1},{1,-1},{-1,0},{-1,1},{-1,-1}};
    private static Set<Integer> isPrime = new HashSet<>(), isMet = new HashSet<>();

    public int mostFrequentPrime(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int[] mv : moves) {
                    int x = i, y = j;
                    int curNum = 0;
                    while (x >= 0 && x < m && y >= 0 && y < n) {
                        curNum = curNum * 10 + mat[x][y];
                        if (curNum >= 10 && isPrimeNum(curNum)) {
                            count.put(curNum, count.getOrDefault(curNum, 0) + 1);
                        }
                        x += mv[0];
                        y += mv[1];
                    }
                }
            }
        }
        int res = -1, max = 0;
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            if (entry.getValue() > max) {
                max = entry.getValue();
                res = entry.getKey();
            } else if (entry.getValue() == max) {
                res = Math.max(res, entry.getKey());
            }
        }
        return res;
    }

    private boolean isPrimeNum(int n) {
        if (isMet.contains(n)) {
            return isPrime.contains(n);
        } else {
            boolean res = isPrimeNumCal(n);
            isMet.add(n);
            if (res) {
                isPrime.add(n);
            }
            return res;
        }
    }

    private boolean isPrimeNumCal(int n) {
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

100208. Count Prefix and Suffix Pairs II

给你一个下标从 0 开始的字符串数组 words 。

定义一个 布尔 函数 isPrefixAndSuffix ，它接受两个字符串参数 str1 和 str2 ：

• 当 str1 同时是 str2 的前缀（prefix）和后缀（suffix）时，isPrefixAndSuffix(str1, str2) 返回 true，否则返回 false。

例如，isPrefixAndSuffix("aba", "ababa") 返回 true，因为 "aba" 既是 "ababa" 的前缀，也是 "ababa" 的后缀，但是 isPrefixAndSuffix("abc", "abcd") 返回 false。

以整数形式，返回满足 i < j 且 isPrefixAndSuffix(words[i], words[j]) 为 true 的下标对 (i, j) 的 数量 。

测试样例：

输入：words = ["a","aba","ababa","aa"]

输出：4

解释：在本示例中，计数的下标对包括：

• i = 0 且 j = 1 ，因为 isPrefixAndSuffix("a", "aba") 为 true 。
• i = 0 且 j = 2 ，因为 isPrefixAndSuffix("a", "ababa") 为 true 。
• i = 0 且 j = 3 ，因为 isPrefixAndSuffix("a", "aa") 为 true 。
• i = 1 且 j = 2 ，因为 isPrefixAndSuffix("aba", "ababa") 为 true 。

因此，答案是 4 。

解答：这题和上周周赛其实一样，还是可以利用前缀哈希来解决。有一点需要注意，它的结果是long。我WA了好几次，最后发现用int型爆长度了。。。

class Solution {
    private static final int mod = 1_000_000_007;

    public long countPrefixSuffixPairs(String[] words) {
        HashMap<Long, Integer> set = new HashMap<>();
        long res = 0;
        for (String word : words) {
            int len = word.length();
            long left = 0, right = 0, mul = 1;
            for (int i = 0, j = len - 1; i < word.length(); ++i, --j) {
                left = (word.charAt(i) * mul + left) % mod;
                right = ((right * 331) + word.charAt(j)) % mod;
                if (left == right && set.containsKey(left)) {
                    res += set.get(left);
                }
                mul = (mul * 331) % mod;
            }
            set.put(left, set.getOrDefault(left,0) + 1);
        }
        return res;
    }
}