吐鲁番大型网站建设平台,wordpress 重写规则,软件外包开发,做网站运营好还是SEO好复习比学习更重要#xff0c;更需要投入时间#xff0c;更需要花费精力 1.字符串的排列2.找出字符串中第一个匹配的下标3.最大连续1的个数II4.数组中的山脉5.移除元素6.两个数组的交集II7.有序数组的平方8.删除有序数组中的重复项II9.寻找重复数10.水果成篮 1.字符串的排列
… 复习比学习更重要更需要投入时间更需要花费精力 1.字符串的排列2.找出字符串中第一个匹配的下标3.最大连续1的个数II4.数组中的山脉5.移除元素6.两个数组的交集II7.有序数组的平方8.删除有序数组中的重复项II9.寻找重复数10.水果成篮 1.字符串的排列
在滑动窗口总结文章里面讲解过了
二刷debug首先缩小窗口的条件是r-l s1.size()。然后必须用need.count( c )而不是need[c] 1。count( c ) 仅仅检查键 c 是否存在于 unordered_map 中与键对应的值无关而need[c]1是必须need中有其键并且数量大于等于1
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;}
};2.找出字符串中第一个匹配的下标 拿到手的第一想法就是滑动窗口输出left 但是这个要求顺序完全一样不能是排列或者组合 查了一下KMP是专门弄这种的学习新算法了(我只是来做双指针的…)这篇文章是个纯刷题记录不贴详细讲解最多记录大致思路需要讲解去秒杀直接部分-传送门 二刷debug写出来了几乎是靠背的注意ne初始化
class Solution {
public:int strStr(string haystack, string needle) {int n haystack.size();int m needle.size();vectorint ne(m, -1);// ne数组必须初始化为-1而不是0,只有-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;}
};3.最大连续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;}
};4.数组中的山脉 先找到可能得山顶再双指针两边扩展记录res 留意lri的边界 二刷debug注意双指针两边扩展的手法还有边界问题如果是只能到倒数第二个元素的话i.size()-1即可
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;}
};5.移除元素
移除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;}
}6.两个数组的交集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;}
};7.有序数组的平方
给一个非递减的数组现在需要你将每个元素都平方然后递增排序返回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;}
};
8.删除有序数组中的重复项II
给你一个有序数组 nums 请你 原地 删除重复出现的元素使得出现次数超过两次的元素只出现两次 返回删除后数组的新长度。
不要使用额外的数组空间你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
前2个肯定不用删所以可以跳过从j 2开始比 还是太优雅了这代码
二刷debug不会很难理解
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;}
};9.寻找重复数 不可以用sort也不可以用额外数组 这个要求真的是把我路都堵死了… 二刷debug不会… 数组小技巧数组也可以看做链表来做 以图为例天然就有数组链表0-1-3-2-4 fast nums[nums[fast]]相当于fast fast-next-next slow nums[slow]相当于slow slow-next 几刷容易写成return nums[slow]实际上最后一个是slow nums[slow]所以直接写成return slow就可以了
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;}
};10.水果成篮
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
二刷debug小于等于2的水果树种类也可以另外unordered_map类型可以使用erase
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;}
};
