专栏:优选算法
给定两个字符串 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
仅包含小写字母“abc”的异位词 有:abc,acb,bac,bca,cab,cba;
输出: [0,6](子串的起始索引)
1.两个字符串都按照字符顺序排序,然后比较是否相等 排序+比较 nlogn +n
2.统计每个字符出现的次数 哈希表遍历比较
因为字符串p 的异位词的⻓度“m”⼀定与字符串p的⻓度相同,所以我们可以在字符串 s 中构 造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝,并在滑动中维护窗⼝中每种字⺟的数量;保持窗口大小一次遍历比较。
可以⽤两个⼤⼩为 26 的数组来模拟哈希表,⼀个来保存 s 中的⼦串每个字符出现的个 数,另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
利用变化量count来统计窗口中“有效字符的次数”;
当窗⼝中每种字⺟的数量与字符串p中每种字⺟的数量相同时,则说明当前窗⼝为字符串 p 的异位词;
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
int m = p.size();
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
// 进窗⼝ + 维护 count
if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
if(right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
}
// 更新结果
if(count == m) ret.push_back(left);
}
return ret;
}
};
for(auto ch : p) hash1[ch - 'a']++;
for
循环: 用于遍历字符串 p
,并统计每个字符的出现次数。ch - 'a'
: 将字符转换为数组索引,例如 'a'
对应 0
,'b'
对应 1
。left
, right
, count
: left
和 right
分别表示窗口的左边界和右边界,count
用于记录匹配字符的数量。for
循环: 遍历字符串 s
,右指针 right
不断向右移动。s[right]
加入窗口并更新频率数组 hash2
。如果该字符的频率没有超过 hash1
中的频率,则计数器 count
加一。m
时,将 s[left]
移出窗口,并更新频率数组 hash2
和计数器 count
。count
等于 m
,说明当前窗口是一个字母异位词,记录起始索引 left
。int* findAnagrams(char * s, char * p, int* returnSize) {
int s_len = strlen(s); // 使用 strlen 计算字符串 s 的长度
int p_len = strlen(p); // 使用 strlen 计算字符串 p 的长度
int *ret = (int *)malloc(s_len * sizeof(int));
*returnSize = 0;
int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
for (int i = 0; i < p_len; i++) {
hash1[p[i] - 'a']++;
}
int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
int count = 0;
for (int left = 0, right = 0; right < s_len; right++) {
char in = s[right];
// 进窗口 + 维护 count
if (++hash2[in - 'a'] <= hash1[in - 'a']) {
count++;
}
// 判断窗口是否超过大小
if (right - left + 1 > p_len) {
char out = s[left++];
// 出窗口 + 维护 count
if (hash2[out - 'a']-- <= hash1[out - 'a']) {
count--;
}
}
// 更新结果
if (count == p_len) {
ret[*returnSize] = left;
(*returnSize)++;
}
}
return ret;
}
int hash1[26] = {0}; // 统计字符串 p 中每个字符出现的个数
for (int i = 0; i < p_len; i++) {
hash1[p[i] - 'a']++;
}
hash1
:长度为26的整数数组,用于统计字符串p
中每个字符的出现次数。hash1[i]
表示字符'a' + i
在字符串p
中的出现次数。p
,更新hash1
数组。 int hash2[26] = {0}; // 统计窗口里面的每一个字符出现的个数
int count = 0;
for (int left = 0, right = 0; right < s_len; right++) {
char in = s[right];
// 进窗口 + 维护 count
if (++hash2[in - 'a'] <= hash1[in - 'a']) {
count++;
}
hash2
:长度为26的整数数组,用于统计滑动窗口内每个字符的出现次数。count
:记录当前滑动窗口内与字符串p
中字符频率一致的字符数。right
指针不断向右移动,将字符s[right]
加入窗口,同时更新hash2
数组和count
计数。 // 判断窗口是否超过大小
if (right - left + 1 > p_len) {
char out = s[left++];
// 出窗口 + 维护 count
if (hash2[out - 'a']-- <= hash1[out - 'a']) {
count--;
}
}
p
的长度(right - left + 1 > p_len
),则需要移除窗口左侧的字符。left
指针,移除窗口左侧字符,同时更新hash2
数组和count
计数。 // 更新结果
if (count == p_len) {
ret[*returnSize] = left;
(*returnSize)++;
}
}
return ret;
}
count
等于字符串p
的长度,说明当前窗口内字符频率与字符串p
一致,将left
指针的值加入结果数组ret
。*returnSize
。vector
是 STL 的一部分,提供动态数组的功能。for
循环: C++11 引入的循环方式,简化了遍历操作。向量 vector
概述:vector
是 C++ 标准模板库(STL)中的一个动态数组,可以根据需要动态调整大小。
特点:
vector
可以在运行时自动扩展和收缩。示例代码:
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 添加元素到末尾
vec.push_back(6);
// 随机访问
std::cout << "Element at index 2: " << vec[2] << std::endl;
// 遍历向量
for(int i : vec) {
std::cout << i << " ";
}
return 0;
}
高级用法:
插入和删除:
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 在指定位置插入元素
vec.insert(vec.begin() + 2, 99);
// 删除指定位置的元素
vec.erase(vec.begin() + 4);
// 遍历向量
for(int i : vec) {
std::cout << i << " ";
}
return 0;
}
动态调整大小:
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec(5, 10); // 创建一个大小为5的向量,初始值为10
vec.resize(10, 20); // 调整向量大小为10,新增的元素值为20
for(int i : vec) {
std::cout << i << " ";
}
return 0;
}
for
循环概述:范围 for
循环是 C++11 引入的一种简化遍历容器的方式。
特点:
示例代码:
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for(int i : vec) {
std::cout << i << " ";
}
return 0;
}
高级用法:
使用引用遍历并修改元素:
#include <vector>
#include <iostream>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
for(int& i : vec) {
i *= 2; // 每个元素乘以2
}
for(const int& i : vec) {
std::cout << i << " ";
}
return 0;
}
概述:字符数组用于存储字符的频率信息,通常用于字符串相关的算法中。
实现:使用大小为 26 的数组来记录每个小写字母的出现次数,数组索引对应字母的偏移量(例如 'a' 对应索引 0,'b' 对应索引 1)。
特点:
示例代码:
#include <iostream>
#include <string>
int main() {
std::string s = "hello";
int freq[26] = {0};
for(char ch : s) {
freq[ch - 'a']++;
}
for(int i = 0; i < 26; ++i) {
if (freq[i] > 0) {
std::cout << (char)('a' + i) << ": " << freq[i] << std::endl;
}
}
return 0;
}
高级用法:
判断两个字符串是否是字母异位词:
#include <iostream>
#include <string>
#include <algorithm>
bool isAnagram(std::string s1, std::string s2) {
if (s1.size() != s2.size()) return false;
int freq[26] = {0};
for(char ch : s1) {
freq[ch - 'a']++;
}
for(char ch : s2) {
freq[ch - 'a']--;
}
for(int i = 0; i < 26; ++i) {
if (freq[i] != 0) return false;
}
return true;
}
int main() {
std::string s1 = "listen";
std::string s2 = "silent";
if (isAnagram(s1, s2)) {
std::cout << s1 << " and " << s2 << " are anagrams." << std::endl;
} else {
std::cout << s1 << " and " << s2 << " are not anagrams." << std::endl;
}
return 0;
}
概述:双指针技术通常用于处理数组或字符串中的子数组或子串问题。
实现:使用两个指针(左指针和右指针)来维护一个窗口,该窗口在数组或字符串中滑动,以寻找满足特定条件的子数组或子串。
特点:
示例代码:
#include <vector>
#include <iostream>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
int left = 0, right = 0, sum = 0, target = 10;
while(right < nums.size()) {
sum += nums[right++];
while(sum > target) {
sum -= nums[left++];
}
if(sum == target) {
std::cout << "Subarray found from index " << left << " to " << right - 1 << std::endl;
}
}
return 0;
}
高级用法:
找到所有和为给定值的子数组:
#include <vector>
#include <iostream>
std::vector<std::pair<int, int>> findAllSubarrays(std::vector<int>& nums, int target) {
std::vector<std::pair<int, int>> result;
int left = 0, right = 0, sum = 0;
while(right < nums.size()) {
sum += nums[right++];
while(sum > target) {
sum -= nums[left++];
}
if(sum == target) {
result.push_back({left, right - 1});
}
}
return result;
}
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
int target = 10;
std::vector<std::pair<int, int>> subarrays = findAllSubarrays(nums, target);
for(auto& p : subarrays) {
std::cout << "Subarray found from index " << p.first << " to " << p.second << std::endl;
}
return 0;
}
概述:类是 C++ 的基本面向对象编程(OOP)结构,用于封装数据和操作数据的方法。成员函数是类的函数,可以操作类的成员数据。
实现:
class
关键字定义类,类中可以包含数据成员和成员函数。public
, protected
, private
控制成员的访问权限。特点:
示例代码:
#include <iostream>
#include <vector>
#include <string>
class Solution {
public:
std::vector<int> findAnagrams(std::string s, std::string p) {
std::vector<int> ret;
int hash1[26] = { 0 };
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 };
int m = p.size();
for(int left = 0, right = 0, count = 0; right < s.size(); right++) {
char in = s[right];
if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
if(right - left + 1 > m) {
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
}
if(count == m) ret.push_back(left);
}
return ret;
}
};
int main() {
Solution solution;
std::string s = "cbaebabacd";
std::string p = "abc";
std::vector<int> result = solution.findAnagrams(s, p);
for(int index : result) {
std::cout << index << " ";
}
return 0;
}
高级用法:
类的继承:
#include <iostream>
class Base {
public:
void show() {
std::cout << "Base class" << std::endl;
}
};
class Derived : public Base {
public:
void show() {
std::cout << "Derived class" << std::endl;
}
};
int main() {
Base* basePtr;
Derived derived;
basePtr = &derived;
basePtr->show(); // 调用基类的 show 方法
derived.show(); // 调用派生类的 show 方法
return 0;
}
虚函数与多态:
#include <iostream>
class Base {
public:
virtual void show() {
std::cout << "Base class" << std::endl;
}
};
class Derived : public Base {
public:
void show() override {
std::cout << "Derived class" << std::endl;
}
};
int main() {
Base* basePtr;
Derived derived;
basePtr = &derived;
basePtr->show(); // 调用派生类的 show 方法,实现多态
return 0;
}