devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【优选算法】滑动窗口——leetcode——438.找到字符串中所有字母异位词_438. 找到字符串中所有字母异位词

作者：小惠珠哦 | 2024-08-20 20:11:33

赞

踩

438. 找到字符串中所有字母异位词

目录

1.题目

2.题目理解 

3.算法原理

1.如何快速判断两个字符串是否是异位词

2.解决问题 

暴力求解——>滑动窗口+哈希表

 滑动窗口

利用滑动窗口+哈希表解决问题 

 优化：更新结果的判断条件

4.编程代码 

C++代码

 1.频率统计

2. 双指针

 C语言代码

1.字符频率统计 

2.滑动窗口机制

3.判断窗口大小并维护窗口内字符频率

4.更新结果

C++知识点详解

1. STL（Standard Template Library）

2. 范围 for 循环

3. 字符数组与频率统计

4. 双指针（Sliding Window）技巧

5. 成员函数与类

ce6fbd68767d465bbe94b775b8b811db.png

731bd47804784fa2897220a90a387b28.gif

专栏：优选算法

1.题目

438. 找到字符串中所有字母异位词

给定两个字符串 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 仅包含小写字母

2.题目理解 

“abc”的异位词 有：abc，acb，bac，bca，cab，cba；

 输出: [0,6]（子串的起始索引）

3.算法原理

1.如何快速判断两个字符串是否是异位词

1.两个字符串都按照字符顺序排序，然后比较是否相等               排序+比较     nlogn +n       

2.统计每个字符出现的次数     哈希表遍历比较

2.解决问题 

暴力求解——>滑动窗口+哈希表

因为字符串p 的异位词的⻓度“m”⼀定与字符串p的⻓度相同，所以我们可以在字符串 s 中构
造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；保持窗口大小一次遍历比较。

 滑动窗口

利用滑动窗口+哈希表解决问题 

可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个
数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

 优化：更新结果的判断条件

利用变化量count来统计窗口中“有效字符的次数”；

当窗⼝中每种字⺟的数量与字符串p中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p 
的异位词；

 

4.编程代码 

C++代码

  1. class Solution
  2. {
  3. public:
  4. vector<int> findAnagrams(string s, string p)
  5. {
  6. vector<int> ret;
  7. int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
  8. for(auto ch : p) hash1[ch - 'a']++;
  9. int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
  10. int m = p.size();
  11. for(int left = 0, right = 0, count = 0; right < s.size(); right++)
  12. {
  13. char in = s[right];
  14. // 进窗⼝ + 维护 count
  15. if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
  16. if(right - left + 1 > m) // 判断
  17. {
  18. char out = s[left++];
  19. // 出窗⼝ + 维护 count
  20. if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
  21. }
  22. // 更新结果
  23. if(count == m) ret.push_back(left);
  24. }
  25. return ret;
  26. }
  27. };

 1.频率统计

for(auto ch : p) hash1[ch - 'a']++;
  • 范围 for 循环: 用于遍历字符串 p，并统计每个字符的出现次数。
  • 字符偏移量 ch - 'a': 将字符转换为数组索引，例如 'a' 对应 0，'b' 对应 1。

2. 双指针

  • 初始化指针和计数器 left, right, count: left 和 right 分别表示窗口的左边界和右边界，count 用于记录匹配字符的数量。
  • 滑动窗口 for 循环: 遍历字符串 s，右指针 right 不断向右移动。
  • 进窗口操作: 将 s[right] 加入窗口并更新频率数组 hash2。如果该字符的频率没有超过 hash1 中的频率，则计数器 count 加一。
  • 出窗口操作: 当窗口大小超过 m 时，将 s[left] 移出窗口，并更新频率数组 hash2 和计数器 count。
  • 更新结果: 如果 count 等于 m，说明当前窗口是一个字母异位词，记录起始索引 left。

 C语言代码

  1. int* findAnagrams(char * s, char * p, int* returnSize) {
  2.     int s_len = strlen(s);  // 使用 strlen 计算字符串 s 的长度
  3.     int p_len = strlen(p);  // 使用 strlen 计算字符串 p 的长度
  4.     int *ret = (int *)malloc(s_len * sizeof(int));
  5.     *returnSize = 0;
  7.     int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
  8.     for (int i = 0; i < p_len; i++) {
  9.         hash1[p[i] - 'a']++;
  10.     }
  11.  
  12.     int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
  13.     int count = 0;
  14.     for (int left = 0, right = 0; right < s_len; right++) {
  15.         char in = s[right];
  16.         // 进窗口 + 维护 count
  17.         if (++hash2[in - 'a'] <= hash1[in - 'a']) {
  18.             count++;
  19.         }
  20.  
  21.         // 判断窗口是否超过大小
  22.         if (right - left + 1 > p_len) {
  23.             char out = s[left++];
  24.             // 出窗口 + 维护 count
  25.             if (hash2[out - 'a']-- <= hash1[out - 'a']) {
  26.                 count--;
  27.             }
  28.         }
  29.  
  30.         // 更新结果
  31.         if (count == p_len) {
  32.             ret[*returnSize] = left;
  33.             (*returnSize)++;
  34.         }
  35.     }
  36.  
  37.     return ret;
  38. }

