h5页面制作软件教程,如何seo网站,wordpress自动翻译插件,手机网站仿站教程
#x1f525;个人主页#xff1a;guoguoqiang. #x1f525;专栏#xff1a;leetcode刷题
209.长度最小的子数组 求最短长度之和等于目标值。 方法一#xff1a; 暴力枚举#xff08;会超时#xff09; 从头开始遍历直到之和等于target然后更新结果。这…
个人主页guoguoqiang. 专栏leetcode刷题
209.长度最小的子数组 求最短长度之和等于目标值。 方法一 暴力枚举会超时 从头开始遍历直到之和等于target然后更新结果。这里就不写代码了。 方法二 滑动窗口
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int nnums.size(),sum0,lenINT_MAX;for(int left0,right0;rightn;right){sumnums[right];//入窗口while(sumtarget){//判断 题目要求就为sum大于等于target然后长度最小lenmin(len,right-left1);//更新结果sum-nums[left];//出窗口}}return lenINT_MAX?0:len;//如果它还未更新就说明和没有大于target否则就更新了len。}
};3.无重复字符的最长字串 可以看出这道题目全是字母可以通过数组来模拟哈希表 方法一哈希表暴力枚举 每有一个就入哈希表然后就判断是否重复然后更新结果。循环结束最后的len即为结果
class Solution {
public:int lengthOfLongestSubstring(string s) {int ret 0; // 记录结果int n s.length();// 1. 枚举从不同位置开始的最⻓重复⼦串// 枚举起始位置for (int i 0; i n; i) { // 创建⼀个哈希表统计频次int hash[128] {0};// 寻找结束为⽌for (int j i; j n; j) {hash[s[j]]; // 统计字符出现的频次if (hash[s[j]] 1) // 如果出现重复的break;// 如果没有重复就更新 retret max(ret, j - i 1);}}// 2. 返回结果return ret;}
};方法二 通过哈希表滑动窗口
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]{0};int left0,right0,ns.size();int ret0;while(rightn){//遍历字符串hash[s[right]];//进窗口while(hash[s[right]]1)//判断是否出现重复字符串hash[s[left]]--;//将这个左对应的元素出窗口retmax(ret,right-left1);//更新结果求最长长度right;//让下一个元素进窗口}return ret;}
};1004. 最大连续1的个数 III 利用滑动窗口来 这个题就是记录最大连续1的个数然后用一个变量来记录0的个数如果大于k就将左侧的元素出窗口直到zerok;然后更新结果
class Solution {
public:int longestOnes(vectorint nums, int k) {int ret0;for(int left0,right0,zero0;rightnums.size();right){if(nums[right]0) zero;//记录0的个数while(zerok){//如果0的个数大于kif(nums[left]0) zero--;//就判断left位置是否为0为0就跳出窗口不为0就遍历下一个}retmax(ret,right-left1);//更新结果}return ret;}
};1658.将x减到0的最小操作数 方法 滑动窗口 这个相减为最小生成数然后可以改为中间部分的和为sum-x求长度最长数组长度-len即为外部相减为0的最短长度。
class Solution {
public:int minOperations(vectorint nums, int x) {int sum0;for(auto num:nums) sumnum;//求全部的和int targetsum-x;//为中间区域的和这个就可以改为之前的那个最长长度和为targetif(target0) return -1;int ret-1;for(int left0,right0,tmp0;rightnums.size();right){tmpnums[right];//入窗口while(tmptarget){//判断是否大于targettmp-nums[left];//出窗口}if(tmptarget)//如果和等于targetretmax(ret,right-left1);//更新结果}if(ret-1) return ret;//说明没找到else return nums.size()-ret;//就返回n-ret的即为能减为0的最短长度}
};904.水果成篮 这个题目可以理解为最多只能能摘两种水果但是不限制数量所以需要求可以摘的水果的最大数量。 方法 通过哈希表滑动窗口来实现
class Solution {
public:int totalFruit(vectorint f) {unordered_mapint,int hash;//创建哈希表int ret0;for(int left0,right0;rightf.size();right){hash[f[right]];//入窗口while(hash.size()2){//如果种类大于两种就从左面出窗口直到种类等于两种hash[f[left]]--;if(hash[f[left]]0) hash.erase(f[left]);//如果这个种类数量等于零就从哈希表中删除left;}retmax(ret,right-left1);//更新结果}return ret;}
};通过观察这个题的数字范围是1到100000 可以通过创建一个数组来代替哈希表实现
class Solution {
public:int totalFruit(vectorint fruits) {int hash[100001]{0};//哈希表int nfruits.size();int ret0;for(int left0,right0,kinds0;rightn;right){if(hash[fruits[right]]0) kinds;//如果这个元素为0说明是新种类kindshash[fruits[right]];//进窗口while(kinds2){hash[fruits[left]]--;//出窗口if(hash[fruits[left]]0) kinds--;//如果这个值变为零就需要将种类--left;//left遍历下一个left对应元素直到种类等于2}retmax(ret,right-left1);//更新结果}return ret;}
};438.找到字符串中所有字母异位词 方法一暴力枚举哈希表 就是遍历整个s然后找出等于hash表中p的单词然后就记录到结果中 方法二滑动窗口哈希表
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash1[26]{0};for(auto ch:p) hash1[ch-a];//记录p中的字母int hash2[26]{0};int mp.size();//记录p中的个数for(int left0,right0,count0;rights.size();right){char ins[right];if(hash2[in-a]hash1[in-a]) count;//判断进窗口的元素是否为有效元素if(right-left1m){//长度大于m出窗口char outs[left];if(hash2[out-a]--hash1[out-a]) count--;//判断是否为有效元素然后出窗口更新}if(countm) ret.push_back(left);//更新结果}return ret;}
};这个题目的范围只包括小写字母就可以通过一个int数组来代替哈希表。
30.串联所有单词的字符 这个题目说明可以看例子了解 就是将words中的字符可以全排列找到然后返回首元素在s中出现的下标位置。
方法一暴力枚举哈希表会超时 先将words中的元素进哈希表hashstring,int统计words中的元素。 然后for循环遍历字符串判断是否为串联子串。 方法二 滑动窗口哈希表 在暴力枚举中是一个单位一个单位进行移动在这个题中就显得不是很合适这个我们可以把后面words中的word看作一个单位按这个单位长度进行移动。这样我们这个题就可以看作找到字符串中所有字母的异位词。 我们需要注意 窗口执行的次数。
class Solution {
public:vectorint findSubstring(string s, vectorstring words) {vectorint ret;unordered_mapstring,int hash1 ;//将所有的words进入哈希表for(auto word:words) hash1[word];int sizewords.size();//记录words中的元素个数int lenwords[0].size();//记录words中的单个元素长度for(int i0;ilen;i){//执行len次 因为次数多了有重复遍历unordered_mapstring,inthash2;for(int lefti,righti,count0;rightlens.size();rightlen){//一次跳过长度个长度string ins.substr(right,len);hash2[in];//记录s中的单词if(hash1.count(in)hash2[in]hash1[in])count;//如果words中存在则进行判断s中出现的次数是不是小于等于words中的if(right-left1size*len){//长度超了需要出窗口string outs.substr(left,len);if(hash1.count(out)hash2[out]hash1[out]) count--;//出窗口并记录counthash2[out]--;//将这个元素从哈希表中出去leftlen;//一次len个单位长度}if(countsize) ret.push_back(left);//更新结果}}return ret;}
};
