LeetCode-385

本篇核心词: Z函数

Q2

最长公共前缀的长度

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

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

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

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

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

示例 1：

输入：arr1 = [1,10,100], arr2 = [1000]
输出：3
解释：存在 3 个数对 (arr1[i], arr2[j]) ：
- (1, 1000) 的最长公共前缀是 1 。
- (10, 1000) 的最长公共前缀是 10 。
- (100, 1000) 的最长公共前缀是 100 。
最长的公共前缀是 100 ，长度为 3 。

示例 2：

输入：arr1 = [1,2,3], arr2 = [4,4,4]
输出：0
解释：任何数对 (arr1[i], arr2[j]) 之中都不存在公共前缀，因此返回 0 。
请注意，同一个数组内元素之间的公共前缀不在考虑范围内。

提示：

• 1 <= arr1.length, arr2.length <= 5 * 104
• 1 <= arr1[i], arr2[i] <= 108

保存arr1的所有前缀，在arr2中判断是否存在，存在更新最大值即可。

class Solution:
    def longestCommonPrefix(self, arr1: List[int], arr2: List[int]) -> int:
        s = set()
        for x in arr1:
            c = str(x)
            n = len(c)
            for i in range(1, n + 1):
                s.add(c[:i])
        ans = 0
        for x in arr2:
            c = str(x)
            n = len(c)
            for i in range(1, n + 1):
                if c[:i] in s:
                    ans = max(ans, i)
        return ans

Q3

出现频率最高的质数

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

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

返回在遍历矩阵所创建的所有数字中，出现频率最高的、大于 10的

质数

；如果不存在这样的质数，则返回 -1 。如果存在多个出现频率最高的质数，那么返回其中最大的那个。

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

示例 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 。

示例 2：

输入：mat = [[7]]
输出：-1
解释：唯一可以生成的数字是 7 。它是一个质数，但不大于 10 ，所以返回 -1 。

示例 3：

输入：mat = [[9,7,8],[4,6,5],[2,8,6]]
输出：97
解释： 
从单元格 (0,0) 出发，所有可能方向上生成的大于 10 的数字有: [97,978,96,966,94,942] 。
从单元格 (0,1) 出发，所有可能方向上生成的大于 10 的数字有: [78,75,76,768,74,79] 。
从单元格 (0,2) 出发，所有可能方向上生成的大于 10 的数字有: [85,856,86,862,87,879] 。
从单元格 (1,0) 出发，所有可能方向上生成的大于 10 的数字有: [46,465,48,42,49,47] 。
从单元格 (1,1) 出发，所有可能方向上生成的大于 10 的数字有: [65,66,68,62,64,69,67,68] 。
从单元格 (1,2) 出发，所有可能方向上生成的大于 10 的数字有: [56,58,56,564,57,58] 。
从单元格 (2,0) 出发，所有可能方向上生成的大于 10 的数字有: [28,286,24,249,26,268] 。
从单元格 (2,1) 出发，所有可能方向上生成的大于 10 的数字有: [86,82,84,86,867,85] 。
从单元格 (2,2) 出发，所有可能方向上生成的大于 10 的数字有: [68,682,66,669,65,658] 。
在所有生成的数字中，出现频率最高的质数是 97 。

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 6
• 1 <= mat[i][j] <= 9

对于每个位置，8个方向都模拟一遍，求最大频率质数即可。

class Solution:
    def mostFrequentPrime(self, mat: List[List[int]]) -> int:

        cnt = Counter()

        def is_prime(x: int) -> bool:
            if x < 2:
                return False
            k = 2
            while k * k <= x:
                if x % k == 0: return False
                k += 1
            return True

        n, m = len(mat), len(mat[0])
        d = [(0, 1), (1, 0), (0, -1), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for i in range(n):
            for j in range(m):
                if mat[i][j] > 10 and is_prime(mat[i][j]): cnt[mat[i][j]] += 1
                for dx, dy in d:
                    sx, sy, t = i, j, mat[i][j]
                    while 0 <= sx + dx < n and 0 <= sy + dy < m:
                        sx, sy = sx + dx, sy + dy
                        t = t * 10 + mat[sx][sy]
                        if t > 10 and is_prime(t): cnt[t] += 1
        ans, mxv = -1, 0
        for k, v in cnt.items():
            if v > mxv or v == mxv and k > ans:
                ans = k
                mxv = v
        return ans

Q1&Q4

统计前后缀下标对

给你一个下标从 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) 的 数量 。