1.字符频率统计 

  1.     int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
  2.     for (int i = 0; i < p_len; i++) {
  3.         hash1[p[i] - 'a']++;
  4.     }
  • hash1：长度为26的整数数组，用于统计字符串p中每个字符的出现次数。hash1[i]表示字符'a' + i在字符串p中的出现次数。
  • 循环遍历字符串p，更新hash1数组。

2.滑动窗口机制

  1.     int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
  2.     int count = 0;
  3.     for (int left = 0, right = 0; right < s_len; right++) {
  4.         char in = s[right];
  5.         // 进窗口 + 维护 count
  6.         if (++hash2[in - 'a'] <= hash1[in - 'a']) {
  7.             count++;
  8.         }
  • hash2：长度为26的整数数组，用于统计滑动窗口内每个字符的出现次数。
  • count：记录当前滑动窗口内与字符串p中字符频率一致的字符数。
  • 滑动窗口通过right指针不断向右移动，将字符s[right]加入窗口，同时更新hash2数组和count计数。

3.判断窗口大小并维护窗口内字符频率

  1.         // 判断窗口是否超过大小
  2.         if (right - left + 1 > p_len) {
  3.             char out = s[left++];
  4.             // 出窗口 + 维护 count
  5.             if (hash2[out - 'a']-- <= hash1[out - 'a']) {
  6.                 count--;
  7.             }
  8.         }
  • 检查滑动窗口的大小，如果窗口大小超过字符串p的长度（right - left + 1 > p_len），则需要移除窗口左侧的字符。
  • 更新left指针，移除窗口左侧字符，同时更新hash2数组和count计数。

4.更新结果

  1.         // 更新结果
  2.         if (count == p_len) {
  3.             ret[*returnSize] = left;
  4.             (*returnSize)++;
  5.         }
  6.     }
  7.  
  8.     return ret;
  9. }
  • 如果count等于字符串p的长度，说明当前窗口内字符频率与字符串p一致，将left指针的值加入结果数组ret。
  • 更新结果数组的大小*returnSize。

C++知识点详解

  • STL（Standard Template Library）: 向量 vector 是 STL 的一部分，提供动态数组的功能。
  • 范围 for 循环: C++11 引入的循环方式，简化了遍历操作。
  • 字符数组与频率统计: 使用数组来记录字符出现的频率，并进行简单的数学运算实现高效统计。
  • 双指针（Sliding Window）技巧: 通过两个指针控制一个窗口，用于高效地处理子串问题。
  • 成员函数与类: 通过类和成员函数组织代码，方便管理和调用。

1. STL（Standard Template Library）

向量 vector

概述：vector 是 C++ 标准模板库（STL）中的一个动态数组，可以根据需要动态调整大小。

特点：

  • 动态调整大小：vector 可以在运行时自动扩展和收缩。
  • 随机访问：支持使用索引进行随机访问，访问时间复杂度为 O(1)。
  • 内部实现：使用连续的内存块存储元素，类似于数组。

示例代码：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> vec = {1, 2, 3, 4, 5};
  6.     
  7.     // 添加元素到末尾
  8.     vec.push_back(6);
  9.     
  10.     // 随机访问
  11.     std::cout << "Element at index 2: " << vec[2] << std::endl;
  12.     
  13.     // 遍历向量
  14.     for(int i : vec) {
  15.         std::cout << i << " ";
  16.     }
  17.     
  18.     return 0;
  19. }

高级用法：

