哈希表_数据结构

哈希表

1.定义：利用散列技术(建立一个对应关系)将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或者哈希表。

2.性质：

• 散列技术即是一种存储方法，也是一种查找方法。
• 数据元素之间没有逻辑关系，不能像其他数据结构利用连线图表示出来。
• 存储位置和关键字相关联。是一个面向查找的数据存储结构。
  

3.设计要求：

• 计算简单，就是建立对应关系的函数应该简洁，并能够防止地址冲突
• 散列表的地址分布均匀。
  

4.方法选取：

• 方法很多：直接定地址法，平方取中法，数字分析法，除留余数法
• 除留余数法：是最常用的构造散列函数的方法
  \[f(key)=key \ mod\ p (p\leq m),m=length(hash map)\]
  

5.解决散列冲突问题：

• 开放定址法：地址一旦冲突，就去寻找下一个空的散列地址。这种方法也叫线性探测法。
  \[f_{i}(key)=(f(key)+d_{i}) \ mod\ m\]
• 链地址法：一旦出现冲突，原地增加链表，增加结点。
• 公共溢出法：将所有的冲突值进行溢出，添加一个溢出表，所有冲突值按顺序全部存入溢出表
  
  

目录

• 347.TOP k frequent elements
• 349.两个数组的交集
• 187.DNA中的重复序列
• 205.相同结构的字符串
• 451.按照频率排序字符
• 500.键盘行元素
• 508.子树和的出现频率
• 389.字符串的不同
• 409.最长的回文字符串
• 438.找到所有回文字符串的位置

349. Intersection of Two Arrays

// unordered_set 哈希表的数据结构的使用
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> result;
        unordered_set<int> nums1_set (nums1.begin(),nums1.end());
        for(auto i:nums2){
            if(nums1_set.count(i)){
                result.push_back(i);
                nums1_set.erase(i);
            }
        }
        return result；    
    }
};

347.TOP k frequent elements

# 用了两种数据结构，一个字典，一个堆排序
from collections import Counter
import heapq
class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        nums_dict=Counter(nums)
        return heapq.nlargest(k,nums_dict,nums_dict.get)

# 自己写的，但是不对
from collections import Counter
class Solution:
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        
        nums_dict=Counter(nums)
        a=[]
        for i,v in nums_dict.items(): # 这里估计是缺少排序
            a.append(i)
        return a[0:k]

// c++ 是使用 map哈希和优先队列来实现
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 好好学习如何新建一个哈希map
        unordered_map<int,int> map;
        for(int num : nums){
            map[num]++;
        }
        
        vector<int> res;
        // pair<first, second>: first is frequency,  second is number
        priority_queue<pair<int,int>> pq; 
        for(auto it = map.begin(); it != map.end(); it++){
            // 实现对pair,关联容器还是要看看
            pq.push(make_pair(it->second, it->first));// 注意这个优先队列的特性，在
            // 插入元素的时候就根据 it->second 的大小值进行排序了。
            if(pq.size() > (int)map.size() - k){
                res.push_back(pq.top().second);
                pq.pop();
            }
        }
        return res;
    }
};

// 同样的方法
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> result;
        unordered_map<int,int>nums_map;
        for(int num:nums){
            nums_map[num]++;
        }
        priority_queue<pair<int,int>> pq;
        for(auto it=nums_map.begin(); it!=nums_map.end();it++){
            pq.push(make_pair(it->second,it->first));        
            }
            // 这样会更好的理解一点
        for(int j=0;j<k;j++){
            result.push_back(pq.top().second);
            pq.pop();
        }
        
        return result;
    }
};

187.Repeated DNA Sequences

// 自己思考的方法，就是最暴力的读取计数法
// 利用哈希map来存储个数
class Solution {
public:
    vector<string> findRepeatedDnaSequences(string s) {
        vector<string> result;
        if(s.size()<10)
            return result;
        map<string,int> string_count;
        for(int i=0;i<s.size()-10+1;i++){
            string sub_str=s.substr(i,10);
            string_count[sub_str]++;
        }
        for(const auto &w:string_count){
            if(w.second>1){
                result.push_back(w.first);
            }
        }
        return result;
    }
};

205.Isomorphic String

// 这个是没有ac的版本
// 主要问题是在建立映射的时候出现了一点问题
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char,char> str_map;
        if(s.size()!=t.size())
            return false;
        for(int i=0;i<s.size();i++){
            if(!str_map.count(t[i]))
                str_map[s[i]]=t[i];
            if(str_map[s[i]]!=t[i])
                return false;
        }
        return true;
    }
};
// 上面整体的解题思路不对
// 利用两个数组来实现 map映射的关系
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int num_ss[256]={0}, num_st[256]={0},n=s.size();
        for(int i=0;i<n;i++){
            if(num_ss[s[i]]!=num_st[t[i]])
                return false;
            num_ss[s[i]]=i+1;  //要改变一起改变，要不就不改变
            num_st[t[i]]=i+1;
        }
        return true;
    }
};

