mvc 网站建设,wordpress朗读文章,全球最大的c2c平台,不备案域名能用吗个人主页#xff1a;C忠实粉丝 欢迎 点赞#x1f44d; 收藏✨ 留言✉ 加关注#x1f493;本文由 C忠实粉丝 原创 滑动窗口(6)_找到字符串中所有字母异位词 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记#xff0c;欢迎大家在评论区交流讨论#x1f4… 个人主页C忠实粉丝 欢迎 点赞 收藏✨ 留言✉ 加关注本文由 C忠实粉丝 原创 滑动窗口(6)_找到字符串中所有字母异位词 收录于专栏【经典算法练习】 本专栏旨在分享学习算法的一点学习笔记欢迎大家在评论区交流讨论 1. 题目链接:
OJ链接:找到字符串中所有字母异位词
2. 题目描述 :
给定两个字符串 s 和 p找到 s 中所有 p 的 异位词 的子串返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串包括相同的字符串。
示例 1:
输入: s cbaebabacd, p abc
输出: [0,6]
解释:
起始索引等于 0 的子串是 cba, 它是 abc 的异位词。
起始索引等于 6 的子串是 bac, 它是 abc 的异位词。示例 2:
输入: s abab, p ab
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 ab, 它是 ab 的异位词。
起始索引等于 1 的子串是 ba, 它是 ab 的异位词。
起始索引等于 2 的子串是 ab, 它是 ab 的异位词。提示:
1 s.length, p.length 3 * 104s 和 p 仅包含小写字母
3. 解法 : 解法一(暴力枚举) : 算法思路 : 1.用两个hash表分别存贮两个字符串,hash1存贮字符串s,hash2存贮字符串p 2.用两层循环取s中的p大小的字符串存入hash1中,然后与hash2进行比较 3.如果相等返回s取的子字符串的起始位置,不相等直接从下一个位置截取p大小的字符串继续比较 易错警示: 1. 在遍历字符串s时需要注意边界问题,如果当s的长度小于p时,还去s中取p长度的字符串就会导致越界访问,程序报错! 2. 如果刚开始字符串s就小于p,可以直接放回空vector,不需要处理! 代码展示 :
class Solution {bool check(int a[], int b[]){for(int i 0; i 26; i)if(b[i] ! a[i]) return false;return true;}
public:vectorint findAnagrams(string s, string p) {vectorint ret;int hash2[26] {0};for(auto e : p) hash2[e - a];int slen s.size();int plen p.size();//如果s的长度小于p的长度直接返回空结果if(slen plen) return ret;for(int i 0; i s.size() - p.size(); i)//确保不越界{int hash1[26] {0};for(int j 0; j plen; j)hash1[s[i j] - a];if(check(hash1, hash2)) ret.push_back(i);}return ret;}
}; 结果分析 : 其实这道题很出乎我的意料,我没想到两层循环的暴力也能解决,因为算法题暴力一般都解决不了. 但是我分析了一下题目给的范围我恍然大悟,题目两个字符串的长度都小于3*10^4,这个暴力算法两层遍历时间复杂度为O(N^2),总体数据级别为9*10^8 10^9,计算机能在1s中内完成,系统也就不会判定你超时,我们的check函数虽然也是遍历,但只遍历了26次,是常数级别,可以忽略不记,所以我们整体的代码顺利AC了这道题! 对暴力算法的反思与优化 : 这里对暴力算法的优化很简单,没错我们的老朋友滑动窗口: 还是和之前一样的思路,我们没有必要让j直接回来,我们可以让i直接,这样就省去了多余的遍历 解法二(滑动窗口) : 算法思路 : 1. 因为字符串p的异位词的长度一定与字符串p的长度相同,所以我们可以在字符串s中构造一个长度与字符串p的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量; 2. 当窗口中每种字母的数量与字符串p中每种字母的数量相同时,则说明当前窗口为字符串p的异位词; 3. 因此可以用两个大小为26的数组来模拟哈希表,一个来保存s中的字串每个字符出现的个数,另一个来保存p中每一个字符出现的个数.这样就能判断两个串是否是异位词. 图解流程 : 代码展示 :
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ret;int n p.size(), count 0;int hash1[26] {0}, hash2[26] {0};for(auto ch : p) hash2[ch - a];for(int left 0, right 0; right s.size(); right){if(hash1[s[right] - a] hash2[s[right] - a]) count;if(right- left 1 n){if(hash1[s[left] - a]-- hash2[s[left - 1] - a]) count--;}if(count n) ret.push_back(left);}return ret;}
}; 结果分析 : 时间复杂度: O(N) 空间复杂度: O(1) 滑动窗口在这道题中是一种效率很高的解决方法.
