数据结构第七章-哈希表
基础知识 ：哈希表定义
字符哈希
/*统计一个字符串里面各个字符的数量*/
int main(){
int char_map[128] = {0};//ASCII码从0-127，使用数组下标作为映射，最大范围到128
std::string str = "abcdefgaaxxy";
for (int i = 0; i < str.length(); i++){
char_map[str[i]]++;//把每一个字符通过ASCII码来映射到数组下标下
}
//char_map['a']++;相当于char_map[97]++
//char_map['b']++;相当于char_map[98]++
for (int i = 0; i < 128; i++){
if (char_map[i] > 0){
printf("[%c][%d] : %d\n", i, i, char_map[i]);
}
}
return 0;
}
哈希表排序整数
int main(){//哈希表排序，使用数组的下标对正整数进行排序
//哈希表长度需要超过最大待排序数字
int random[10] = {999, 1, 444, 7, 20, 9, 1, 3, 7, 7};
int hash_map[1000] = {0};
for (int i = 0; i < 10; i++){
hash_map[random[i]]++;
}
for (int i = 0; i < 1000; i++){//哈希表中的下标是原数字，哈希表中的数字是原数字的出现次数，遍历哈希表，当遇到出现的次数大于0就打印该点下标，出现几次打印几次
for (int j = 0; j < hash_map[i]; j++){
printf("%d\n", i);
}
}
return 0;
}
任意元素的映射
不同的整数或者字符串，由于哈希函数的处理，可能会被映射到同一个下标，产生冲突，此时哈希表不能正常完成映射
整数的哈希函数 ：直接对整数取余表长再返回
字符串的哈希函数：字符串中ASCII湘江得到整数取余表长
此时由于哈希函数的选择，不同的数字被映射到同一个下标，产生冲突
拉链法解决冲突，构造哈希表
[[链表，栈，队列，堆的补充内容#链表逆序——头插法|头插法的具体内容]] 头插法不需要遍历整个链表，单次插入的复杂度为O(1)
代码实现 hash_table[hash_key] 指的是这个是这个节点的链表头指向的位置 在没有进行哈希的时候 hash_table里面所有的值都是NULL
struct ListNode {//哈希表为普通的单链表
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int hash_func(int key, int table_len){
return key % table_len;//整数哈希函数
}
void insert(ListNode *hash_table[], ListNode *node, int table_len){
int hash_key = hash_func(node->val, table_len);//计算该节点的hash_key
node->next = hash_table[hash_key];//将当前的node->next指向当前的头节点（一开始的时候是NULL）
hash_table[hash_key] = node;//将该节点作为新的头节点
}
bool search(ListNode *hash_table[], int value, int table_len){//搜索元素
int hash_key = hash_func(value, table_len);//计算该节点的hash_key
ListNode *head = hash_table[hash_key];//找到对应头节点
while(head){//遍历该链表直到找到目标节点
if (head->val == value){
return true;
}
head = head->next;
}
return false;
}
测试代码
int main(){//TABLE_LEN取为质数，冲突会比其他数字少，为什么自己证
const int TABLE_LEN = 11;
ListNode *hash_table[TABLE_LEN] = {0};
std::vector<ListNode *> hash_node_vec;
int test[8] = {1, 1, 4, 9, 20, 30, 150, 500};
for (int i = 0; i < 8; i++){
hash_node_vec.push_back(new ListNode(test[i]));
}
for (int i = 0; i < hash_node_vec.size(); i++){
insert(hash_table, hash_node_vec[i], TABLE_LEN);
}
printf("Hash table:\n");
for (int i = 0; i < TABLE_LEN; i++){
printf("[%d]:", i);
ListNode *head = hash_table[i];
while(head){
printf("->%d", head->val);
head = head->next;
}
printf("\n");
}
printf("\n");
printf("Test search:\n");
for (int i = 0; i < 10; i++){
if (search(hash_table, i, TABLE_LEN)){
printf("%d is in the hash table.\n");
}
else{
printf("%d is not in the hash table.\n");
}
}
return 0;
}
哈希map与STLmap
迭代器（iterator）是一种设计模式，它提供了一种顺序访问容器中元素的方法，而无需暴露容器的内部实现细节。迭代器可以看作是一个指向容器中元素的指针，它提供了一些操作来遍历容器中的元素。
在 C++ 中，标准库中的许多容器都提供了迭代器来支持对容器中元素的遍历。例如，std::vector、std::list、std::set、std::map 等容器都提供了迭代器。
迭代器通常提供了以下几种操作：
*：解引用迭代器，访问当前元素的值。++：将迭代器移动到下一个元素。--：将迭代器移动到上一个元素（仅双向迭代器和随机访问迭代器支持）。- == 和！= 来判断两个迭代器是否相等
struct ListNode {
std::string key;//把字符串key映射为整数val
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main(){//将字符串key映射为整数val
std::map<std::string, int> hash_map;
std::string str1 = "abc";
std::string str2 = "aaa";
std::string str3 = "xxxxx";
hash_map[str1] = 1;
hash_map[str2] = 2;
hash_map[str3] = 100;
if (hash_map.find(str1) != hash_map.end()){
printf("%s is in hash_map, value is %d\n",
str1.c_str(), hash_map[str1]);//c_str()返回一个指向以空字符结尾的字符串的指针，字符串内容与str的内容相同，不能直接str,printf里面没有str类型，要用c_str()把str类型转化为指向str的指针
}
std::map<std::string, int> ::iterator it;//定义一个指向hash_map内部内容的迭代器来遍历hash_map
for (it = hash_map.begin(); it != hash_map.end(); it++){//迭代器指向hash_map的第一个元素，每次循环都增加
printf("hash_map[%s] = %d\n", it->first.c_str(), it->second);
} //it->first指向对应hash_map的键，it->second指向的hash_map的值（只有指向map或者unordered_map的函数才有这个first,second操作
return 0;
}
STL::map内部是由红黑树实现的 STL::unordered_map内部是由哈希表构成 没啥区别
最长回文串
#easy 409. 最长回文串 - 力扣（LeetCode） 已知一个只包括大小写字符的字符串，求用该字符串中的字符可以生成的最长回文字符串长度 示例
输入:s = "abccccdd"
输出:7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
输入:s = "a"
输出:1
用基础的字符哈希就行
有点贪心的感觉
*解决方法如下
class Solution {
public:
int longestPalindrome(std::string s) {
int char_map[128] = {0};//字符哈希
int max_length = 0;//回文串偶数部分的最大长度
int flag = 0;//是否有中心点
for (int i = 0; i < s.length(); i++){
char_map[s[i]]++;//遍历给定字符串建立哈希表
}
for (int i = 0; i < 128; i++){//遍历哈希表
if (char_map[i] % 2 == 0){//如果哈希表有偶数，则可以前面放一个后面放一个
max_length += char_map[i];//最大长度相当于该字符出现的次数
}
else{//如果为奇数，就去掉一个，把flag设置为1，多的一个作为中心点备用
max_length += char_map[i] - 1;//剩下的仍为偶数,前面一个后面一个
flag = 1;
}
}
return max_length + flag;//最终结果为最长的回文串加上中心点。如果没有中心点flag是0
}
};
词语模式
#easy 290. 单词规律 - 力扣（LeetCode） 已知字符串pattern与字符串str，确认str是否与pattern匹配，str和pattern匹配代表字符串str中的单词和pattern中的字符一一对应（其中pattern中只包含小写字符，str中的单词只包含小写字符，用空格分割）
示例
示例1:
输入: pattern = "abba", s = "dog cat cat dog"
输出: true
示例 2:
输入:pattern = "abba", s = "dog cat cat fish"
输出: false
算法思路
解决方法如下
class Solution {
public:
bool wordPattern(std::string pattern, std::string str) {
std::map<std::string, char> word_map;//单词到pattern字符的映射
char used[128] = {0};//pattern字符到已使用字符的映射
std::string word;//临时拆分出的单词
int pos = 0;//当前指向pattern字符，指针
str.push_back(' ');//往str后面push一个空格，让其碰到空格就拆分单词
for (int i = 0; i < str.length(); i++){//遍历整个str
if (str[i] == ' '){//遇到空格就拆分出新单词
if (pos == pattern.length()){//分割出一个单词，但是已经没有pattern字符与之对应（4个单词2个pattern的情况）
return false;
}
if (word_map.find(word) == word_map.end()){//当在哈希表里面没有找到与该单词对应的映射
if (used[pattern[pos]]){//如果当前的字符已经使用过
return false;
}
word_map[word] = pattern[pos];//没有使用过，则建立该单词与对应字符进行映射
used[pattern[pos]] = 1;//字符与used进行映射，标记该字符已使用
}
else{
if (word_map[word] != pattern[pos]){//如果这个单词出现，但是它本来的映射字符不是目前的字符
return false;
}
}
word = "";//完成一个单词的插入和查询，清空word
pos++;//指向pattern的字符指针前移
}
else{//否则把字符录入word
word += str[i];
}
}
if (pos != pattern.length()){//如果全部遍历完成发现还有没有使用过的pattern
return false;
}
return true;
}
};
同字符词语分组
#medium 49. 字母异位词分组 - 力扣（LeetCode） 已知一组字符串，将所有由颠倒字母顺序而构成的字放到一起输出
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
思路 显然，如果某两个字符串，出现的各个字符数相同,则他们应该在同一组
方法1
解决方法如下
class Solution {
public:
std::vector<std::vector<std::string> > groupAnagrams(
std::vector<std::string>& strs) {
std::map<std::string, std::vector<std::string> > anagram;//内部排序的各个单词为key，以字符串向量为value，存储各个字符数量相同的字符串
std::vector<std::vector<std::string> > result; //存储最终结果
for (int i = 0; i < strs.size(); i++){//遍历各个单词
std::string str = strs[i];//建立临时str储存这个单词
std::sort(str.begin(), str.end());//对该单词进行排序
if (anagram.find(str) == anagram.end()){//如果在anagram里面没有找到这个key
std::vector<std::string> item;//建立一个空的字符串向量
anagram[str] = item;//建立该Key与字符串向量的映射
}
anagram[str].push_back(strs[i]);//把目前的这个单词push进这个key对应的字符串向量里面
}
std::map<std::string, std::vector<std::string> > ::iterator it;//定义迭代器遍历map
for (it = anagram.begin(); it != anagram.end(); it++){//遍历整个map
result.push_back((*it).second);//把map的结果push进result
}
return result;
}
};
BTW 一般来说如果该函数是传递引用的话尽量不要再内部对内容进行修改
方法2
解决方法如下
void change_to_vector(std::string &str, std::vector<int> &vec){//把字符串转化为vector
for (int i = 0; i < 26; i++){//将整个vector重置为0
vec.push_back(0);
}
for (int i = 0; i < str.length(); i++){//遍历字符串和vec进行映射
vec[str[i]-'a']++;//对应下标的点变为1
}
}
class Solution {
public:
std::vector<std::vector<std::string> > groupAnagrams(
std::vector<std::string>& strs) {
std::map<std::vector<int>, std::vector<std::string> > anagram;//哈希表
std::vector<std::vector<std::string> > result; //最终结果
for (int i = 0; i < strs.size(); i++){//遍历给定字符向量
std::vector<int> vec;//新建一个vec
change_to_vector(strs[i], vec);//把vec与str进行映射
if (anagram.find(vec) == anagram.end()){//如果再哈希表中没有找到该vec
std::vector<std::string> item;//新建一个空字符串向量
anagram[vec] = item;//建立空字符向量和哈希表的映射
}
anagram[vec].push_back(strs[i]);//把这个字符串Push进哈希表
}
std::map<std::vector<int>,
std::vector<std::string> > ::iterator it;//遍历哈希表push进result
for (it = anagram.begin(); it != anagram.end(); it++){
result.push_back((*it).second);
}
return result;
}
};
方法3
#未完成
这个方法有点歪门邪道，有点意思，但是无法处理大规模的数据，乐扣117/118不能AC
这个方法的主要思路是把26个字母全部映射为质数，这样只需要计算每一个字符串的乘积，这样可以避免哈希冲突，因为每一个数的质因数分解都是唯一的
代码如下
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<char, int> map = {//建立字母和质数之间的映射
{'a',2},{'b',3},{'c',5},{'d',7},{'e',11},{'f',13},{'g',17},{'h',19},{'i',23},{'j',29},{'k',31},{'l',37},{'m',41},
{'n',43},{'o',47},{'p',53},{'q',59},{'r',61},{'s',67},{'t',71},{'u',73},{'v',79},{'w',83},{'x',89},{'y',97},{'z',101}
};
unordered_map<unsigned long long, vector<string>> resmap;//建立乘数和字符串向量之间的映射
vector<vector<string>> reslist;//最终结果
for (string str : strs) {//遍历strs里面的每一个字符串，命名为str(C++语法)
unsigned long long m = 1;//初始化乘积
for (int i = 0; i < str.size(); i++) {//遍历目前的字符串，算出当前字符的乘积
m *= map[str[i]];
}
if (resmap.find(m) == resmap.end()) {//如果在map里面没有找到
resmap[m] = {};//定义一个空的字符串向量
}
resmap[m].push_back(str);//把结果的字符串push进刚刚建立映射的字符串向量里面
}
for (auto it : resmap) {//遍历的map里面的每一个键值对，auto是自动推断变量类型,此时it是一个pair
reslist.push_back(it.second);//把遍历的结果push进入最终结果
}
return reslist;
}
};
然而 unsigned long long 类型的最高得精度是$2^{64}-1$ 所有当乘积大于这个数的时候就会出现错误
比如示例
输入：
["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"]
输出：
[["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa","aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"]]
预期结果：
[["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"],["aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]]
这里面有98个a，自然爆掉了
无重复字符的最长字串
#medium 3. 无重复字符的最长子串 - 力扣（LeetCode） 已知一个字符串，求用该字符串的无重复字符的最长字串的长度 示例 ：
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
注意：字串必须得是连续的，子序列可以不是连续的
计算出所有字串的时间复杂度为O($n^2$)
滑动窗口算法
解决方法如下
class Solution {
public:
int lengthOfLongestSubstring(std::string s) {
int begin = 0;//窗口的头指针
int result = 0;//最后结果
std::string word = "";//窗口内的字符串
int char_map[128] = {0};//hashmap来统计各个字符出现频次
for (int i = 0; i < s.length(); i++){//i向前滑动
char_map[s[i]]++;
if (char_map[s[i]] == 1){//word里面没有出现过该字符
word += s[i];//把word里面依次储存s[i]对应的字符
if (result < word.length()){//如果当前结果比word长度小
result = word.length();//当前result更新为word的长度
}
}
else{//word里面出现已经出现过的字符了,将重复的字符删去
while(begin < i && char_map[s[i]] > 1){//begin指针向前移动，直到到达i的或者i对应的字符频次等于1
char_map[s[begin]]--;//减少begin指向字符的出现频次
begin++;//前移begin
}
word = "";//重新更新word
for (int j = begin; j <= i; j++){
word += s[j];//把更新后的窗口中的字符push进入word
}
}
}
return result;
}
};
重复的DNA序列
#medium 187. 重复的DNA序列 - 力扣（LeetCode） 将DNA序列就看作只包含["A','C','G','T']的4个字符的字符串，给定一个DNA字符串，找到所有长度为10且出现超过1次的字串 示例
示例 1：
输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：
输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]
方法1： 枚举
#easy
枚举里面所有长度为10的，遍历字符哈希，取出出现次数大于1的字串就行
解决方法如下
class Solution {
public:
std::vector<std::string> findRepeatedDnaSequences(std::string s) {
std::map<std::string, int> word_map;//单词和单词数量的字符哈希
std::vector<std::string> result;//最终结果
for (int i = 0; i < s.length(); i++){//遍历整个字符串
std::string word = s.substr(i, 10);//取出以i为开头长度为10的一个字符串，substr第一个参数为起点，第二个参数为取出的长度
word_map[word]++;//增加该串字符的出现次数
}
std::map<std::string, int> ::iterator it;//定义一个迭代器来指向map的每一个键值对（实际类型是pair)
for (it = word_map.begin(); it != word_map.end(); it++){//遍历整个哈希表
if (it->second > 1){//当出现频率大于1的时候取出该字符串
result.push_back(it->first);
}
}
return result;
}
};
这方法有够草率
方法2 ：滚动哈希
#hard
方法2会比方法1快很多，位运算的计算效率很高
整数哈希必须得是全局的，因为数组太大了
关于左移运算转化为整数
以s="ACGT"为例
当 i = 3时，s[i] = 'T'，所以 char_map[s[i]] = 3（11）。将 key 左移两位后仍然为 0，然后加上 char_map[s[i]] 的值变为 3（11）。因此，此时 key = 3。
当 i = 2 时，s[i] = 'G'，所以 char_map[s[i]] = 2（10）。将 key 左移两位后变为 12（1100），然后加上 char_map[s[i]] 的值变为 14（1110）。因此，此时 key = 14。
当 i = 1 时，s[i] = 'C'，所以 char_map[s[i]] = 1（01）。将 key 左移两位后变为 56（111000），然后加上 char_map[s[i]] 的值变为 57（111001）。因此，此时 key = 57。
当 i = 0 时，s[i] = 'A'，所以 char_map[s[i]] = 0（00）。将 key 左移两位后变为 228（11100100），然后加上 char_map[s[i]] 的值仍然为 228（11100100）。因此，最终我们得到的哈希值为 key = 228。
关于位运算的迭代
以AAAAACCCCTT为例，此时的key为11010101010000000000
向右进行迭代
首先，我们需要将字符 “T” 映射到一个 2 位的二进制数。在这段代码中，字符 ‘T’ 被映射为 11。
然后，我们利用滚动哈希来快速更新哈希键值。
1. 将当前哈希键值右移两位，得到 001101010101000000。这相当于删除最旧的字符。
2. 将新字符 “T” 对应的二进制数左移 18 位，得到 110000000000000000。
3. 用按位或运算符将上一步得到的结果添加到键值的高位，得到 111101010101000000。这就是加入新字符 “T” 后的哈希键值。
看懂了吧，我真是好人
解决方法如下
int g_hash_map[1048576] = {0};//哈希太大了，需要全局数组
std::string change_int_to_DNA(int DNA){//将一个长度为10的片段从整数转化为字符串
static const char DNA_CHAR[] = {'A', 'C', 'G', 'T'};
std::string str;
for (int i = 0; i < 10; i++){
str += DNA_CHAR[DNA & 3];//DNA&3是取得二进制序列的最右边的两个二进制数
DNA = DNA >> 2;//向右移动两位，处理新的二进制数
}
return str;
}
class Solution {
public:
std::vector<std::string> findRepeatedDnaSequences(std::string s) {
std::vector<std::string> result;
if (s.length() < 10){
return result;
}
for (int i = 0; i < 1048576; i++){//每次调用时需要更新全局数组
g_hash_map[i] = 0;
}
int char_map[128] = {0};//设置字符到证书的转换数组
char_map['A'] = 0;
char_map['C'] = 1;
char_map['G'] = 2;
char_map['T'] = 3;
int key = 0;//把DNA字符串的前10个字符进行编码
for (int i = 9; i >= 0; i--){
key = (key << 2) + char_map[s[i]];
}
g_hash_map[key] = 1;
for (int i = 10; i < s.length(); i++){//滚动哈希，到下一个序列
key = key >> 2;
key = key | (char_map[s[i]] << 18);
g_hash_map[key]++;
}
for (int i = 0; i < 1048576; i++){//频率大于1的时候，解码后push进结果里面
if (g_hash_map[i] > 1){
result.push_back(change_int_to_DNA(i));
}
}
return result;
}
};
最小窗口子串
#hard 76. 最小覆盖子串 - 力扣（LeetCode） 已知字符串S和字符串T，求S中的最小窗口（区间），使得这个区间中包含了字符串T中的所有字符
示例：
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
预备知识
bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){
for (int i = 0; i < vec_t.size(); i++){//利用vec_t遍历t中出现的字符
if (map_s[vec_t[i]] < map_t[vec_t[i]]){
return false;//如果s中出现的字符小于t中出现该字符的数量
}
}
return true;
}
int main(){
std::string s = "ADOBECODEBANC";
std::string t = "ABCDAB";
const int MAX_ARRAY_LEN = 128;//char 0-127，利用数组下表记录字符个数
int map_t[MAX_ARRAY_LEN] = {0};//记录t字符串各字符个数
int map_s[MAX_ARRAY_LEN] = {0};//记录s字符串各字符个数
std::vector<int> vec_t;//记录t字符串有那些字符
for (int i = 0; i < s.length(); i++){
map_s[s[i]]++;//遍历s，记录s字符串各字符个数
}
for (int i = 0; i < t.length(); i++){
map_t[t[i]]++;//遍历t，记录t字符串各字符个数
}
for (int i = 0; i < MAX_ARRAY_LEN; i++){
if (map_t[i] > 0){
vec_t.push_back(i);
}//遍历，将字符串t中出现的字符存储到vec_t里面（存的是ASCII码）
}
/*测试代码*/
printf("String S %s 's char number:\n", s.c_str());
for (int i = 0; i < MAX_ARRAY_LEN; i++){
if (map_s[i]>0){
printf("%c : %d\n", i, map_s[i]);
}
}
printf("String T %s 's char number:\n", t.c_str());
for (int i = 0; i < MAX_ARRAY_LEN; i++){
if (map_t[i]>0){
printf("%c : %d\n", i, map_t[i]);
}
}
printf("String T %s 's char:\n", t.c_str());
for(int i = 0; i < vec_t.size(); i++){
printf("%c\n",vec_t[i]);
}
printf("is_window_ok = %d\n", is_window_ok(map_s, map_t, vec_t));
return 0;
}
算法思路
本题与[[第七章： 哈希表与字符串#无重复字符的最长字串|该题]]思路类似
解决方法如下
class Solution {
private:
bool is_window_ok(int map_s[], int map_t[], std::vector<int> &vec_t){//判断所有字符是否在t里面
for (int i = 0; i < vec_t.size(); i++){
if (map_s[vec_t[i]] < map_t[vec_t[i]]){
return false;
}
}
return true;
}
public:
std::string minWindow(std::string s, std::string t) {
const int MAX_ARRAY_LEN = 128;
int map_t[MAX_ARRAY_LEN] = {0};
int map_s[MAX_ARRAY_LEN] = {0};
std::vector<int> vec_t;
for (int i = 0; i < t.length(); i++){
map_t[t[i]]++;
}
for (int i = 0; i < MAX_ARRAY_LEN; i++){
if (map_t[i] > 0){
vec_t.push_back(i);
}
}
/*最小窗户代码*/
int window_begin = 0;//最小窗口
std::string result; //最小窗口对应的字符串
for (int i = 0; i < s.length(); i++){//i代表窗口的尾指针
map_s[s[i]]++;//将尾指针指向的字符添加到窗口表示map
while(window_begin < i){//窗口指针不能超过尾指针
char begin_ch = s[window_begin];//备份对应字符
if (map_t[begin_ch] == 0){//如果当前头指针指向的字符没有
window_begin++;//begin前移
}
else if (map_s[begin_ch] > map_t[begin_ch]){//如果头指针指向的字符出现在T里面，但是窗口里面有超过T个对应字符
map_s[begin_ch]--;//指向字符频率减少
window_begin++;//前移
}
else{
break;//如果不是1，2 不能前移
}
}
if (is_window_ok(map_s, map_t, vec_t)){//计算新字符串长度，如果map_s所有字符和频率都在map_t里面
int new_window_len = i - window_begin + 1;//当前窗口长度是窗口头指针减去窗口尾指针加一
if (result == "" || result.length() > new_window_len){
result = s.substr(window_begin, new_window_len);//结果字符串，或者当前窗口的字符串更小的时候更新结果
}//替换窗口所对应的字符串
}
}
return result;
}
};
本文是原创文章，采用 CC BY-NC-ND 4.0 协议，完整转载请注明来自 name1110
阅读建议
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果