Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

c++ 哈希表find_Leecode刷题---哈希表与字符串

作者：Gausst松鼠会 | 2024-03-13 02:55:33

踩

哈希表find函数

哈希表，Hash table,也叫散列表，是根据关键字值（key）直接进行访问的数据结构，它通过把关键字值映射到表中一个位置（数组下标）来直接访问，以加快查找关键字值的速度，这个映射函数叫做哈希函数，存放记录的数组叫做哈希表

给定表M，存在函数f，对任意的关键字值key，带入函数后若能得到包含该关键字的表中地址，称表M为哈希（Hash）表，函数（key）为哈希函数。

预备知识1：最简单的哈希--字符哈希

统计字符型中的字符个数


#include<stdio.h>
#include<string>
 
int main()
{
    int char_map[128] = {0}; //ASCII码共有128个字符
    std::string str = "abcdefgaaxxy";
 
    for(int i = 0;i<str.length();i++)
    {
        char_map[str[i]]++;
    }
    for(int i = 0;i<128;i++)
    {
        if(char_map[i] > 0)
        {
            printf("[%c][%d]: %dn",i,i,char_map[i]);
        }
    }
    return 0;
}

预备知识2 ：哈希表排序整数


#include<stdio.h>
#include<string>
 
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++)
    {
        for(int j = 0;j<hash_map[i];j++)
        {
            printf("%dn",i);
        }
    }
    return 0;
}

输出：

思考：

1.当遇到负数，或非常大的整数，如何进行哈希

2当遇到字符串，如何进行哈希

3.当遇到其他无法直接映射的数据类型，如浮点数，数组，对象等等，如何进行哈希（映射）？

解决：利用哈希函数，将key（大整数，负数，浮点数）转换为整数再对表长取余，从而key转换为关键字被转换为哈希表的表长范围内的整数。

问题引入2，发生冲突：不同的整数或者字符串，由于哈希函数的选择，被映射到了同一个下标下；


#include<stdio.h>
#include<string>
 
int int_func(int key,int table_len)
{
   return key % table_len;
}
int string_func(std::string key,int table_len)
{
    int sum = 0;
    for(int i = 0;i<key.length();i++)
    {
        sum += key[i];
    }
    return sum % table_len;
}
 
int main()
{
    const int TABLE_LEN = 10;
    int hash_map[TABLE_LEN] = {0};
    hash_map[int_func(99999995,TABLE_LEN)]++;
    hash_map[int_func(5,TABLE_LEN)]++;
    hash_map[string_func("abc",TABLE_LEN)]++;
    hash_map[string_func("bac",TABLE_LEN)]++;
    for(int i =0;i<TABLE_LEN;i++)
    {
        printf("hash_map[%d] = %dn",i,hash_map[i]);
    }
    return 0;
}

输出

预备知识：拉链法解决冲突，构造哈希表

将所有哈希表结果相同的结点连接在同一个单链表中。

若选定的哈希表长度为m，则可将哈希表定义一个长度为m的指针数组t[0,...m-1],指针数组中的每个指针指向哈希函数结果相同的单链表

插入value：

将元素value插入哈希表，若元素value的哈希函数值为hash_key，将value对应的节点以头插法的方法插入到t[hash_key]为头指针的单链表中

查找value：

若元素value的哈希函数值为hash_key,遍历以t[hash_key]为头指针的单链表，查找链表各个节点的值域是否为value


#include<stdio.h>
 
 
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);
    node->next =  hash_table[hash_key];
    hash_table[hash_key] = node;
}
 
bool search(ListNode *hash_table[],int value,int table_len)
{
    int hash_key = hash_func(value,table_len);
    ListNode *head = hash_table[hash_key];
    while(head)
    {
        if(head->val==value)
        {
            return true;
        }
        head=head->next;
    }
    return false;
}

测试一下


