商业网站建设案例笔记,网站建设投标文档,西安网站建设哪家比较好,nat123做视频网站文章目录 1.将x减到0的最小操作数2.水果成篮3.找到字符串中所有字母异位词 1.将x减到0的最小操作数 分析题目 x不断地减去数组两端的值 看能否减到0#xff1b;是不是就是在问#xff1a;nums数组中存不存在【左端右端】组成的连续区间#xff0c;区间上数的和为x 继续分析 … 文章目录 1.将x减到0的最小操作数2.水果成篮3.找到字符串中所有字母异位词 1.将x减到0的最小操作数 分析题目 x不断地减去数组两端的值 看能否减到0是不是就是在问nums数组中存不存在【左端右端】组成的连续区间区间上数的和为x 继续分析 》 是不是就是在问nums数组中存不存在内部的一段连续区间区间上的数的和为sum(nums) - x 很明显这是个经过分析的【滑动窗口】问题 代码 class Solution
{
public:int minOperations(vectorint nums, int x){int sum 0;for (int a : nums)sum a;int target sum - x;//x比sum大 sum中就不会存在几个数的和xif (target 0)return -1;int ret -1;for (int left 0, right 0, tmp 0; right nums.size(); right){tmp nums[right]; while (tmp target) tmp - nums[left]; if (tmp target) ret max(ret, right - left 1);}if (ret -1)return ret;elsereturn nums.size() - ret;}
};
2.水果成篮 分析 依旧是滑动窗口一个区间该区间内水果种类不能超2超2就将下一个元素作为区间的起始位置 代码 class Solution
{
public:int totalFruit(vectorint f){// i是树的下标 fruits[i]是水果的种类编号 fruits[i]: 0~100000int hash[100001] {0}; // 以水果的种类编号作hash的下标 对应值记录该种水果出现次数int ret 0;for (int left 0, right 0, kinds 0; right f.size(); right){// 当前遍历的该水果在篮子里的次数是0 种类if (hash[f[right]] 0)kinds;// 当前遍历的该水果可以出现在篮子里hash[f[right]];while (kinds 2){// left作起始位置的这个区间已达最大长度 继续遍历 将下一个元素作为区间的起始位置hash[f[left]]--; // 出窗口 水果次数--if (hash[f[left]] 0) // 如果拿出窗口的水果在原来的篮子里是独苗 种类也--kinds--;left; // 继续下一个元素作为区间的起始位置}ret max(ret, right - left 1);}return ret;}
};cpp_stl容器unordered_map class Solution
{
public:int totalFruit(vectorint f){unordered_mapint, int hash; int ret 0;for (int left 0, right 0; right f.size(); right){hash[f[right]]; while (hash.size() 2) {hash[f[left]]--;if (hash[f[left]] 0)hash.erase(f[left]);left;}ret max(ret, right - left 1);}return ret;}
};
3.找到字符串中所有字母异位词 滑动窗口的分类 区间长度固定如本题左指针疯狂右移 right不动右指针疯狂右移 left不动 总体思路这道题【维护窗口的时机】发生在窗口的长度超过了p的长度保证窗口的长度只能不大于p的长度 遍历母串遍历到who不管符不符合条件who就先进窗口如果who是一个【有效字符】即【可以作为异位词的字符】即【在p中出现且次数不超过在p中出现的字符】接着上一句如果who是一个【有效字符】那么有效字符个数validChar; 经过不断遍历如果窗口的长度已经大于p的长度窗口就要右移了即left; 并且left在窗口中的次数也要winHash[out - a]--; 需要注意的是如果移出去的left他对应的值在窗口中出现的次数大于在p中出现的次数left移出后有效字符个数不变left出去正是我们想要的这个操作表明窗口中少了一个不该出现的字符这使得区间中的字符越来越接近我们想要的字符组合即异位词。上述操作保证了窗口的长度只能不大于p的长度。接着再判断如果此时窗口中的有效字符个数 p的长度表示我们找了“异位词”。如果此时validChar ! pLen 表示: 虽然窗口的长度到达了pLen但是窗口中的字符并不是全部有效还要继续添加新元素来满足窗口的长度为pLen且均为有效字符。 代码 史上最全解析 class Solution
{
public:vectorint findAnagrams(string s, string p){vectorint ret;int sLen s.size(), pLen p.size(), validChar;// 母串长度比子串长度还小 直接返回if (sLen pLen)return ret;// p字符串有哪些字符 分别出现了多少次// phash中值不为0的下标代表有哪些字符 值就是它出现的次数int pHash[26] {0};for (auto ch : p)pHash[ch - a];// 记录窗口中有哪些字符以及对应出现的次数int winHash[26] {0};// 要理解这种写法 要理解两个关键字// 1. winHash :窗口中有哪些字符以及对应出现的次数// 2. validChar:窗口中有效字符的个数for (int left 0, right 0, validChar 0; right s.size(); right){// in即将进入窗口的字符char in s[right];// 遍历到in了 in默认进窗口 用【in在窗口中的次数】来表征in进窗口了// 如果此时窗口中in的次数大于p中in的次数 那么in是作为一个无效字符进的窗口 有效字符个数不变// 如果此时窗口中in的次数不大于p中in的次数 表明in此时在窗口中是一个有效字符 有效字符个数if (winHash[in - a] pHash[in - a])validChar;// 窗口的长度已经大于子串了if (right - left 1 pLen){char out s[left];// out在窗口中出现的次数 out在p中出现的次数 有效字符个数--// 反向理解// 如果out在窗口中出现的次数 out在p中出现的次数// out移出后 有效字符个数不变 out出去正是我们想要的 窗口中少了一个不该出现的字符// 这使得区间中的字符越来越接近我们想要的字符组合了即异位词if (winHash[out - a]-- pHash[out - a])validChar--;}// 前面两个if保证窗口的窗口不会超过p的长度// 如果此时validChar pLen即窗口中的有效字符个数等于p的长度 表示我们找了“异位词”// 如果此时validChar ! pLen 表示: 虽然窗口的长度到达了pLen 但是窗口中的字符并不是全部有效// 还要继续添加新元素 来满足窗口的长度为pLen且均为有效字符if (validChar pLen)ret.push_back(left);}return ret;}
};
