刚创业 建网站,手机怎么建立网站,网站二次开发教程,工装设计网站案例题目来源#xff1a;
438. 找到字符串中所有字母异位词 - 力扣#xff08;LeetCode#xff09; 题目内容#xff1a;
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 示例 1: 输入: s
438. 找到字符串中所有字母异位词 - 力扣LeetCode 题目内容
给定两个字符串 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 * 104 s 和 p 仅包含小写字母 思路分析
思路一不定长滑窗 来源:灵茶山艾府 枚举子串s′的右端点如果发现s′其中一种字母的出现次数大于 p的这种字母的出现次数则右移s′的左端点。如果发现s′的长度等于p的长度则说明s′的每种字母的出现次数和p的每种字母的出现次数都相同那么s′是p的异位词。 代码实现版本一灵神附带注释
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint ans;int cnt[26];//记录p中每种字母出现的次数这里我觉得也可以使用哈希表实现for(char c:p) cnt[c-a];int left 0;for(int right0;rights.size();right){int cs[right]-a;cnt[c]--;while(cnt[c]0){//是循环 字母c太多了cnt[s[left]-a];//左端点向后移动left;}if(right-left1p.length()){//经过上面while循环s‘和p的每种字符出现次数都相同ans.push_back(left);}}return ans;}
};
代码实现版本二int数组ant 替换成哈希表
我再想想 题目心得 体会题目解法的精妙思想 滑动窗口是怎么实现的/为什么要用滑动窗口 比较滑动窗口和双指针算法的区别 int/char cs[right]-a; //这里的c两种类型都可以运行 最近在读一本书《刻意练习》 作者在通过举例的方式想向我们传达一种思想 一些国际象棋大师之所以厉害是因为他们的脑袋里存储了上万个残局模型在比赛/下棋过程中针对不通的情况进行调用/做出改善。 我觉得我们学习算法的过程亦是如此先针对基础的算法进行学习在头脑中积累算法模板最后遇到题目/实际问题进行合适的调用并输出。 说了这么多。就是想表达。有时候不用太纠结。不会了就看看答案但一定要自己敲一遍。多记忆一些。下次才会有思路。