示例 1：

输入：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 。

示例 2：

输入：words = ["pa","papa","ma","mama"]
输出：2
解释：在本示例中，计数的下标对包括：
i = 0 且 j = 1 ，因为 isPrefixAndSuffix("pa", "papa") 为 true 。
i = 2 且 j = 3 ，因为 isPrefixAndSuffix("ma", "mama") 为 true 。
因此，答案是 2 。

示例 3：

输入：words = ["abab","ab"]
输出：0
解释：在本示例中，唯一有效的下标对是 i = 0 且 j = 1 ，但是 isPrefixAndSuffix("abab", "ab") 为 false 。
因此，答案是 0 。

提示：

• 1 <= words.length <= 105
• 1 <= words[i].length <= 105
• words[i] 仅由小写英文字母组成。
• 所有 words[i] 的长度之和不超过 5 * 105 。

字典树+z函数。这也是我第一次学习z函数算法。

对于一个长度为$n$的字符串$s$,定义函数z[i]表示s和s[i, n - 1]的lcp,z被成为z函数。特别的，z[0] = 0

对于本题而言，可以使用字典树，一边存一边对于每个字符串的前缀进行查询有多少个字符串与其相同，需要保证的是，此字符串的前缀必须和后缀相同，如果能够处理每个字符串的每个位置的前缀是否与其后缀完全相同，就简单多了。对于处理方法可以使用z函数(完全符合z函数的定义)，使用字符串hash也是可以的。

关于z函数的理解，若过端点位于zbox内的话，就可以使用之前的值来更新zbox,找到i - l的z[i]这个代表之前的可以最多匹配多少，还需判断这个值是否超过的zbox的长度(r - i + 1)，取两者最小值。之后就是暴力匹配了。

import java.util.ArrayList;
import java.util.List;

class Solution {


    static class Node {
        Node[] nodes = new Node[26];

        long cnt;
    }


    Node root = new Node();

    void add(String s) {
        Node temp = root;
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            int c = aChar - 'a';
            if (temp.nodes[c] == null) temp.nodes[c] = new Node();
            temp = temp.nodes[c];
        }
        temp.cnt++;
    }

    long get(String s, int[] z) {
        Node temp = root;
        long ret = 0;
        int n = s.length();
        char[] chars = s.toCharArray();
        for (int i = 0; i < n; i++) {
            int c = chars[i] - 'a';
            if (temp.nodes[c] == null) return ret;
            if (i == n - 1 || z[n - i - 1] == i + 1) ret += temp.nodes[c].cnt;
            temp = temp.nodes[c];
        }
        return ret;
    }

    public long countPrefixSuffixPairs(String[] words) {
        List<int[]> list = sHash(words);

        long ans = 0;
        for (int i = 0; i < words.length; i++) {
            ans += get(words[i], list.get(i));
            add(words[i]);
        }
        return ans;
    }

    public List<int[]> zFunc(String[] words) {
        List<int[]> zList = new ArrayList<>();
        for (String string : words) {
            char[] s = string.toCharArray();
            int n = s.length;
            int[] z = new int[n];
            for (int i = 1, l = 0, r = 0; i < n; ++i) {
                if (i <= r && z[i - l] < r - i + 1) {
                    z[i] = z[i - l];
                } else {
                    z[i] = Math.max(0, r - i + 1);
                    while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
                }
                if (i + z[i] - 1 > r) {
                    l = i;
                    r = i + z[i] - 1;
                }
            }
            zList.add(z);
        }
        return zList;
    }

    public List<int[]> sHash(String[] words) {
        List<int[]> list = new ArrayList<>();
        int P = 233;
        for (var word : words) {
            int n = word.length();
            int[] p = new int[n + 1], h = new int[n + 1];
            p[0] = 1;
            for (int i = 1; i <= n; i++) {
               p[i] = p[i - 1] * P;
               h[i] = h[i - 1] * P + word.charAt(i - 1);
            }
            int[] k = new int[n];
            for (int i = 1; i < n; i++) {
                if (h[n] - h[i] * p[n - i] == h[n - i] - h[0] * p[n - i]) k[i] = n - i;  //和z函数保持一致
            }
            list.add(k);
        }
        return list;
    }
}