前言
这题很难,这题很难,但是..... 也值得学习一下,因为用到了二分和前缀hash
题目 (最长公共子路径)
https://leetcode-cn.com/problems/longest-common-subpath/
一个国家由 n 个编号为 0 到 n - 1 的城市组成。在这个国家里,每两个 城市之间都有一条道路连接。
总共有 m 个编号为 0 到 m - 1 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示,每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 重复 出现,但同一个城市在一条路径中不会连续出现。
给你一个整数 n 和二维数组 paths ,其中 paths[i] 是一个整数数组,表示第 i 个朋友走过的路径,请你返回 每一个 朋友都走过的 最长公共子路径 的长度,如果不存在公共子路径,请你返回 0 。
一个 子路径 指的是一条路径中连续的城市序列。
---------------------------------
样例:
输入:n = 5, paths = [[0,1,2,3,4],
[2,3,4],
[4,0,1,2,3]]
输出:2
解释:最长公共子路径为 [2,3]
--------------------------------
数据规模
1 <= n <= 105
m == paths.length
2 <= m <= 105
sum(paths[i].length) <= 105
0 <= paths[i][j] < n
paths[i] 中同一个城市不会连续重复出现
思路
1.怎么想到用二分
数据规模,经验(反正我做的时候没想到)
首先,数据规模1e5,所以n方算法过不了,只能优化nlogn(要不就用数据结构优化,要不就算法优化)
二分就能优化一个n
能用二分的条件是:单调性和二段性
单调性:假如2是一个解,那么1必然也是一个解,所以答案具有单调性
二段性:假如从1~9之间找最优解(最大的公共连续子数组的长度)。假如4是一个解,我需要找最优解,比4小的我都不用看,最优解必然大于等于4.
所以满足单调性和二段性,可以用整数二分来解。
因为求最长的,所以找的是右边解,用l=mid
2.check函数怎么写
判断是否都存在长度为x的连续子数组。
暴力方法不行,用的话,要一个一个比,不行。
只能hash,前缀hash很合适,因为要求很多不同连续子数组的hash。
问题:同一个路径,有相同的连续子数组怎么解决?
答:用map来排除,没出现才加,同一个一样的不加
最后把最大数量的长度为x的子数组,与路径组数比,相等则表示存在。
实现代码
问题:算hash值得hash函数要设计一下;
typedef unsigned long long ULL;
const int N = 100010;
const int BASE = 133333333331;
ULL h[N];
ULL p[N];
inline ULL get(int l, int r) {
return h[r] - h[l-1] * p[r-l+1];
}
class Solution {
public:
vector<vector<int> > _path;
unordered_map<ULL, int> curr, cnt;
// 检查是否存在长度为x的连续子数组,使用前缀hash来快速计算连续子数组是否相同
bool check(int x) {
curr.clear(),cnt.clear();
int k = 0;
for (auto &e : _path) {
//对于每个数组,预处理前缀hash数组和幂次数组p
int n = e.size();
p[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i-1] * BASE + e[i-1];
p[i] = p[i-1] * BASE;
}
// 为了防止一个数组,出现两个相同的连续子数组,用map来存储是否出现
// 遍历每个长度为x的子数组
for (int i = x; i <= n; i++) {
ULL t = get(i-x+1,i);
if (!curr.count(t) || curr[t] != k) { // 当前不能出现两个
curr[t] = k;
cnt[t]++;
}
}
k++;
}
int res = 0;
for (auto &[K, V] : cnt) res = max(res, V);
// cout << res << " ";
return res == _path.size();
}
int longestCommonSubpath(int n, vector<vector<int>>& paths) {
_path = paths;
int l = 0, r = N;
for (auto e : paths) {
r = min(r, (int)e.size());
}
int mid;
while (l < r) {
mid = (l + r + 1) >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return r;
}
};