1923. 最长公共子路径Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里，每两个城市之间都有一条道路连接。

总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能重复出现，但同一个城市在一条路径中不会连续出现。

给你一个整数 n 和二维数组 paths ，其中 paths[i] 是一个整数数组，表示第 i 个朋友走过的路径，请你返回每一个朋友都走过的最长公共子路径的长度，如果不存在公共子路径，请你返回 0 。

一个子路径指的是一条路径中连续的城市序列。

示例 1：

输入：n = 5, paths = [[0,1,2,3,4],
[2,3,4],
[4,0,1,2,3]]
输出：2
解释：最长公共子路径为 [2,3] 。

示例 2：

输入：n = 3, paths = [[0],[1],[2]]
输出：0
解释：三条路径没有公共子路径。

示例 3：

输入：n = 5, paths = [[0,1,2,3,4],
[4,3,2,1,0]]
输出：1
解释：最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。

提示：

1 <= n <= 10⁵
m == paths.length
2 <= m <= 10⁵
sum(paths[i].length) <= 10⁵
0 <= paths[i][j] < n
paths[i] 中同一个城市不会连续重复出现。

# 思路

Map<Long, Set> 处理哈希冲突

# 解法

class Solution {
    public int longestCommonSubpath(int n, int[][] paths) {
        int minLen = Integer.MAX_VALUE; for(int[] path : paths) minLen = Math.min(minLen, path.length);
        int lft = 1, rht = minLen, mid, ans = 0;
        while(lft <= rht) {
            mid = lft + (rht - lft) / 2;
            if(check(paths, mid)) {
                ans = mid;
                lft = mid + 1;
            }
            else {
                rht = mid - 1;
            }
        }
        return ans;
    }

    private boolean check(int[][] paths, int len) {
        long mod = Integer.MAX_VALUE, base1 = 100007, mult1 = 1L, base2 = 100009, mult2 = 1L;
        for(int i = 1; i <= len; ++i) {
            mult1 = mult1 * base1 % mod;
            mult2 = mult2 * base2 % mod;
        }
        Map<Long, Set<Long>> map1 = new HashMap<>();
        for(int i = 0; i < paths.length; ++i) {
            long key = 0L, val = 0L;
            for(int j = 0; j < len; ++j) {
                key = (key * base1 + paths[i][j]) % mod;
                val = (val * base2 + paths[i][j]) % mod;
            }
            Map<Long, Set<Long>> map2 = new HashMap<>();
            if(i == 0 || map1.containsKey(key) && map1.get(key).contains(val)) {
                if(!map2.containsKey(key)) map2.put(key, new HashSet<Long>());
                map2.get(key).add(val);
            }
            for(int j = len; j < paths[i].length; ++j) {
                key = ((key * base1 - (paths[i][j - len]) * mult1 + paths[i][j]) % mod + mod) % mod;
                val = ((val * base2 - (paths[i][j - len]) * mult2 + paths[i][j]) % mod + mod) % mod;
                if(i == 0 || map1.containsKey(key) && map1.get(key).contains(val)) {
                    if(!map2.containsKey(key)) map2.put(key, new HashSet<Long>());
                    map2.get(key).add(val);
                }
            }
            if(map2.isEmpty()) return false;
            map1 = map2;
        }
        return true;
    } 
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

# 总结

分析出几种情况，然后分别对各个情况实现

#Java