int main()
{
    const int TABLE_LEN = 11; //hash表长度尽量为质数；
    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("HashTable: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;
}

预备知识3：哈希map与STL map


#include<stdio.h>
#include<string>
#include<map>
 
struct ListNode
{
    std::string key;
    int val;
    ListNode *next;
    ListNode(int x):val(x),next(NULL) {}
};
 
int main()
{
    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()) //c_str:返回当前字符串的首字符地址
    {
        printf("%s is in hash_map,value is %dn",str1.c_str(),hash_map[str1]);
    }
 
    std::map<std::string,int> :: iterator it;
    for(it = hash_map.begin();it != hash_map.end();it++)
    {
        printf("hash_map[%s] = %dn",it->first.c_str(),it->second);
    }
}

输出：

leecode刷题

409 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。

注意:

假设字符串的长度不会超过 1010。

示例 1:

输入:

"abccccdd"

输出:

解释:

我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

来源：力扣（LeetCode）

链接：力扣

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考：

1.查找出字符中所有字符的个数

2.回文字符串要分字符数量为偶数和奇数两种情况

偶数：

全部都会用上，头部放一个字符，尾部就对应放一个

奇数：丢掉一个字符，剩下的字符数为偶数个，按照字符数量为偶数的字符处理

随机选择一个字符当作中心字符

算法思路：

1.利用字符哈希方法，统计字符串中所有的字符数量；

2.设置最长回文串偶数字符长度max_length=0;

3.设置是否有中心点标记 flag = 0；

4.遍历每一个字符，字符数为count，若count为偶数，max_length += count;若count为奇数，max_length += count - 1, flag = 1;

5.最终最长回文子串长度：max_length + flag


class Solution {
public:
    int longestPalindrome(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
            {
                max_length+=char_map[i]-1;
                flag =1;
            }
        }
        return max_length +flag;
    }
};

290:词语模式

给定一种规律 pattern 和一个字符串 str ，判断 str 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", str = "dog cat cat dog"

输出: true

示例 2:

输入:pattern = "abba", str = "dog cat cat fish"

输出: false

示例 3:

输入: pattern = "aaaa", str = "dog cat cat dog"

输出: false

示例 4:

输入: pattern = "abba", str = "dog dog dog dog"

输出: false

来源：力扣（LeetCode）

链接：力扣

分析：1，当拆解出一个单词时，若该单词已出现，则当前单词对应的pattern字符必为该单词曾经对应的pattern字符；

2.当拆解出一个单词时，若该单词未曾出现，则当前单词对应得到pattern字符也必须未曾出现。

3.单词的个数与pattern字符串中出现的字符数量相同

算法思路：

若pattern=“abb?”,string="dog cat dog *"

1.设置单词（字符串）到pattern字符中的映射（哈希）；使用数组used[128]记录pattern字符串是否使用过；

2.遍历str，按照空格拆分单词，同时对应的向前移动指向pattern字符的指针，每拆分出一个单词，判断：

如果该单词从未出现在哈希表中：

如果当前pattern已经被使用，返回false；

否则将单词与所指向的pattern做映射；标记pattern已经被使用；

否则：

如果当前单词在哈希表中的映射字符不是当前指向的pattern字符，则返回false；

3.若单词个数与pattern字符个数不匹配，返回false


class Solution {
public:
    bool wordPattern(string pattern, string str) {
 
        std::map<std::string,char> word_map; //单词到字符的映射
        char used[128]={0};
        std::string word;//临时保存的单词；
        int pos = 0;//当前指向pattern的字符
        str.push_back(' ');
        for(int i =0;i<str.length();i++)
        {
            if(str[i]==' ') //拆分出一个字符
            {
                if( pos==pattern.length())
                {
                    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;
                }
                else
                {
                    if(word_map[word]!=pattern[pos])
                    {
                        return false;
                    }
                }
                word="";
                pos++;
            }
            else
            {
                word+=str[i];
            }
        }
        if(pos!=pattern.length())
        {
            return false;
        }
        return true;
    }
};

49.同字符词语分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]

输出:[

["ate","eat","tea"],

["nat","tan"],

["bat"]

]

来源：力扣（LeetCode）

链接：力扣

思考：anagram分组，若某两个字符型，出现的各个字符串数相同，则他们应该为同一分组。

哈希表以内部进行排序的各个单词为key，以字符串向量（vetor<string>）为value，存储各个字符数量相同的字符串（anagram）

算法思路：

设置字符串到字符串向量的哈希表anagram，遍历字符串向量strs中的单词strs[i];

(1)设置临时遍历str = strs[i],对str进行排序；

（2）若str未出现在anagram中，设置str到一个空字符串向量的映射。

（3）将strs[i]添加至字符串向量anagram[str]中。

遍历哈希表anagram，将全部key对应的value push至最终结果中。


class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::map<std::string,std::vector<std::string>> anagram;
        std::vector<std::vector<std::string>> result;
        for(int i = 0; i<strs.size();i++)
        {
            std::string str = strs[i];
            std::sort(str.begin(),str.end());
            if(anagram.find(str) == anagram.end())
            {
                std::vector<std::string> item;
                anagram[str] = item;
            }
            anagram[str].push_back(strs[i]);    
 
        }
        std::map<std::string,std::vector<std::string>> ::iterator it;
        for(it = anagram.begin();it != anagram.end(); it++)
        {
            result.push_back((*it).second);
        }
        return result;
    }
};

方法二：

哈希表以26个字母的字符数量（一个长度为26的vector，统计单词中的各个字符的数量）为key，以字符串向量（vector<string>）为value，存储各个字符数量相同的字符串（anagram）

设置vector到字符串向量的哈希表anagram，遍历字符串向量strs中的单词strs[i]:

（1）统计strs[i]中的各个字符数量，存储至vec。

（2）若vec未出现在anagram中，设置vec到一个空字符串向量的映射。

（3）将str[i]添加至字符串向量anagram[vec]中。

遍历哈希表anagranm,将全部key对应的value,push至最终结果中。


void change_to_vector(std::string &str,std::vector<int> &vec)
{
    for(int i = 0;i<26;i++)
    {
        vec.push_back(0);
    }
    for(int i = 0; i<str.length();i++)
    {
        vec[str[i]-'a']++;
    }
}
 
 
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        std::map<std::vector<int>,std::vector<std::string>> anagram;
        std::vector<std::vector<std::string>> results;
        for(int i = 0; i<strs.size(); i++)
        {
            std::vector<int> vec;
            change_to_vector(strs[i],vec);
            if(anagram.find(vec) == anagram.end())
            {
                std::vector<std::string> item;
                anagram[vec] = item;
            }
            anagram[vec].push_back(strs[i]);
        }
        std::map<std::vector<int>,std::vector<std::string> > ::iterator it;
        for(it = anagram.begin();it!=anagram.end();it++)
        {
            results.push_back((*it).second);
        }
        return results;        
    }
};

3.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

来源：力扣（LeetCode）

链接：力扣

双指针扫描字符串方法：

1.设置一个记录字符数量的字符哈希，char_map;

2.设置一个记录当前满足条件的最长子串变量word；

3.设置两个指针（记作指针i与指针begin）指向字符串第一个字符；

4.设置最长满足条件的子串的长度result；

5.i指针向后逐个扫描字符串中的字符，在这个过程中，使用char_map记录字符数量

如果word中没有出现过该字符：对word尾部添加字符并检查result是否需要更新；

否则：begin指针向前移动，更新char_map中的字符数量，直到字符s[i]的数量为i；更新word，将word赋值为begin与i之间的子串。

在整个过程中使用begin与i维护一个窗口，该窗口中的子串满足题目条件（无重复的字符），窗口线性向前滑动，整体时间复杂度为Q(n)。


class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int begin = 0;
        int result = 0;
        std::string word = "";
        int char_map[128] = {0};
        for(int i = 0;i<s.length();i++)
        {
            char_map[s[i]]++;
            if(char_map[s[i]] == 1)
            {
                word+=s[i];
                if(result < word.length())
                {
                    result = word.length();
                }
            }
            else
            {
                while(begin <i && char_map[s[i]]>1)
                {
                    char_map[s[begin]]--;
                    begin++;
                }
                word = "";
                for(int j = begin; j<=i; j++)
                {
                    word +=s[j];
                }
            }
        }
        return result;
    }
};