插入和删除：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> vec = {1, 2, 3, 4, 5};
  6.     
  7.     // 在指定位置插入元素
  8.     vec.insert(vec.begin() + 2, 99);
  9.     
  10.     // 删除指定位置的元素
  11.     vec.erase(vec.begin() + 4);
  12.     
  13.     // 遍历向量
  14.     for(int i : vec) {
  15.         std::cout << i << " ";
  16.     }
  17.     
  18.     return 0;
  19. }

 

 动态调整大小：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> vec(5, 10); // 创建一个大小为5的向量，初始值为10
  6.     
  7.     vec.resize(10, 20); // 调整向量大小为10，新增的元素值为20
  8.     
  9.     for(int i : vec) {
  10.         std::cout << i << " ";
  11.     }
  12.     
  13.     return 0;
  14. }

2. 范围 for 循环

概述：范围 for 循环是 C++11 引入的一种简化遍历容器的方式。

特点：

  • 简化代码：不需要显式地定义迭代器或索引变量。
  • 安全性：自动处理容器的边界，减少越界错误。

示例代码：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> vec = {1, 2, 3, 4, 5};
  6.     
  7.     for(int i : vec) {
  8.         std::cout << i << " ";
  9.     }
  10.     
  11.     return 0;
  12. }

 

高级用法：

使用引用遍历并修改元素：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> vec = {1, 2, 3, 4, 5};
  6.     
  7.     for(int& i : vec) {
  8.         i *= 2; // 每个元素乘以2
  9.     }
  10.     
  11.     for(const int& i : vec) {
  12.         std::cout << i << " ";
  13.     }
  14.     
  15.     return 0;
  16. }

3. 字符数组与频率统计

概述：字符数组用于存储字符的频率信息，通常用于字符串相关的算法中。

实现：使用大小为 26 的数组来记录每个小写字母的出现次数，数组索引对应字母的偏移量（例如 'a' 对应索引 0，'b' 对应索引 1）。

特点：

  • 高效：使用数组进行频率统计和比较，时间复杂度为 O(1)。
  • 简单：数组索引和字符的偏移量直接对应，易于实现和理解。

示例代码：

  1. #include <iostream>
  2. #include <string>
  3.  
  4. int main() {
  5.     std::string s = "hello";
  6.     int freq[26] = {0};
  7.     
  8.     for(char ch : s) {
  9.         freq[ch - 'a']++;
  10.     }
  11.     
  12.     for(int i = 0; i < 26; ++i) {
  13.         if (freq[i] > 0) {
  14.             std::cout << (char)('a' + i) << ": " << freq[i] << std::endl;
  15.         }
  16.     }
  17.     
  18.     return 0;
  19. }

高级用法：

判断两个字符串是否是字母异位词：

  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. bool isAnagram(std::string s1, std::string s2) {
  6.     if (s1.size() != s2.size()) return false;
  7.     
  8.     int freq[26] = {0};
  9.     
  10.     for(char ch : s1) {
  11.         freq[ch - 'a']++;
  12.     }
  13.     
  14.     for(char ch : s2) {
  15.         freq[ch - 'a']--;
  16.     }
  17.     
  18.     for(int i = 0; i < 26; ++i) {
  19.         if (freq[i] != 0) return false;
  20.     }
  21.     
  22.     return true;
  23. }
  24.  
  25. int main() {
  26.     std::string s1 = "listen";
  27.     std::string s2 = "silent";
  28.     
  29.     if (isAnagram(s1, s2)) {
  30.         std::cout << s1 << " and " << s2 << " are anagrams." << std::endl;
  31.     } else {
  32.         std::cout << s1 << " and " << s2 << " are not anagrams." << std::endl;
  33.     }
  34.     
  35.     return 0;
  36. }

4. 双指针（Sliding Window）技巧

概述：双指针技术通常用于处理数组或字符串中的子数组或子串问题。

实现：使用两个指针（左指针和右指针）来维护一个窗口，该窗口在数组或字符串中滑动，以寻找满足特定条件的子数组或子串。

特点：

  • 高效：通过调整指针位置来动态维护窗口，减少不必要的计算。
  • 灵活：可以用于解决多种问题，如最长子串、最短子串、子数组和等。

示例代码：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. int main() {
  5.     std::vector<int> nums = {1, 2, 3, 4, 5, 6};
  6.     int left = 0, right = 0, sum = 0, target = 10;
  7.     
  8.     while(right < nums.size()) {
  9.         sum += nums[right++];
  10.         
  11.         while(sum > target) {
  12.             sum -= nums[left++];
  13.         }
  14.         
  15.         if(sum == target) {
  16.             std::cout << "Subarray found from index " << left << " to " << right - 1 << std::endl;
  17.         }
  18.     }
  19.     
  20.     return 0;
  21. }

