哈希表与字符串

字符哈希
哈希表排序整数
拉链法解决冲突,使用头插法

一,最长回文串

1.用数组实现哈希:即下标为key,对应的值为value
2.是否有中心点,及其计算,比较讨巧

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;
    }
};

作者:xia-mu-lao-zhang-ren
链接:https://leetcode-cn.com/problems/longest-palindrome/solution/zui-chang-hui-wen-zi-chuan-by-xia-mu-lao-vknq/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

二,词语模式

1.根据空格划分单词
2.建立字符串和字符的映射
3.建立映射与否,字符是否使用过,是否不够或多余
4.没有映射就添加一个,有就继续往后添加,通过if实现此功能

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        map<string,char>word_map;//单词-字符
        char used[128]={0};
        string word;//临时保存拆分的单词
        int pos=0;//当前指向pattern的字符
        s.push_back(' ');//s尾部追加一个空格,使得遇到空格拆分单词,无需特殊处理了
        for(int i=0;i<s.length();i++){
            if(s[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,指针迁移
                word="";
                pos++;

            }
            else{
                word+=s[i];//划分单词
            }
        }
        if(pos!=pattern.length()){
            return false;//有多余的pattern字符
        }
        return true;



    }
};

作者:xia-mu-lao-zhang-ren
链接:https://leetcode-cn.com/problems/word-pattern/solution/dan-ci-gui-lu-by-xia-mu-lao-zhang-ren-qt1f/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

三,同字符词语分组

方法一

class Solution {
public:
//一个字符,映射一个字符数组
    //各个字符数量相同的字符串
    //若str未未出出现现在anagram中,设置str到一个空字符串向量的映射。
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<string,vector<string> >anagram;
        vector<vector<string> >result;
        for(int i=0;i<strs.size();i++){//遍历各个单词
            string str=strs[i];//临时保存该单词
            sort(str.begin(),str.end());
            if(anagram.find(str)==anagram.end()){//若str未未出出现现在anagram中,设置str到一个空字符串向量的映射。
                vector<string> item;
                anagram[str]=item;
            }
            anagram[str].push_back(strs[i]); //在对应的字符串向量中push结果【 anagram[str]指的是vector<string>】         
        }
        map<string,vector<string> >::iterator it;
        for(it=anagram.begin();it!=anagram.end();it++){
            result.push_back((*it).second);
        }
        return result;
    }
};

作者:xia-mu-lao-zhang-ren
链接:https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-xia-mu-lao-zha-l1l5/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二

void change_to_vector(string &str,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']++;//将str中的字符串各个字符个数进行统计并存入vec中
    }
}
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        map<vector<int> ,vector<string> >anagram;
        vector<vector<string> >result;
        for(int i=0;i<strs.size();i++){
            vector<int>vec;
            change_to_vector(strs[i],vec);
            if(anagram.find(vec)==anagram.end()){
                vector<string>item;
                anagram[vec]=item;
            }
            anagram[vec].push_back(strs[i]);
        }
        map<vector<int>,vector<string> >::iterator it;
        for(it=anagram.begin();it!=anagram.end();it++){
            result.push_back((*it).second);
        }
        return result;
    }
};

四,无重复字符的最长子串

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int begin=0;//头指针
        int result=0;
        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){//调整begin的位置,清除char_map中重复的字符
                    char_map[s[begin]]--;
                    begin++;
                }
                word="";
                for(int j=begin;j<=i;j++){//从新的begin开始重新更新word,改变的不是begin,然后再进行i的for循环
                    word+=s[j];
                }
            }
        }
        return result;

    }
};

作者:xia-mu-lao-zhang-ren
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-33z96/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

五,重复的DNA序列

1.哈希map
2.哈希数组

class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        map<string,int>word_map;//<单词,单词数量>映射
        vector<string>result;
        for(int i=0;i<s.length();i++){
            string word=s.substr(i,10);
            if(word_map.find(word)!=word_map.end()){//若在哈希表中出现
                word_map[word]+=1;
            }
            else{
                word_map[word]=1;//没有出现就添加进去
            }
        }
        map<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;
    }
};

作者:xia-mu-lao-zhang-ren
链接:https://leetcode-cn.com/problems/repeated-dna-sequences/solution/zhong-fu-de-dnaxu-lie-by-xia-mu-lao-zhan-vu4v/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇:Leetcode.438 Find All Anagrams in a String(Java)


下一篇:php – 用于anagram解算器的Mysql多个查询