187,重复的DNA序列

所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。

示例：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"

输出：["AAAAACCCCC", "CCCCCAAAAA"]

来源：力扣（LeetCode）

链接：力扣

算法思路：

枚举法
枚举DNA字符串的所有长度为10的子串，将其插入到哈希Map中，并记录子串数量；遍历哈希map，将所有出现超过1次的子串存储到结果中，算法复杂度O（n）。


class Solution {
public:
    vector<string> findRepeatedDnaSequences(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); 获得字符串s中从第i位开始的长度为10的字符串
            if(word_map.find(word)!=word_map.end())
            {
                word_map[word]+=1;
            }
            else
            {
                word_map[word] =1;
            }
        }
        std::map<std::string,int>::iterator it;
        for(it = word_map.begin();it!=word_map.end();it++)
        {
            if(it->second>1){
                result.push_back(it->first);
            } 
        }
        return result;
    }
};

方法二：将长度为10的DNA序列进行整数编码；

['A','C','G','T']4个字符串分别用[0,1,2,3]（二进制形式00,01,10,11）所表示，故长度为10的DNA序列可以用20个比特位的整数所表示

1.设置全局整数哈希int g_hash_map[1048576];(2^20=1048576),表示所有的长度为10的DNA序列。

2,将DNA字符串的前10个字符使用左移位运算转换为整数key，g_hash_map[key]++。

3.从DNA的第11个字符开始，按顺序遍历各个字符，遇到1个字符即将key右移2位（去掉最低位），并且将新的DNA字符s[i]转换为整数后，或到最高位（第19,20位），g_hash_map[key]++。

4.遍历哈希表g_hash_map,若g_hash_map[i]>1,将i从低位到高位转换为10个字符的DNA序列，push至结果数组

76.最小窗口子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"

输出: "BANC"

说明：

如果 S 中不存这样的子串，则返回空字符串 ""。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）

链接：力扣

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思考：枚举法：枚举S的所有子字符串，检查字符串中是否包含字符串T=“ABC”

预备知识：


#include<stdio.h>
#include<vector>
#include<string>
bool is_window_ok(int map_s[],int map_t[],std::vector<int> &vec_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;
}
int main()
{
    std::string s="ADOBECODEBANC";
    std::string t = "ABCDAB";
    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<s.length();i++)
    {
        map_s[s[i]]++;
    }
    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);
        }
    }
}

1.设置两个字符哈希数组，map_s与map_t,map_s代表当前处理窗口区间中的字符数量，map_t代表子串T的字符数量

2.设置两个指针（记作指针i与指针begin）指向字符串第一个字符；

3.i指针向后逐个扫描字符串中的字符，在这个过程中，循环检查begin指针是否可以向前移动：

如果当前begin指向的字符T中没出现，直接前移begin；

如果begin指向的字符T中出现了，但是当前区间窗口中的该字符数量足够，向前移动begin，并更新map_s;

否则不能移动begin，跳出检查。

4.指针i每向前扫描一个字符，即检查一下是否可以更新最终结果（找到最小的包含T中各个字符的窗口）。

在整个过程中使用begin与i维护一个窗口，该窗口中的子串满足题目条件，窗口线性向前滑动，整体时间复杂度为O（n）


class Solution {
private:
    bool is_window_ok(int map_s[],int map_t[],std::vector<int> &vec_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:
    string minWindow(string s, 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++)
        {
            map_s[s[i]]++;
            while(window_begin<i)
            {
                char begin_ch = s[window_begin];
                if(map_t[begin_ch]==0)
                {
                    window_begin++;
                }
                else if(map_s[begin_ch]>map_t[begin_ch])
                {
                    //更新map_s
                    map_s[begin_ch]--;
                    window_begin++;
                }
                else{
                    break;
                }
            }
            if(is_window_ok(map_s,map_t,vec_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;
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/227422