当前位置: 首页> 科技> 数码 > 2021年免费的网站有哪些_创立一个公司需要多少钱_现在疫情怎么样了最新消息_最新一周新闻

2021年免费的网站有哪些_创立一个公司需要多少钱_现在疫情怎么样了最新消息_最新一周新闻

时间:2025/7/11 0:47:38来源:https://blog.csdn.net/wer24_25/article/details/142341377 浏览次数:0次
2021年免费的网站有哪些_创立一个公司需要多少钱_现在疫情怎么样了最新消息_最新一周新闻

个人主页:C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创

滑动窗口(6)_找到字符串中所有字母异位词

收录于专栏【经典算法练习
本专栏旨在分享学习算法的一点学习笔记,欢迎大家在评论区交流讨论💌

目录

1. 题目链接:

2. 题目描述 :

3. 解法 :

    解法一(暴力枚举) :

    算法思路 :

    易错警示:

    代码展示 :

    结果分析 :

    对暴力算法的反思与优化 :

    解法二(滑动窗口) :

    算法思路 :

    图解流程 :

    代码展示 :

    结果分析 :


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 * 104
  • s 和 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:vector<int> findAnagrams(string s, string p) {vector<int> 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:vector<int> findAnagrams(string s, string p) {vector<int> 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)

滑动窗口在这道题中是一种效率很高的解决方法.

关键字:2021年免费的网站有哪些_创立一个公司需要多少钱_现在疫情怎么样了最新消息_最新一周新闻

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: