方法二:滑动窗口:枚举 A 和 B 所有的对齐方式。对齐的方式有两类:第一类为 A 不变,B 的首元素与 A 中的某个元素对齐;第二类为 B 不变,A 的首元素与 B 中的某个元素对齐。对于每一种对齐方式,计算它们相对位置相同的重复子数组即可。时间复杂度: O((N+M)×min(N,M)) 。
方法三:如果数组 A 和 B 有一个长度为 k 的公共子数组,那么它们一定有长度为 j≤k 的公共子数组。这样我们可以通过二分查找的方法找到最大的 k。而为了优化时间复杂度,在二分查找的每一步中,使用哈希的方法来判断数组 A 和 B 中是否存在相同特定长度的子数组。(搬运一下官网的讲解)
intfindLength(vector<int>& A,vector<int>& B) {int ret =0;intdp[B.size() +1][A.size() +1];memset(dp,0,sizeof(dp));for(int i =B.size() -1; i >=0; i --){for(int j =A.size() -1; j >=0; j --){if(B[i] ==A[j]){dp[i][j] =dp[i +1][j +1] +1; } ret = std::max(ret,dp[i][j]); } }return ret;}intfindLength(vector<int>& A,vector<int>& B) {int ret =0;intdp[B.size() +1][A.size() +1];memset(dp,0,sizeof(dp));for(int i =1; i <=A.size(); i ++){for(int j =1; j <=B.size(); j ++){if(B[i -1] ==A[j -1]){ // i 只与 i - 1 有关dp[i][j] =dp[i -1][j -1] +1; }else{dp[i][j] =0; } ret = std::max(ret,dp[i][j]); } }return ret;}// 优化到一维数组:第二层for循环我们使用的倒序的方式,这是因为dp数组后面的值会依赖// 前面的值,而前面的值不依赖后面的值,所以后面的值先修改对前面的没影响,但前面的值// 修改会对后面的值有影响,所以这里要使用倒序的方式。intfindLength(vector<int>& A,vector<int>& B) {int ret =0;intdp[B.size() +1];memset(dp,0,sizeof(dp));for(int i =0; i <A.size(); i ++){for(int j =B.size(); j >0; j --){if(A[i] ==B[j -1]){dp[j] =dp[j -1] +1; }else{dp[j] =0; } ret = std::max(ret,dp[j]); } }return ret;}
intfindLength(vector<int>& A,vector<int>& B) {int ret =0;int m =A.size(), n =B.size();for(int i =0; i < m; i ++){int p = i, q =0;int len =0;while(p < m && q < n){ len =A[p] ==B[q] ? len +1:0; ret =max(ret, len); p++, q++; } }for(int i =0; i < n; i ++){int p = i, q =0;int len =0;while(p < n && q < m){ len =B[p] ==A[q] ? len +1:0; ret =max(ret, len); p++, q++; } }return ret;}// 滑动窗口算法有个小优化,每次对齐后可以计算一下长度len是否已经小于或等于结果ret,// 如果是,那我们就不用继续循环计算了,因为后面肯定没有更长的。
int base =113;int mod =1e9+7;// 求pow(base, len - 1),注意溢出问题longhelper(int i){long res =1;long ref = base;while(i !=0){ //如果是奇数次幂,先抽一个底数出来,提前乘到结果中if(i %2!=0){ res = (res * ref) % mod; } //底数平方,幂减半 ref = (ref * ref) %mod; i /=2; }return res;}// 检验是否存在长度为len的公共子数组boolcheck(std::vector<int>& A, std::vector<int>& B,int len){ // 算出A[0, len - 1]的哈希值long hashA =0;for(int i =0; i < len; i++) hashA = (hashA * base +A[i]) % mod; unordered_set<int> setA;setA.insert(hashA); // 根据公式递推后面对应长度的哈希值,并存入哈希表long ref =helper(len -1) ;for(int i =0; i <A.size() - len; i ++){ // +mod 是为了保证 hashA 大于0 hashA = ((hashA -A[i] * ref % mod + mod) % mod * base +A[i + len]) % mod;setA.insert(hashA); } // 同样的方式处理B数组long hashB =0;for(int i =0; i < len; i++) hashB = (hashB * base +B[i]) % mod;if(setA.count(hashB))returntrue;for(int i =0; i <B.size() - len; i++){ hashB = ((hashB -B[i] * ref % mod + mod) % mod * base +B[i + len]) % mod;if(setA.count(hashB))returntrue; }returnfalse;}intfindLength(vector<int>& A,vector<int>& B) { // [left, right]是所有可能不存在“对应长度的公共子数组”的集合 // (0是一定存在的,所以left从1开始,min(A.size() , B.size()) + 1 // 是一定不存在的,所以也需要包含在内)int left =1;int right =min(A.size(),B.size()) +1;while(left < right){int mid = left + (right - left) /2;if(check(A, B, mid)) left = mid +1;else right = mid; }return left -1;}
思路一:动态规划: dp[i] 表示以第 i 个数字结尾的最长上升子序列的长度,nums[i]必须被选取。则状态转移方程为:
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]
思路二:二分查找:
intlengthOfLIS(vector<int>& nums) {if(nums.empty())return0; vector<int>dp(nums.size(),1);int ret =1;for(int i =1; i <nums.size(); i ++){int j = i -1;for(; j >=0; j --){if(nums[i] >nums[j]){dp[i] =max(dp[i],dp[j] +1); } } ret =max(ret,dp[i]); }return ret;}