c++滑动窗口leetcode3-567

c++滑动窗口leetcode3-5673 无重复字符的最长子串 力扣 LeetCode leetcode cn com 写的不太好的一版 内存占用太多 时间太长 int lengthOfLong string s int n 0 int l 0 int p 0 int q 0

大家好,我是讯享网,很高兴认识大家。

3. 无重复字符的最长子串 - 力扣(LeetCode) (leetcode-cn.com)

写的不太好的一版,内存占用太多,时间太长。 

int lengthOfLongestSubstring(string s) { int n=0;int l=0; int p=0;int q=0;set<char> ss; while(q<s.size()&&p<s.size()){ if (ss.count(s[q])==0) {ss.insert(s[q]); q++; l++; } else { p=p+1; q=p; ss.clear(); l=0; } if (l>n){ n=l; } } return n; }

讯享网

 离谱,修改了一版时间还是很长,看来可能不能用set

讯享网int lengthOfLongestSubstring(string s) { int n=0; int p=0;int q=0;set<char> ss; while(q<s.size()&&p<s.size()){ if (ss.count(s[q])==0) {ss.insert(s[q]); q++; } else { p=q-ss.size()+1; q=p; ss.clear(); } if (ss.size()>n){ n=ss.size(); } } return n; }

看了大佬的题解…以这个字符串为例:abcabcbb,当i等于3时,也就是指向了第二个a, 此时我就需要查之前有没有出现过a, 如果出现了是在哪一个位置出现的。然后通过last[index] 查到等于1, 也就是说,如果start 依然等于0的话,那么当前窗口就有两个a了,也就是字符串重复了,所以我们需要移动当前窗口的start指针,移动到什么地方呢?移动到什么地方,窗口内就没有重复元素了呢? 对了,就是a上一次出现的位置的下一个位置,就是1 + 1 = 2。当start == 2, 当前窗口就没有了重复元素,那么以当前字符为结尾的最长无重复子串就是bca,然后再和之前的res取最大值。然后i指向后面的位置,按照同样思路计算。

int lengthOfLongestSubstring(string s) { int n=0; int p=0;int q=0; int ss[128]; for(int i = 0; i < 128; i++) { ss[i] = -1; } for(int i=0;i<s.size();i++) { int index=char(s[i]); p=max(p,ss[index]+1); q=max(q,i-p+1); ss[index]=i; } return q; }

 567. 字符串的排列 - 力扣(LeetCode) (leetcode-cn.com)

这个题跟上面的题有点相似,都可以用出现的次数代替字符本身。通过字符次数的变化,发现排列的规律。 


讯享网

讯享网 bool checkInclusion(string s1, string s2) { int ss[26]; for(int i=0;i<26;i++) { ss[i]=0; } for(int i=0;i<s1.size();i++) { --ss[s1[i]-'a'];//这个地方用减法下面比较好判断 } int p=0; int q=0; while(q<s2.size()&&p<s2.size()) { ++ss[s2[q]-'a']; while(ss[s2[q]-'a']>0) { ss[s2[p]-'a']--; p++; } if(q-p+1==s1.size()) { return true; } q++; }return false; }

题解的简单解法:滑动窗口

使用两个数组cnt1和 cnt2 ,cnt 1 统计 s1 中各个字符的个数,cnt 2统计当前遍历的子串中各个字符的个数。

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

bool checkInclusion(string s1, string s2) { int n = s1.length(), m = s2.length(); if (n > m) { return false; } vector<int> cnt1(26), cnt2(26); for (int i = 0; i < n; ++i) { ++cnt1[s1[i] - 'a']; ++cnt2[s2[i] - 'a']; } if (cnt1 == cnt2) { return true; } for (int i = n; i < m; ++i) { ++cnt2[s2[i] - 'a']; --cnt2[s2[i - n] - 'a']; if (cnt1 == cnt2) { return true; } } return false; } 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

小讯
上一篇 2025-01-27 19:22
下一篇 2025-03-22 12:43

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/115478.html