给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出: 3 解释: 长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
class Solution {动态二维+无伪头行列 public: int findLength(vector<int>& A, vector<int>& B) { if(A.size()==0||B.size()==0)return 0; vector<vector<int>>dp(A.size(),vector<int>(B.size(),0)); int resMax=0; for(int j=0;j<B.size();++j) dp[0][j]=A[0]==B[j]?1:0; for(int i=1;i<A.size();++i){ dp[i][0]=A[i]==B[0]?1:0; for(int j=1;j<B.size();++j) if(A[i]==B[j]){ dp[i][j]=dp[i-1][j-1]+1; resMax=max(resMax,dp[i][j]); } } return resMax; } }; class Solution {//动态一维优化+无伪头行列 public: int findLength(vector<int>& A, vector<int>& B) { if(A.size()==0||B.size()==0)return 0; vector<int>dp(B.size(),0); int resMax=0; for(int i=0;i<B.size();++i) if(A[0]==B[i])dp[i]=1; for(int i=1;i<A.size();++i){ for(int j=B.size()-1;j>=1;--j)//逆序 j:b.size()-1~1 if(A[i]==B[j]){ dp[j]=dp[j-1]+1; resMax=max(resMax,dp[j]); } else dp[j]=0;//容易漏掉 dp[0]=A[i]==B[0]?1:0;//j:0 resMax=max(resMax,dp[0]); } return resMax; } }; class Solution {//动态二维+伪头行列 public: int findLength(vector<int>& A, vector<int>& B) { if(A.size()==0||B.size()==0)return 0; vector<vector<int>>dp(A.size()+1,vector<int>(B.size()+1,0)); int resMax=0; for(int i=1;i<=A.size();++i) for(int j=1;j<=B.size();++j) if(A[i-1]==B[j-1]){ dp[i][j]=dp[i-1][j-1]+1; resMax=max(resMax,dp[i][j]); } return resMax; } }; class Solution {//动态一维+伪头 public: int findLength(vector<int>& A, vector<int>& B) { if(A.size()==0||B.size()==0)return 0; vector<int>dp(B.size()+1,0);// int resMax=0; for(int i=1;i<=B.size();++i) if(A[0]==B[i-1])dp[i]=1; for(int i=2;i<=A.size();++i) for(int j=B.size();j>=1;--j) if(A[i-1]==B[j-1]){ dp[j]=dp[j-1]+1; resMax=max(resMax,dp[j]); } else dp[j]=0;// return resMax; } };
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
注意: 字符串长度 和 k 不会超过 104。
示例 1:
输入: s = "ABAB", k = 2
输出: 4
解释: 用两个'A'替换为两个'B',反之亦然。
示例 2:
输入: s = "AABABBA", k = 1
输出: 4
解释: 将中间的一个'A'替换为'B',字符串变为 "AABBBBA"。 子串 "BBBB" 有最长重复字母, 答案为 4。
class Solution { public: int characterReplacement(string s, int k) { if(s.size()<=1)return s.size(); unordered_map<char,int>windows; int le=0,ri=0; int maxCnt=0; int res=0; while(ri<s.size()){ char c=s[ri++]; ++windows[c]; maxCnt=max(maxCnt,windows[c]); if(ri-le<=maxCnt+k)res=max(res,ri-le); if(ri-le>maxCnt+k){ char c=s[le++]; if(windows[c]--==maxCnt)--maxCnt; } } return res; } }; 为什么maxCnt减小时可以不更新。 right++时，窗口扩大， left++，right++时,窗口大小不变，窗口平移。 可以看出 窗口并不会缩小。 代码最终返回的结果是最大的窗口大小，我们找的是最大的窗口，只有maxCnt变大，窗口才可以扩大；maxCnt减小对窗口的大小没有什么影响，所以不更新也可以。
