424. 替换后的最长重复字符
给你一个仅由大写英文字母组成的字符串，你可以将任意位置上的字符替换成另外的字符，总共可最多替换 k 次。在执行上述操作后，找到包含重复字母的最长子串的长度。
如果我们按序遍历每个字符开始计算符合条件的子串长度，对于每个子串，我们只需要以它的第一个字符为不变字符。思路简单，代码清晰，耗时巨长，加了一个遇连续相同字符直接跳过，以及i到达的字符开始的子串不可能为最大时结束，才勉强AC
int characterReplacement(string s, int k) { int n=s.length(); int ans=0; for(int i=0;i<s.length();i++){ if(i>0&&s[i]==s[i-1])continue; if(s.length()-i+k<=ans)return ans; char c=s[i]; int tmp=0; for(int j=i+1;j<s.length();j++){ if(s[j]!=c)tmp++; if(tmp>k){ ans=max(ans,j-i); break; } } if(tmp<=k) ans=max(ans,min((int)s.length(),(int)s.length()-i+k-tmp)); } return ans; }
这题是典型的双指针问题，或者，滑动窗口问题。不需要保存每一个窗口内的字母出现的最大值，因为字母一定是从右边新添的字符里出现，而且只有当窗口内出现了比历史更多的字母数时，答案才会更新，也就是maxCnt不需要是实时的最大字母数。
int characterReplacement(string s, int k) { int n=s.length(); int ans=0,left=0,maxCnt=0; vector<int> letter(26,0); for(int i=0;i<s.length();i++){ letter[s[i]-'A']++; maxCnt=max(maxCnt,letter[s[i]-'A']); if(i-left+1-maxCnt>k){ letter[s[left]-'A']--; left++; } ans=max(ans,i-left+1); } return ans; }
457. 环形数组循环
给定一个含有正整数和负整数的环形数组 nums。 如果某个索引中的数 k 为正数，则向前移动 k 个索引。相反，如果是负数 (-k)，则向后移动 k 个索引。因为数组是环形的，所以可以假设最后一个元素的下一个元素是第一个元素，而第一个元素的前一个元素是最后一个元素。
确定 nums 中是否存在循环（或周期）。循环必须在相同的索引处开始和结束并且循环长度 > 1。此外，一个循环中的所有运动都必须沿着同一方向进行。换句话说，一个循环中不能同时包括向前的运动和向后的运动。
原方法：
用一个数组vis记录
vis[i]=k表示 结点 i 是从下标 k 为起始点出发所能到达的路径上的点
每次从未探索过的i出发找大于1的环
bool circularArrayLoop(vector<int>& nums) { int n=nums.size(); vector<int> vis(n,-1); for(int i=0;i<n;i++) { if(vis[i]>=0&&vis[i]<i)continue; int t=i; bool flag=nums[i]>0?true:false; while(flag==(nums[t]>0)){ //flag保证同方向 if(vis[t]==i){ int len=0; int k=(t+nums[t]+n)%n; while(k<0)k=(k+n); //保证下标为正 while(k!=t){ k=(k+nums[k]+n)%n; while(k<0) k=(k+n); len++; if(len>0) return true; } //计算环的长度 break; //从i出发仅有1单位长度的环，继续从i+1开始找 } if(vis[t]!=-1)break; //跑到之前走过的路上去了，之前无解，这次也无解 vis[t]=i; t=(t+n+nums[t])%n; while(t<0)t=(t+n); } } return false; }
改进方法：既然是双指针的问题，又有环，那快慢指针肯定没跑了
int idx(int i, int dx,int n){ if(dx>0)return (i+dx)%n; else return (i-abs(dx)%n+n)%n; } bool circularArrayLoop(vector<int>& nums) { int n=nums.size(); vector<int> vis(n,-1); for(int i=0;i<n;i++) { if(vis[i]!=-1)continue; int slow=i,fast=i; while(nums[slow]*nums[fast]>0&&nums[slow]*nums[idx(fast,nums[fast],n)]>0){ slow=idx(slow,nums[slow],n); if(vis[slow]!=-1&&vis[slow]!=i)break;vis[slow]=i; fast=idx(fast,nums[fast],n); if(vis[fast]!=-1&&vis[fast]!=i)break;vis[fast]=i; fast=idx(fast,nums[fast],n); if(vis[fast]!=-1&&vis[fast]!=i)break;vis[fast]=i; if(fast==slow){ if(idx(slow,nums[slow],n)!=slow)return true; break; } } } return false; }
待更新。。。