百度收录网站技巧,产品市场调研怎么做,如何搜索公司所有的网站,数字营销沙盘大赛写在前面#xff1a;此篇博客是以[双指针总结]博客为基础的针对性训练#xff0c;题源是codetop标签双指针近一年#xff0c;频率由高到低 1.无重复字符的最长子串2.三数之和3.环形链表4.合并两个有序数组5.接雨水6.环形链表II7.删除链表的倒数第N个节点8.训练计划II9.最小覆… 写在前面此篇博客是以[双指针总结]博客为基础的针对性训练题源是codetop标签双指针近一年频率由高到低 1.无重复字符的最长子串2.三数之和3.环形链表4.合并两个有序数组5.接雨水6.环形链表II7.删除链表的倒数第N个节点8.训练计划II9.最小覆盖子串10.回文链表11.长度最小的子数组12.移动零13.盛水最多的容器14.旋转链表15.最接近的三数之和16.删除有序数组中的重复项17. 返回倒数第k个节点的值18. 四数之和19.验证回文串20.字符串的排列21.找出字符串中第一个匹配的下标22.最大连续1的个数II23.数组中的山脉24.移除元素25.两个数组的交集II26.有序数组的平方27.删除有序数组中的重复项II28.寻找重复数29 .水果成篮30.和为k的子数组31.统计[优美子数组]32.区间列表的交集33.将x减到0的最小操作34.替换子串得到平衡字符串35.划分字母区间36.分隔链表 不二刷三刷就是没刷过!!不二刷三刷就是没刷过!!不二刷三刷就是没刷过!!重要的事情说三遍!!!
1.无重复字符的最长子串
之前学习双指针的总结在这里传送门-双指针总结
在传送门里有一个题是无重复数字的最长子串 是差不多的简单哒没事哒
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_mapchar, int a;//map来记录s某个字符出现多少次int j 0;//双指针维护的数组是[ji]int r 0;//r是最大长度不断更新for(int i 0; i s.size(); i ){//i是维护数组的右边界a[s[i]] ;//记录每个s[i]出现的次数while(a[s[i]] 1){//一旦重复出现了那么重复的一定是s[i],因为[j i-1]是维护好了的-- a[s[j ]];//一遍让j往前推一遍减掉不在维护数组[ji]内的字符次数}r max(r, i - j 1);}return r;}
};2.三数之和
还是上一题传送门里面有原题讲解这里再贴一遍代码
class Solution {
public:vectorvectorint threeSum(vectorint nums) {sort(nums.begin(), nums.end());vectorvectorint res;for(int i 0; i nums.size(); i ){if(i nums[i] nums[i - 1]) continue;for(int j i 1, k nums.size() - 1; j k; j ){if(j i 1 nums[j] nums[j - 1]) continue;while(j k nums[i] nums[j] nums[k] 0) k --;if(j k nums[i] nums[j] nums[k] 0) res.push_back({nums[i], nums[j], nums[k]});}}return res;}
};3.环形链表
很意外的没有一次通过这一题在传送门里面也有纯原题 主要是while(fast!NULL fast-next ! NULL fast-next-next ! NULL) 一开始写成了while(fast!NULL fast-next-next ! NULL) 不可以跳过fast-next直接判断fast-next-next如果fast-next NULL 会触发未定义错误
class Solution {
public:bool hasCycle(ListNode *head) {if(head NULL || head-next NULL) return false;ListNode* slow head;ListNode* fast head-next;while(fast!NULL fast-next ! NULL fast-next-next ! NULL){if(slow fast) return true;fast fast-next-next;slow slow-next;}return false;}
};4.合并两个有序数组
两个非递减顺序排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。 请你合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
要求合并到nums1数组内需要考虑两个边界oldIndex和p2如果p2为空了剩下的nums1根本不用动可以直接返回所以这里while语句里面应该是p20 这里稍微debug了一会还是得先想清楚再敲
class Solution {
public:void merge(vectorint nums1, int m, vectorint nums2, int n) {int oldIndex m - 1; // 最后一个有效元素的位置int newIndex m n - 1; // 合并后最后一个位置int p2 n - 1; // nums2的最后一个元素的位置while (p2 0) {if (oldIndex 0 nums1[oldIndex] nums2[p2]) {nums1[newIndex--] nums1[oldIndex--];} else {nums1[newIndex--] nums2[p2--];}}}
};5.接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。 找凹槽在单调栈的一篇文秒杀整个题型里面也有这个题-传送门
class Solution {
public:int trap(vectorint height) {stackint s;vectorint res;int sum 0;for(int i 0; i height.size(); i ){while(!s.empty() height[s.top()] height[i]){int mid height[s.top()];s.pop();if(!s.empty()){int h min(height[s.top()], height[i]) - mid;int w i - s.top() - 1;sum h * w;}}s.push(i);}return sum;}
};6.环形链表II
秒杀系列里面的原题 没有秒杀耻辱的忘记怎么做了罚自己手写思路
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head NULL || head-next NULL) return NULL;ListNode* slow head;ListNode* fast head;while(fast!NULL fast-next!NULLfast-next-next!NULL){slow slow-next;fast fast-next-next;if(slow fast){ListNode* p2 slow;ListNode* p1 head;while(p1 ! p2){p1 p1-next;p2 p2-next;}return p1;}}return NULL;}
};7.删除链表的倒数第N个节点
还是双指针传送门的原题秒了 但是有个地方当时写题解其实没有太明白
dummy的必要性为了同一删除操作假如链表长度是n又要删除倒数第n个节点即头结点加了dummy就不需要单独讨论了为什么in注意最后的while(fast)这个地方当fast来到了表尾还是能进入循环的fast再走一步是空slow还能再走这样正好可以删除所以必须slow和fast中间空出两个元素
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy new ListNode(0);dummy-next head;ListNode* slow dummy;ListNode* fast dummy;for(int i 0; i n; i ){fast fast-next;}while(fast){fast fast-next;slow slow-next;}ListNode* p slow-next;slow-next slow-next-next;delete p;ListNode* newHead dummy-next;delete dummy;return newHead;}
};8.训练计划II
这题时间复杂度卡的很松
class Solution {
public:ListNode* trainingPlan(ListNode* head, int cnt) {if(!head) return NULL;int len 1;//记录链表长度.ListNode *p head;while(p-next){len;p p-next;}p head;while(len - cnt){p p-next;len --;}return p;}
};9.最小覆盖子串
很意外为什么出现在双指针的标签下 这题考的滑动窗口 紧急写了篇滑动窗口的秒杀文章-传送门 二刷有个容易没注意到的地方 缩小窗口的时候必须先判断valid– 再window–
class Solution {
public:string minWindow(string s, string t) {unordered_mapchar, int window;unordered_mapchar, int need;for(char c : t) need[c];int start 0;int len INT_MAX;int left 0;int right 0;int valid 0;while(right s.size()){char c s[right];right;if(need.count(c)){window[c];if(window[c] need[c]) valid;}while(valid need.size()){if(right - left len){start left;len right - left;}char a s[left];left;if(need.count(a)){if(window[a] need[a]) valid--;window[a]--;}}}return len INT_MAX ? : s.substr(start, len);}
};10.回文链表
给你一个单链表的头节点 head 请你判断该链表是否为 回文链表。如果是返回 true 否则返回 false 。 力扣234. 思路不难但是好多细节需要注意 首先不能用双指针总结找中间的节点的办法因为那个主要是保证fast能走到底并且slow是会走到双数链表的中间节点靠右第二个 而这题主要是找中点并且应该是靠左那个 所以直接-next-next就好这样的fast不一定走到底但是也不用管了 找到中点之后将slow后面的指针指向翻转 最后从两边走到中间去比较 用while(p2)判断是否走完因为p2指的是更短那根可以把奇数链表中间多余节点忽略掉
class Solution {
public:bool isPalindrome(ListNode* head) {//找中点ListNode* slow head;ListNode* fast head;while(fast ! NULL fast-next ! NULL fast-next-next !NULL){fast fast-next-next;slow slow-next;}//slow在的位置就是中点奇数的话就是中间的数偶数的话就是中间两个左边的数//反转中点右边的链表ListNode* pre NULL;ListNode* cur slow-next;while(cur){ListNode* temp cur-next;cur-next pre;pre cur;cur temp;}slow-next NULL;//比较两部分链表第一条从head开始第二条从pre开始这个时候的cur已经是空了//从两边开始避免了奇数中间那个多余数的比较//要么一样长要么第二条短所以while(p2)ListNode* p1 head;ListNode* p2 pre;while(p2){if(p2-val ! p1-val) return false;p2 p2-next;p1 p1-next;}return true;}
};11.长度最小的子数组 考滑动窗口的 要注意是大于等于不是等于 看错题目一顿调
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left 0;int right 0;int sum 0;int len INT_MAX;while(right nums.size()){sum nums[right];right;while(sum target){len min(len, right - left);sum - nums[left];left ;}}return len INT_MAX ? 0 : len;}
};12.移动零 非0元素前移这和秒杀双指针里面的移除特定元素是一样的 最后别忘了填充
class Solution {
public:void moveZeroes(vectorint nums) {//非0前移int slow 0;for(int fast 0; fast nums.size(); fast ){if(nums[fast] ! 0){nums[slow] nums[fast];slow;}}//剩下部分填充0for(; slow nums.size(); slow ) nums[slow] 0;}
};13.盛水最多的容器
双指针秒杀里面的原题
class Solution {
public:int maxArea(vectorint height) {int left 0, right height.size() - 1;int r 0;while(left right){r max(r, min(height[right], height[left]) * (right - left));if(height[left] height[right]) left ;else right --;}return r;}
};14.旋转链表 整体思路是将链表头尾连起来再在新的表尾处砍断 里面有非常多的小细节比如 k k % length; 寻找新的表尾成环右移k个说明链表倒数第k个会变成表头for (int i 0; i length - k - 1; i)可以定位到表头前面一个也就是表尾
class Solution {
public:ListNode* rotateRight(ListNode* head, int k) {if (!head || !head-next || k 0) return head;// 第一步计算链表长度并形成环形链表ListNode* lastNode head;int length 1;while (lastNode-next) {lastNode lastNode-next;length;}lastNode-next head; // 形成环形链表// 第二步计算实际需要移动的步数k k % length;if (k 0) {lastNode-next NULL; // 恢复链表return head;}// 第三步找到新的头节点和尾节点ListNode* newTail head;for (int i 0; i length - k - 1; i) {newTail newTail-next;}ListNode* newHead newTail-next;// 断开链表newTail-next NULL;return newHead;}
};
15.最接近的三数之和 别人写的代码怎么这么优雅┭┮﹏┭┮ 重点在于判断最近的用abs绝对值 if(abs(target - close) abs(target - closeNum)) closeNum close close是当前的三个元素closeNum是最接近的初始化为nums[0] nums[1] nums[2]
这个return的是和重复不重复只是降低复杂度不会改变答案不用像三数之和一样死扣不重复
class Solution {
public:int threeSumClosest(vectorint nums, int target) {sort(nums.begin(), nums.end());int closeNum nums[0] nums[1] nums[2];for(int i 0; i nums.size(); i ){if(i nums[i] nums[i - 1]) continue;int left i 1, right nums.size() - 1;while(left right){int close nums[i] nums[left] nums[right];if(abs(target - close) abs(target - closeNum)) closeNum close;if(close target) right--;else if(close target) left;else return target;}}return closeNum;}
};16.删除有序数组中的重复项 快慢指针一开始没能灵活应用还得练
class Solution {
public:int removeDuplicates(vectorint nums) {int slow 0, fast 1;while(fast nums.size()){if(nums[slow] nums[fast]){fast;}else{slow;nums[slow] nums[fast];}}return slow 1;}
};17. 返回倒数第k个节点的值
假如链表长度是k返回倒数第k个的情况要留意处理 这题题目给的k一定是合理的
class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode* slow head;ListNode* fast head;// fast 指针先前进 k 步for (int i 0; i k; i) {fast fast-next;}// 同时前进 slow 和 fast直到 fast 到达链表末尾while (fast ! nullptr) {fast fast-next;slow slow-next;}// 此时 slow 所指向的即为倒数第 k 个节点return slow-val;}
};18. 四数之和
双指针秒杀原题
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {sort(nums.begin(), nums.end());vectorvectorint res;for(int i 0; i nums.size(); i ){if(i nums[i] nums[i - 1]) continue;for(int j i 1; j nums.size(); j ){if(j i 1 nums[j] nums[j - 1]) continue;for(int k j 1, u nums.size() - 1; k u; k ){//双指针if(k j 1 nums[k] nums[k - 1]) continue; while(k u (long long)nums[i] nums[j] nums[k] nums[u] target) u--;if(k u (long long)nums[i] nums[j] nums[k] nums[u] target) res.push_back({nums[i], nums[j], nums[k], nums[u]});}}}return res;}
};19.验证回文串 先把所有字符转化成小写并过滤掉空格和标点这类字符。然后对剩下的字符执行双指针中的两端向中心的双指针算法即可。
新学到的库函数
isalnum( c )isalnum 检查字符c是不是字母或者数字如果是的话返回true不是的话返回falsetolower( c )tolower 将字符 c 转换为小写字母。如果 c 本身是小写字母或非字母字符返回值将与 c 相同。
class Solution {
public:bool isPalindrome(string s) {string sb;for(int i 0; i s.size(); i ){char c s[i];if(isalnum(c)){sb tolower(c);}}//双指针两头往中间验证s sb;int left 0, right sb.size() - 1;while(left right){if(sb[left] ! sb[right]) return false;left;right--;}return true;}
};20.字符串的排列
在滑动窗口总结文章里面讲解过了 秒啦
class Solution {
public:bool checkInclusion(string s1, string s2) {unordered_mapchar, int window, need;for(char c : s1) need[c] ;int left 0, right 0;int valid 0;while(right s2.size()){char c s2[right];right;if(need.count(c)){window[c];if(need[c] window[c]) valid;}while(right - left s1.size()){char d s2[left];left ;if(need.count(d)){if(need[d] window[d]) valid--;window[d]--;}}if(need.size() valid right - left s1.size()){return true;}}return false;}
};21.找出字符串中第一个匹配的下标 拿到手的第一想法就是滑动窗口输出left 但是这个要求顺序完全一样不能是排列或者组合 查了一下KMP是专门弄这种的学习新算法了(我只是来做双指针的…)这篇文章是个纯刷题记录不贴详细讲解最多记录大致思路需要讲解去秒杀直接部分-传送门
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size();int m needle.size();vectorint ne(m, -1);// 建next数组for(int i 1, j -1; i m; i ){while(j ! -1 needle[i] ! needle[j 1]) j ne[j];if(needle[i] needle[j 1]) j ;ne[i] j;}// 匹配for(int i 0, j -1; i n; i ){while(j ! -1 haystack[i] ! needle[j 1]) j ne[j];if(haystack[i] needle[j 1]) j ;if(j m - 1){return i - m 1;}}return -1;}
};22.最大连续1的个数II
不是家人们滑动窗口为什么都划到双指针标签下了啊 题 给定一个二进制数组 nums 和一个整数 k如果可以翻转最多 k 个 0 则返回 数组中连续 1 的最大个数 。 eg 输入nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出6 在秒杀系列的滑动窗口秒杀文章里面写过 用滑动窗口做题需要先明白3个问题
什么时候扩大窗口更改什么数据什么时候缩小窗口更改什么数据什么时候得到答案
针对123的答案
当可替换次数k0的时候扩大窗口更改窗口里面1的个数让窗口里面都是1等于0的时候也扩万一窗口外面不需要改呢。当可替换次数k0的时候缩小窗口可替换次数以便继续扩大k0的时候窗口内部都是1len更新
class Solution {
public:int longestOnes(vectorint nums, int k) {int left 0, right 0;int windowOneCount 0;int res 0;while(right nums.size()){//right是0也,是1就windowOneCount,自身也if(nums[right] 1){windowOneCount ;}right ;//窗口里面0的个数超过了k,就开始缩小窗口while(right - left - windowOneCount k){if(nums[left] 1) windowOneCount --;left ;}res max(res, right - left);}return res;}
};23.数组中的山脉 先找到可能得山顶再双指针两边扩展记录res 留意lri的边界
class Solution {
public:int longestMountain(vectorint arr) {int l 0, r 0, res 0;for(int i 1; i arr.size() - 1; i ){if(arr[i] arr[i - 1] arr[i] arr[i 1]){l i - 1;r i 1;while(l 0 arr[l] arr[l - 1]) l --;while(r arr.size() - 1 arr[r] arr[r 1]) r ;res max(res, r - l 1);}}return res;}
};24.移除元素
移除val返回新数组的长度 双指针里也有这题秒啦
class Solution {public int removeElement(int[] nums, int val) {int i 0;for (int n : nums)if (n ! val) {nums[i] n;i;}return i;}
}25.两个数组的交集II
给nums1和nums2以数组的形式返回两数组里都存在的数并且这个数的次数要等于两个数组中这个数出现次数更少的那个
别人的代码是真的优雅 这个代码先记录了nums1中每个元素出现的次数到umap中 再在nums2中for每个元素 如果元素在umap中有记录则将其push进res并且umap记录数–
假如nums1中才是数字出现少的那个那么umap[nums1]会先到0以至于res不了nums2的元素假如nums2才是数字出现少的那个那么if(nums2)会先空
太优雅了o(╥﹏╥)o
class Solution {
public:vectorint intersect(vectorint nums1, vectorint nums2) {unordered_mapint, int umap;vectorint res;for(int i 0; i nums1.size(); i ) umap[nums1[i]];for(int i 0; i nums2.size(); i ){if(umap[nums2[i]]){res.push_back(nums2[i]);umap[nums2[i]] --;}}return res;}
};26.有序数组的平方
给一个非递减的数组现在需要你将每个元素都平方然后递增排序返回nums。注意需要时间复杂度是O(n) sort的家伙以后面试也排人后面 sort的复杂度是O(nlogn)所以不能用sort只能用双指针
这里有个十分关键的点就是原本的数组本身就是有序的是一个非递减的数组那么即使数组中元素有正有负绝对值最大的元素肯定是在数组的两端的即数组平方的最大值是在数组的两端的。
所以我们可以使用两个双指针i,j一个指向起始位置一个指向数组的末尾。 定义一个新的数组result用于储存新的有序平方后的元素。
class Solution {
public://双指针vectorint sortedSquares(vectorint A) {int k A.size() - 1; //指向新数组的末尾从后往前赋值vectorint result(A.size(), 0);for (int i 0, j A.size() - 1; i j;) { // 注意这里要i j因为最后要处理两个元素if (A[i] * A[i] A[j] * A[j]) { //判断条件1尾部元素更大result[k--] A[j] * A[j];j--;}else {result[k--] A[i] * A[i]; //判断条件2头部元素更大i;}}return result;}
};
27.删除有序数组中的重复项II
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
前2个肯定不用删所以可以跳过从j 2开始比 还是太优雅了这代码
class Solution {
public:int removeDuplicates(vectorint nums) {if(nums.size() 2) return nums.size();int i 2;for(int j 2; j nums.size(); j ){if(nums[j] ! nums[i - 2]){nums[i] nums[j];i ;}}return i;}
};28.寻找重复数 不可以用sort也不可以用额外数组 这个要求真的是把我路都堵死了…
数组小技巧数组也可以看做链表来做
class Solution {
public:int findDuplicate(vectorint nums) {int fast 0, slow 0;while(true){fast nums[nums[fast]];slow nums[slow];if(fast slow) break;}slow 0;while(fast ! slow){fast nums[fast];slow nums[slow];}return slow;}
};29 .水果成篮
fruits数组fruits[i]代表一种水果比如fruits[2] 1,代表香蕉 现在有fruits.size()棵水果树每次只能摘一颗树 现在有2个篮子每个篮子装一种水果问最多能摘多少棵数
fruit [1,2,1]有两种水果树所以能摘三棵都能摘篮子装得下
滑动窗口。要注意不需要window.size() need也要计算len因为有while(window.size() need)在窗口不是小了就是刚刚好不可能大如果fruit的水果树种类本来就不足2个就可以返回 另外当缩小窗口导致其中一个苹果树没了window应该erase掉。否则还占用一个size
class Solution {
public:int totalFruit(vectorint fruits) {unordered_mapint, int window;int need 2;int len 0;int left 0, right 0;while(right fruits.size()){int c fruits[right];right;window[c];;while(window.size() need){int d fruits[left];left;window[d]--;if(window[d] 0) window.erase(d);}len max(len, right - left);}return len;}
};30.和为k的子数组
给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的子数组个数。子数组是数组中元素的连续非空序列
被骗啦滑窗酷酷一顿做结果nums可以有负数 也就是说left的话窗口和也不一定变小right也不一定窗口和变大 滑动窗口失效的时候要用前缀和前缀和我也写过秒杀系列-传送门
前缀和与子数组的关系是prefix[j] - prefix[i - 1] k假设现在遍历到k 先将前缀和prefix[j]存入哈希表在求prefix[j] - k看他在不在哈希表如果在的话说明存在一个prefix[i - 1]使prefix[j] - prefix[i - 1] k
将当前累加和减去整数k的结果在哈希表中查找是否存在如果存在该key证明以数组某一点为起点到当前位置满足题意resval判断当前累加和是否在哈希表中若存在value1不存在则value1
class Solution {
public:int subarraySum(vectorint nums, int k) {unordered_mapint ,int preSumCount {{0, 1}};int preSum 0, count 0;for(int num : nums){preSum num;count preSumCount[preSum - k];preSumCount[preSum];}return count;}
};31.统计[优美子数组] 看起来又很像滑动窗口但其实最好别用因为滑动窗口一般用来解决的是窗口符合某个特定条件的问题而不是窗口的数量这种情况一般用哈希表和前缀和并且这题和30其实很像
我们可以通过记录前缀和出现的次数来计算有多少个符合条件的子数组 prefix_count[i] k 表示前缀和有i个奇数的数组有k个
class Solution {
public:int numberOfSubarrays(vectorint nums, int k) {unordered_mapint, int preSumNums {{0, 1}};int count 0, curSum 0;for(int num : nums){curSum (num % 2 1 ? 1 : 0);//奇数当1,偶数当0if(preSumNums.find(curSum - k) ! preSumNums.end()) count preSumNums[curSum - k];preSumNums[curSum];}return count;}
};32.区间列表的交集 i为first的行j为second的行
class Solution {
public:vectorvectorint intervalIntersection(vectorvectorint firstList, vectorvectorint secondList) {int i 0, j 0, n firstList.size(), m secondList.size();vectorvectorint res;while(i n j m){int l max(firstList[i][0], secondList[j][0]);int r min(firstList[i][1], secondList[j][1]);if(l r) res.push_back({l, r});firstList[i][1] secondList[j][1] ? j : i ;}return res;}
};33.将x减到0的最小操作 有些题目真的就是破烂(艹皿艹 ) 这题考滑动窗口但是考的很隐蔽题目说只能移除nums最左边和最右边的元素目标值是x可以反着来目标区间是中间的区域目标值是sum - x 注意元素一加立刻right的话窗口长度是right-left for的话因为right会晚一步1所以窗口长度是right-left1
class Solution {
public:int minOperations(vectorint nums, int x) {int sum 0, temp 0, res -1;for(int num : nums) sum num;int target sum - x;if(target 0) return -1;int left 0, right 0;while(right nums.size()){temp nums[right];right ;while(temp target) temp - nums[left];if(temp target) res max(res, right - left);}return res -1 ? -1 : nums.size() - res;}
};34.替换子串得到平衡字符串 还是滑动窗口不太一样的是要观察的是窗口外的元素可以叫他反向滑动(名字我瞎取得。 设m n/4。 滑动窗口内部是待替换字符串窗口外是不替换的。 所以窗口外Q,W,E,R的个数都小于等于m替换窗口内的字母才可能让字符串平衡。 所以right意味着外面的元素少一个这个是替换window需要记录的 如果窗口外有字符大于m说明窗口内无论怎么替换都无法平衡。 用哈希表统计原串的字符个数 固定左边界移动右边界。 如果剩余部分不替换的字符串中所有字母个数均≤m则说明可以构造平衡字符串则用滑窗长度更新最小替换子串长度 然后移动左边界对子串长度进行缩小。
class Solution {
public:int balancedString(string s) {int n s.size();int res INT_MAX;unordered_mapchar, int a;for(char c : s) a[c] ;int m n / 4;if(a[Q] m a[W] m a[E] m a[R] m) return 0;int l 0, r 0;while(r n){char d s[r];r ;a[d] --;while(a[Q] m a[W] m a[E] m a[R] m){res min(res, r - l);char c s[l];a[c] ;l ;}}return res;}
};35.划分字母区间 再强调一遍不二刷三刷的题目就是没刷过
class Solution {
public:vectorint partitionLabels(string s) {// 更新每个字母出现的最远下标// 区间内更新其中每个字母出现的最远下标i等于这个下标的时候片段1int hash[27] {0};//hash数组里面是不同字母对应的ascll码的最远下标 for(int i 0; i s.size(); i ){hash[s[i] - a] i;}vectorint result;int left 0;int right 0;for(int i 0; i s.size(); i ){right max(right, hash[s[i] - a]);if(i right){result.push_back(right - left 1);left i 1;}}return result;}
};36.分隔链表 双指针总结里面原题
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode* dummy1 new ListNode(0);ListNode* p1 dummy1;ListNode* dummy2 new ListNode(0);ListNode* p2 dummy2;ListNode* cur head;while(cur){if(cur-val x){p1-next cur;p1 p1-next;}else{p2-next cur;p2 p2-next;}ListNode* temp cur;cur cur-next;temp-next NULL;}p1-next dummy2-next;delete dummy2;return dummy1-next;}
};持续更新ing 2024/8/5