451. Sort Characters By Frequency

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> m;
        string result;
        map<int,vector<char>> m_freq;
        for(auto c:s){
            m[c]++;
        }
        for(auto x:m){
            m_freq[x.second].push_back(x.first);
        }
        for(auto it=m_freq.rbegin();it!=m_freq.rend();it++){ // rbegin() 进行逆序输出
            // map有的操作，但是unordered_map没有
            for(auto c:it->second)// 遍历vector中所有的字符串
                result.append(it->first,c);
        }
        return result;  
    }
};

// 这个解法 有点东西
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char,int> freq;
        vector<string> bucket(s.size()+1, "");
        string res;
        
        //count frequency of each character
        for(char c:s) freq[c]++;
        //put character into frequency bucket
        for(auto& it:freq) {
            int n = it.second;
            char c = it.first;
            bucket[n].append(n, c); // 这个语句没看懂
        }
        //form descending sorted string
        for(int i=s.size(); i>0; i--) {
            if(!bucket[i].empty())
                res.append(bucket[i]);
        }
        return res;
    }
};

500. Keyboard Row

// 键盘元素
class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        unordered_set<char> row1 {'q', 'w', 'e', 'r', 't', 'y','u', 'i', 'o', 'p'};
        unordered_set<char> row2 {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'}; 
        unordered_set<char> row3 { 'z', 'x', 'c', 'v', 'b' ,'n', 'm'};
        vector<unordered_set<char>> rows {row1, row2, row3};
        
        vector<string> result;
        for(int i=0;i<words.size();i++){
            int row=0;
            for(int k=0;k<3;k++){
                if(rows[k].count((char)tolower(words[i][0]))>0)
                    row=k;    
            }
            result.push_back(words[i]);
            for(int j=0;j<words[i].size();j++){
                if(rows[row].count((char)tolower(words[i][j]))==0){
                    result.pop_back();
                    break;
                }   
            }
        }
        return result;    
    }
};

508. Most Frequent Subtree Sum

// 自己想的思路完全正确
// 就是代码没能自己实现
//1.自下而上的计算所有结点的 node_subtree_sum1.自下而上的计算所有结点的 node_subtree_sum,并存储在一个vector中
//2.对vector中的和及其出现的次数建立一个map
//3.输出出现次数最多的 sum
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int>result;
        unordered_map<int,int> counts;
        int max_count=INT_MIN;
        subTreeSum(root,counts,max_count);
        for(auto &x:counts){
            if(x.second==max_count){
                result.push_back(x.first);
            }
        }
        return result;
        
    }
    // 自下而上而上的代码要多看看，学习
    int subTreeSum(TreeNode *root,unordered_map<int,int>&counts,int &max_count){
        if(!root)
            return 0;
        int sum=root->val;
        sum+=subTreeSum(root->left,counts,max_count);
        sum+=subTreeSum(root->right,counts,max_count);
        counts[sum]++;
        max_count=max(max_count,counts[sum]);
        return sum;
    }
};

389. Find the Difference

// 很简单的一道题
// 解题思路和205 一样
// 都是建立一个 数组的hash来实现计数功能
class Solution {
public:
    char findTheDifference(string s, string t) {  
        char temp;
        int cnt[128]={0};
        for(auto &c:s)
            cnt[c]++;
        for(auto &c:t){
            cnt[c]--;
            if(cnt[c]<0)
                return c;
        }
        return temp;     
    }
};

409. Longest Palindrome

// 自己写的版本
class Solution {
public:
    int longestPalindrome(string s) {
        int max_length=0;
        map<char,int> m;
        for(auto &c:s){
            m[c]++;
        }
        for(const auto w:m){
            if(w.second!=1)
                max_length+=w.second;
        }
        return max_length+1;
    }
};
//能用 vector就用 vector
// 一到字符串这块就歇逼，哎
class Solution {
public:
    int longestPalindrome(string s) {
        vector<int> m(256, 0);        
        for (auto& c : s) m[c-'\0']++;
        int result = 0;
        for (auto& i : m) result += i%2 ? (result%2 ? i-1 : i) : i;
        return result;
    }
};

438. Find All Anagrams in a String

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> pv(26,0), sv(26,0), res;
        if(s.size() < p.size())
           return res;
        // fill pv, vector of counters for pattern string and sv, vector of counters for the sliding window
        for(int i = 0; i < p.size(); ++i)
        {
            ++pv[p[i]-'a'];
            ++sv[s[i]-'a'];
        }
        if(pv == sv)
           res.push_back(0);

        //here window is moving from left to right across the string. 
        //window size is p.size(), so s.size()-p.size() moves are made 
        for(int i = p.size(); i < s.size(); ++i) 
        {
             // window extends one step to the right. counter for s[i] is incremented 
            ++sv[s[i]-'a'];
            
            // since we added one element to the right, 
            // one element to the left should be forgotten. 
            //counter for s[i-p.size()] is decremented
            --sv[s[i-p.size()]-'a']; 

            // if after move to the right the anagram can be composed, 
            // add new position of window's left point to the result 
            if(pv == sv)  
               res.push_back(i-p.size()+1);
        }
        return res;
    }
};