高级用法：

找到所有和为给定值的子数组：

  1. #include <vector>
  2. #include <iostream>
  3.  
  4. std::vector<std::pair<int, int>> findAllSubarrays(std::vector<int>& nums, int target) {
  5.     std::vector<std::pair<int, int>> result;
  6.     int left = 0, right = 0, sum = 0;
  7.     
  8.     while(right < nums.size()) {
  9.         sum += nums[right++];
  10.         
  11.         while(sum > target) {
  12.             sum -= nums[left++];
  13.         }
  14.         
  15.         if(sum == target) {
  16.             result.push_back({left, right - 1});
  17.         }
  18.     }
  19.     
  20.     return result;
  21. }
  22.  
  23. int main() {
  24.     std::vector<int> nums = {1, 2, 3, 4, 5, 6};
  25.     int target = 10;
  26.     
  27.     std::vector<std::pair<int, int>> subarrays = findAllSubarrays(nums, target);
  28.     
  29.     for(auto& p : subarrays) {
  30.         std::cout << "Subarray found from index " << p.first << " to " << p.second << std::endl;
  31.     }
  32.     
  33.     return 0;
  34. }

5. 成员函数与类

概述：类是 C++ 的基本面向对象编程（OOP）结构，用于封装数据和操作数据的方法。成员函数是类的函数，可以操作类的成员数据。

实现：

  • 类定义：使用 class 关键字定义类，类中可以包含数据成员和成员函数。
  • 成员函数：在类的内部定义的方法，可以操作类的成员变量。
  • 访问控制：通过 public, protected, private 控制成员的访问权限。

特点：

  • 封装性：将数据和操作封装在一起，提高代码的可维护性和可重用性。
  • 继承性：类可以通过继承复用已有代码。
  • 多态性：通过虚函数实现多态，提高代码的灵活性。

示例代码：

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. class Solution {
  6. public:
  7.     std::vector<int> findAnagrams(std::string s, std::string p) {
  8.         std::vector<int> ret;
  9.         int hash1[26] = { 0 };
  10.         for(auto ch : p) hash1[ch - 'a']++;
  11.         int hash2[26] = { 0 };
  12.         int m = p.size();
  13.         for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
  14.             char in = s[right];
  15.             if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
  16.             if(right - left + 1 > m) {
  17.                 char out = s[left++];
  18.                 if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
  19.             }
  20.             if(count == m) ret.push_back(left);
  21.         }
  22.         return ret;
  23.     }
  24. };
  25.  
  26. int main() {
  27.     Solution solution;
  28.     std::string s = "cbaebabacd";
  29.     std::string p = "abc";
  30.     std::vector<int> result = solution.findAnagrams(s, p);
  31.     for(int index : result) {
  32.         std::cout << index << " ";
  33.     }
  34.     return 0;
  35. }

 

高级用法：

类的继承：

  1. #include <iostream>
  2.  
  3. class Base {
  4. public:
  5.     void show() {
  6.         std::cout << "Base class" << std::endl;
  7.     }
  8. };
  9.  
  10. class Derived : public Base {
  11. public:
  12.     void show() {
  13.         std::cout << "Derived class" << std::endl;
  14.     }
  15. };
  16.  
  17. int main() {
  18.     Base* basePtr;
  19.     Derived derived;
  20.     basePtr = &derived;
  21.     
  22.     basePtr->show(); // 调用基类的 show 方法
  23.     derived.show();  // 调用派生类的 show 方法
  24.     
  25.     return 0;
  26. }

虚函数与多态：

  1. #include <iostream>
  2.  
  3. class Base {
  4. public:
  5.     virtual void show() {
  6.         std::cout << "Base class" << std::endl;
  7.     }
  8. };
  9.  
  10. class Derived : public Base {
  11. public:
  12.     void show() override {
  13.         std::cout << "Derived class" << std::endl;
  14.     }
  15. };
  16.  
  17. int main() {
  18.     Base* basePtr;
  19.     Derived derived;
  20.     basePtr = &derived;
  21.     
  22.     basePtr->show(); // 调用派生类的 show 方法，实现多态
  23.     
  24.     return 0;
  25. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/1008570
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号