精华内容
下载资源
问答
  • 一.哈希表的介绍 散列表(Hash table,也叫哈希表),是根据关键码值(Key ...哈希表属于一种数据结构不是算法. 代码实现: package com.qiu.hashtable; import java.util.Scanner; public class HashTableDemo {

    一.哈希表的介绍
    散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    为什么要使用哈希表
    在这里插入图片描述
    哈希表的结构:

    在这里插入图片描述

    哈希表属于一种数据结构不是算法.

    看一个实际的需求在这里插入图片描述
    代码实现:

    package com.qiu.hashtable;
    
    
    import java.util.Scanner;
    
    public class HashTableDemo {
        public static void main(String[] args) {
            HashTable hashTable = new HashTable(7);
    
            //写一个简单的菜单
            String key = "";
            Scanner scanner = new Scanner(System.in);
            while(true){
                System.out.println("add: 添加雇员");
                System.out.println("list: 显示雇员");
                System.out.println("find: 查找雇员");
                System.out.println("delete: 删除雇员");
                System.out.println("exit: 退出菜单");
    
                key = scanner.next();
                switch (key){
                    case "add":
                        System.out.println("请输入id");
                        int id = scanner.nextInt();
                        System.out.println("请输入名字");
                        String name = scanner.next();
                        //创建雇员
                        Emp emp = new Emp(id, name);
                        hashTable.add(emp);
                        break;
                    case "list":
                        hashTable.list();
                        break;
                    case "find":
                        System.out.println("请输入要查找的id");
                        id = scanner.nextInt();
                        hashTable.findEmpById(id);
                        break;
                    case "delete":
                        System.out.println("请输入要删除的雇员id");
                        id = scanner.nextInt();
                        hashTable.deleteEmpById(id);
                        break;
                    case "exit":
                        scanner.close();
                        System.exit(0);
                    default:
    
                }
            }
    
    
        }
    }
    //哈希表的创建HashTable
    class HashTable{
        private EmpLinkedList[] empLinkedListArray;
        private int size;
    
        //构造器
        public HashTable(int size){
            this.size = size;
            //初始化empLinkedListArray
            empLinkedListArray = new EmpLinkedList[size];
            //需要分别初始化这几个链表
            for (int i = 0; i < size; i++) {
                //数组里面的每一个元素都需要创建一把
                empLinkedListArray[i] = new EmpLinkedList();
            }
        }
    
        //添加雇员
        public void add(Emp emp){
            //根据员工的id得到该员工应当加入到哪条链表
            int empLinkedListNo = hashFun(emp.id);
            //将emp添加到对应的链表中
            empLinkedListArray[empLinkedListNo].add(emp);
        }
        //遍历所有的链表,遍历hash
        public void list(){
            for (int i = 0; i < size; i++) {
                empLinkedListArray[i].list(i);
            }
        }
        //根据输入的id查找雇员
        public void findEmpById(int id){
            //使用散列函数确定哪条列表
            int empLinkedListNo = hashFun(id);
            Emp emp = empLinkedListArray[empLinkedListNo].findEmpById(id);
            if (emp!=null){
                //找到了
                System.out.printf("在第%d条链表中找到雇员id = %d\n",(empLinkedListNo+1),id);
            }else {
                //没有找到
                System.out.println("在哈希表中没有找到该雇员");
            }
        }
        //根据id删除雇员
        public void deleteEmpById(int id){
            //使用散列函数确定哪条列表
            int empLinkedListNo = hashFun(id);
            empLinkedListArray[empLinkedListNo].delete(id);
    
    
        }
        //编写一个散列函数,使用一个简单的取模法
        public int hashFun(int id){
            return id % size;
        }
    
    }
    
    class Emp {
        public int id;
        public String name;
        public Emp next;
    
        public Emp(int id, String name) {
            this.id = id;
            this.name = name;
        }
    
    }
    //创建一个EmpLinkedList,表示链表
    class EmpLinkedList{
        //头指针,执行第一个Emp,因此我们这个链表的head,是直接指向第一个Emp
        //默认为空
        private Emp head;
        //添加雇员到链表
        //说明
        //1. 假定添加雇员时,id自增长的,即id的分配就是从小到大的
        //因此我们将该雇员直接加入都本链表的最后即可
        public void add(Emp emp){
            //如果是添加第一个雇员
            if (head == null){
                head = emp;
                return;
            }
            //如果不是第一个雇员,则使用一个辅助的指针帮助定位到最后
            Emp curEmp = head;
            while(true){
                if (curEmp.next == null){
                    //说明到了链表的最后
                    break;
                }
                //后移
                curEmp = curEmp.next;
            }
            //退出时直接将emp加入到链表
            curEmp.next = emp;
    
        }
        //遍历链表的雇员信息
        public void list(int no){
            if (head == null){
                System.out.println("第"+(no+1)+"链表为空");
                return;
            }
            System.out.print("第"+(no+1)+"个链表的信息为:");
            //辅助指针
            Emp curEmp = head;
            while (true){
                System.out.printf("=> id=%d name=%s\t",curEmp.id,curEmp.name);
                if (curEmp.next == null){
                    //说明curEmp已经到了最后
                    break;
                }
                curEmp = curEmp.next;
            }
            System.out.println();
        }
        //根据id查找雇员
        public Emp findEmpById(int id){
            //判断链表是否为空
            if (head == null){
                System.out.println("链表为空");
                return null;
            }
            //定义一个辅助指针
            Emp curEmp = head;
            while (true){
                if (curEmp.id == id){
                    //找到了
                    break;
                }
                curEmp = curEmp.next;
                if (curEmp.next == null){
                    //说明当前链表没有找到该雇员
                    curEmp = null;
                    break;
                }
    
            }
            return curEmp;
        }
        //根据id删除雇员
        public void delete(int id){
    
            Emp curEmp = head;
            boolean flag = false;
            if (head == null){
                System.out.println("链表为空,找不到需要删除的雇员");
                return;
            }
            while(true){
            if (head.id == id){
                head = head.next;
                return;
            }
            if (curEmp.next == null){
                break;
            }
            if (curEmp.next.id == id){
                //这个curEmp是待删除节点的前一个节点
                flag = true;
                curEmp.next = curEmp.next.next;
    
                return;
            }else {
                System.out.println("找不到该雇员");
            }
            curEmp = curEmp.next;
            }
        if (flag){
            System.out.println("删除成功");
        }
        }
    
    }
    
    
    展开全文
  • 哈希表的实现

    2015-12-10 02:27:46
    实现一个哈希表,首先我们要知道哈希表可以干什么,包含什么方法,实现哪些功能。 哈希表又叫散列表,是根据关键码值(Key, value)而直接进行访问的数据结构。oracle文档里面提到,用哈希表进行检索和存储,key...
    实现一个哈希表,首先我们要知道哈希表可以干什么,包含什么方法,实现哪些功能。

    哈希表又叫散列表,是根据关键码值(Key, value)而直接进行访问的数据结构。oracle文档里面提到,用哈希表进行检索和存储,key首先要完成hashcode方法,以确定这个key属于哪个区间,也就是说具有相同hashcode的被放在同一块区间里,hashcode往往是取模得出的结果。

    确定了位置,我们还要解决冲突问题,如果表中已经存在当前要存的key,我们应该先删除以前的那个key,先后把新的key加入到表中,这里我们要做两步,判断是否存在相同的key,如果存在就删除以前的key,注意的是这里说的key实际上是<key, value>对。

    实现代码如下

    import java.util.LinkedList;

    public class HashDemo<K, V> {
    private final int MAX_SIZE = 50;
    LinkedList<Element<K,V>>[] items;

    public HashDemo() {
    items = new LinkedList[MAX_SIZE];
    }

    /* 官方实现hashcode代码
    public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
    char val[] = value;

    for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
    }
    hash = h;
    }
    return h;
    }
    */
    public int hashCodeOfKey(K Key) {
    return Key.toString().length() % items.length;
    }

    public void put(K key, V value) {
    int h = hashCodeOfKey(key);
    if(items[h] == null)
    items[h] = new LinkedList<Element<K,V>>();
    //检查当前的key是否已经存在
    LinkedList<Element<K, V>> coll = items[h];
    for(Element<K,V> e : coll) {
    //如果存在就删除以前的元素
    if(e.equivalent(key)) {
    coll.remove(e);
    break;
    }
    }
    //把新的元素加到表中
    Element<K, V> element = new Element<K, V>(key, value);
    coll.add(element);
    }

    public V get(K key) {
    int h = hashCodeOfKey(key);
    if(items[h] == null) {
    return null;
    }
    LinkedList<Element<K, V>> coll = items[h];
    for(Element<K,V> e : coll) {
    if(e.equivalent(key))
    return e.getValue();

    }
    return null;
    }
    }

    //Element类帮助我们处理表中的元素
    class Element<K, V> {
    private K key;
    private V value;
    public Element( K key, V value) {
    this.key = key;
    this.value = value;
    }

    public boolean equivalent(K k) {
    return key.equals(k);
    }

    public K getKey() {
    return key;
    }
    public V getValue() {
    return value;
    }
    }



    [i]参考资料:Cracking the Coding Interview,Gayle Laakmann McDowell[/i]
    展开全文
  • 哈希表(散列表),是根据关键字值key直接进行访问的数据结构,它通过把关键字值映射到表中一个位置(数组下标)来直接访问,以加快查找关键字值的速度。这个映射函数叫做哈希(散列)函数,存放记录的数组叫做哈希...

    1.哈希表

    1.1基本概念

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

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

    例1:给一个字符串,求每个字符出现多少次?

    易忘点:ASC2码0-127,数字0的ASC2码值是48,A的ASC2码值是65,a的ASC2码值是97.

    int main() {
    	int char_map[128] = { 0 };
    	std::string str = "asdasdasfafasd";
    	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]:%d\n", i, i, char_map[i]);
    		}
    	}
    }

    例2:给一个数组,里面存的是随机的正整数。使用哈希表进行排序。

    哈希表的长度需要大于超过最大待排序数字。时间复杂度是O(表长+元素个数)

    void hash_sort() {
    	int random[10] = { 999,1,4,78,2,6,90,23,1,25 };
    	int hash_map[1000] = { 0 };
    	for (int i = 0; i < sizeof(random) / sizeof(random[0]); i++) {
    		hash_map[random[i]]++;
    	}
    	//从小到大排序
    	for (int i = 0; i < sizeof(hash_map) / sizeof(hash_map[0]); i++) {
    		for (int j = 0; j < hash_map[i];j++) {
    			printf("%d ",i);
    		}
    	}
    }

    1.2任意元素的映射

    首先思考下面几个问题:

    1)当遇到负数或非常大的整数时,改如何进行哈希映射呢?

    2)当遇到字符串时,如何进行哈希映射呢?

    3)当遇到其他无法直接映射的数据类型(浮点数、数组、对象)如何进行哈希映射呢?

    解决办法就是利用哈希函数,将关键字值(大整数、字符串、浮点数等)转化为整数再对表长取余,从而关键字值被转换为哈希表的表长范围内的整数。

    例3:冲突问题

    首先我们写了一个整数取余哈希函数和字符串哈希函数展示,用于将大整数和字符串映射到哈希表中。

    //直接对整数取余表长再返回
    int int_func(int key, int table_len) {
    	return key % table_len;
    }
    //将字符串中的字符的ASC2码相加得到整数再取余表长
    int string_func(std::string key, int table_len) {
    	int sum = 0;
    	for (int i = 0; i < key.length(); i++) {
    		sum += key[i];
    	}
    }
    
    int main() {
    	const int TABLE_LEN = 10;
    	int hash_map[TABLE_LEN] = { 0 };
    	hash_map[int_func(999999995, TABLE_LEN)]++;
    	hash_map[int_func(5, TABLE_LEN)]++;
    	hash_map[string_func("abc", TABLE_LEN)]++;
    	hash_map[string_func("asdasd", TABLE_LEN)]++;
    	for (int i = 0; i < TABLE_LEN; i++) {
    		printf("hash_map[%d]=%d\n", i, hash_map[i]);
    	}
    	return 0;
    }

    但这时会发现,很可能会有多个结果映射到了同一个地方。而且不管我们如何设计哈希函数,都会出现这种发生冲突的情况,因为发生冲突的本质原因是哈希表的表长不够大。

    例4:使用拉链法解决冲突

    将所有哈希函数结果相同的结点连接在同一个单链表中。若选定的哈希表长度为m,则可将哈希表定义为一个长度为m的指针数组t[0..m-1],指针数组中的每个指针指向哈希函数结果相同的单链表。TABLE_LEN一般设定为质数,冲突会比其他数字少。

    #pragma region 拉链法解决冲突
    struct LisNode
    {
    	int val;
    	LisNode *next;
    	LisNode(int x) :val(x), next(NULL) {}
    };
    //整数哈希函数
    int hash_func(int key, int table_len) {
    	return key % table_len;
    }
    
    void insert(LisNode *hash_table[], LisNode * 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(LisNode *hash_table[], int value, int table_len) {
    	int hash_key = hash_func(value, table_len);
    	LisNode* head = hash_table[hash_key];
    	while (head!=NULL)
    	{
    		if (head->val == value) {
    			return true;
    		}
    		head = head->next;
    	}
    	return false;
    }
    #pragma endregion

    2.例题操练

    例5:最长回文串(LeetCode 409-简单

    题目:已知一个只包括大小写字符的字符串,求用该字符串中的字符可以生成的最长回文字符串长度。

    例子:S="abccccddaa",可生成的最长回文字符串长度为9,如dccaaaccd、adccbccda等,都是正确的。

    分析:

    除了中心字符外,其余只需要头部出现,尾部也出现。

    字符数量为偶数时,该怎么操作?字符数量为奇数时,该怎么操作?

    遇到偶数个的字符直接用,遇到奇数个的字符如果减1后是偶数就留下1个,其余全用;最后如果有剩1个的字符就随便选一个用。

    算法思路:

    • 利用字符哈希方法,统计字符串中所有的字符数量;
    • 设置最长回文串偶数字符长度为max_length=0;
    • 设置是否有中心点标记flag=0;
    • 遍历每一个字符,字符数为count,若count为偶数,max_length+=count;若count为奇数,max_length+=count-1,flag=1;
    • 最终最长回文子串长度:max_length+flag;

    代码展示:

    class Solution {
    public:
        int longestPalindrome(string s) {
            int max_length=0;
            int flag=0;
            //字符哈希
            int char_map[128]={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;
        }
    };

    例6:词语模式(LeetCode 290-简单

    题目:已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符串str中的单词与pattern中的字符一一对应。(其中pattern中只包含小写字符,str中的单词只包含小写字符,使用空格分隔。)

    例子:

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

    分析:

    • 单词的个数与pattern字符串中的字符数量相同
    • 当拆解出一个单词时,若该单词已出现,则当前单词对应的pattern字符必为该单词曾经对应的pattern字符
    • 当拆解出一个单词时,若该单词未曾出现,则当前单词对应的pattern字符也必须未曾出现

    算法思路:

    • 设置单词到pattern字符的映射;使用数组used[128]记录pattern字符是否使用。
    • 遍历str,按照空格拆分单词,同时对应的向前移动指向pattern字符的指针,每拆分出一个单词,判断:如果该单词从未出现在哈希表中:{如果当前的pattern字符已被使用,则返回fasle;将单词与当前指向的pattern字符做映射;标记当前指向的Pattern字符已使用}否则{如果当前单词在哈希表中的映射字符和当前指向的pattern字符不相同,则返回false}
    • 若单词个数与pattern字符个数不匹配,返回false.

    代码展示:

    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            //单词到pattern
            std::map<string,char> word_hash;
            //是否使用
            int used[128]={0};
            //单词
            std::string word;
            //在尾部添加空格,使得遇到空格拆分单词
            str.push_back(' ');
            //pattern数组的下标
            int j=0;
            for(int i=0;i<str.length();i++){
                //遇到空格则拆分单词并开始判断
                if(str[i]==' '){
                    //如果是新单词
                    if(word_hash.find(word)==word_hash.end()){
                        //对应的pattern用过则false
                        if(used[pattern[j]]==1){
                            return false;
                        }
                        //没用过则标记为用过并添加到哈希表中
                        used[pattern[j]]=1;
                        word_hash[word]=pattern[j];
                    }
                    else{
                        //不是新单词则判断对应关系是否一致
                        if(word_hash[word]!=pattern[j]){
                            return false;
                        }
                    }
                    word="";
                    j++;
                }
                else{
                    word.push_back(str[i]);
                }
            }
            if(j!=pattern.length() ){
                return false;
            }
            return true;
    
        }
    };

    例7:同字符词语分组(LeetCode 49-中等

    题目:已知一组字符串,将所有anagram(由点到字母顺序而构成的字)放到一起输出。

    例子:

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

    分析:如何设计哈希表的key和value,就可将各个字符数相同的字符串映射到一起

    算法思路1:

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

    • 设置临时变量str=strs[i],对str进行排序。
    • 若str未出现在anagram中,设置str到一个空字符串向量的映射。并添加到哈希表中。

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

    代码展示1:

    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            vector<vector<string>> result;
            //哈希表
            std::map<string,vector<string>> anagram_hash;
            for(int i=0;i<strs.size();i++){
                //先对str排序;
                string temp=strs[i];
                std::sort(temp.begin(),temp.end());
                //如果有同组元素则添加
                if(anagram_hash.find(temp)!=anagram_hash.end()){
                    anagram_hash[temp].push_back(strs[i]);
                }
                else{
                    //创建新的
                    vector<string> new_vecstr;
                    anagram_hash[temp]=new_vecstr;
                    anagram_hash[temp].push_back(strs[i]);
                }
            }
            std::map<string,vector<string>>::iterator iter;
            iter=anagram_hash.begin();
            while(iter!=anagram_hash.end()){
                result.push_back(iter->second);
                iter++;
            }
            return result;
        }
    };

    算法思路2:

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

    • 统计strs[i]中的各个字符数量,存储至vec
    • 若vec未出现在anagram中,设置vec到一个空字符串向量的映射。并添加

    遍历哈希表anagram至全部添加至最终结果

    代码展示2:逻辑基本一样,感兴趣的可以自己编写一下

     

    例8:无重复字符的最长子串(LeetCode 3-中等

    问题:已知一个字符串,求用该字符串的无重复字符的最长子串的长度。

    例子:

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

    分析:如果用枚举的方式来计算则复杂度是O(n^2),那么优化的目标就是降低时间复杂度,避免指针不必要的回调。

    算法思路1:

    • 设置一个记录字符数量的字符哈希,char_map
    • 设置一个记录当前满足条件的最长子串变量word;
    • 设置两个指针(i,begin)指向字符串第一个字符
    • 设置最长满足条件的子串的长度result
    • i指针向后逐个扫描字符串中的字符,在这个过程中,使用char_map记录字符数量,如果word中没出现过该字符{word后添加字符并比较result},否则

    代码展示1:

    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{//将重复的字符s[i]去掉
                 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;
        }
    };

    算法思路2:

    • 设置一个字符索引的哈希表char_hash;
    • 设置首尾指针head、tail
    • 遍历str中的字符,判断是否出现过,如果出现过{判断对应索引是否<head,小于head则忽略、大于等于head时则有重复出现,通过tail和haed计算长度;更新head值为重复位置的下一个,同时更新tail}否则添加新的哈希映射。

    代码展示2:

    class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            if(s.length()<2){
                return s.length();
            }
            int result=1;
            //int是字符在s中的index
            std::map<char,int> char_hash;
            int h=0;
            int t=0;
            for(;t<s.length();t++){
                //出现过,并且在目前串内
                if(char_hash.find(s[t])!=char_hash.end() && char_hash[s[t]]>=h){
                    //更新result
                    if(result<(t-h)){
                        result=(t-h);
                    }
                    //更新head
                    h=char_hash[s[t]]+1;
                }
                //最后一个要长度+1
                if(t==s.length()-1  && result<(t-h+1) ){
                        result=(t-h+1);
                }
                //添加新的,或更新旧的
                char_hash[s[t]]=t;
            }
            return result;
        }
    };

    例9:重复的DNA序列(LeetCode 187-中等

    题目:将DNA序列看作是只包括['A','C','G','T'] 4个字符的字符串,给一个DNA字符串,找到所有长度为10的且出现超过1次的子串。

    例子:

    输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
    输出:["AAAAACCCCC", "CCCCCAAAAA"]

    算法思路1:(简单方法)因为题目要求是长度为10,与n无关,所以可以使用枚举法;这种方法虽然可以通过,但完全没挖掘到问题真正的考点

    代码展示1:

    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            vector<string> result;
            map<string,int> hash_str;
            if(s.length()<10){
                return result;
            }
            int head=0;
            int tail=9;
            for(;tail<s.length();head++,tail++){
                string temp=s.substr(head,10);
                //判断是否出现过
                if(hash_str.find(temp)!=hash_str.end()){
                    hash_str[temp]++;
                }
                else{
                    hash_str[temp]=1;
                }
            }
            map<string,int>::iterator iter;
            iter=hash_str.begin();
            while(iter!=hash_str.end()){
                if(iter->second>1){
                    result.push_back(iter->first);
                }
                iter++;
            }
            return result;
        }
    };

    算法思路2:

    将A、C、G、T 4个字符分别用00,01,10,11 表示。故长度为10的DNA序列可以用20个比特位的整数所表示。

    • 设置全局整数哈希,注意长度的设置!(2^20)
    • 将DNA字符串的前10个字符利用移位运算转换为整数key;
    • 从第11个开始,按顺序遍历各个字符,遇到一个字符即将key右移2位(去掉最低位),将新字符添加到最高位
    • 遍历哈希表,输出最后结果

    代码展示2:

    //哈希表很大时需要全局数组,可能会栈溢出,内存爆掉
    int hash_map[1048576] ={0};
    
    string change_int2DNA(int DNA){
        static const char DNA_CHAR[]={'A','C','G','T'};
        string str;
        for(int i=0;i<10;i++){
            //把每2字节对应的字符提取出来
            str+=DNA_CHAR[DNA&3];
            DNA=DNA>>2;
        }
        return str;
    }
    
    class Solution {
    public:
        vector<string> findRepeatedDnaSequences(string s) {
            vector<string> result;
            if(s.length()<10){
                return result;
            }
            //由于是全局数组,每次调用时都需要更新
            for(int i=0;i<1048576;i++){
                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;
            //把前10个字符转成整数
            for(int i=9;i>=0;i--){
                //每存进去一个数后向左移两位
                key=(key<<2)+char_map[s[i]];
            }
            hash_map[key]=1;
            for(int i=10;i<s.length();i++){
                key=key>>2;
                key=key|(char_map[s[i]]<<18);
                hash_map[key]++;
            }
            //遍历将结果输出
            for(int i=0;i<1048576;i++){
                if(hash_map[i]>1){
                    result.push_back(change_int2DNA(i));
                }
            }
            return result;
        }
    };

    例10:最小窗口子串(LeetCode 76-困难

    题目:已知字符串S与字符串T,求在S中的最小窗口(区间),使得这个区间中包含了字符串T中所有的字符。

    例子:

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

    分析:这种枚举能直接解决的问题,大概率trick是在优化时间复杂度上;想办法是否能有一种O(n)的方法解决;既然有窗口,那大概率可以从设计头尾两个指针角度触发,一边遍历一边修正,这样就可实现O(n)时间复杂度的解决办法。

    算法思路:

    • 设置两个字符哈希数组,map_s和map_t,map_s代表当前处理的窗口区间中的字符数量,map_t代表子串T的字符数量。
    • 设置两个指针head和tail,初始化指向字符串的第一个字符;
    • tail指针向后逐个扫描字符串中的字符,在这个过程中循环检查head指针是否可以向前移动。
    • ---如果head指向的字符在T中没出现,直接移动head
    • ---如果head指向的字符在T中出现了,但是当前区间窗口中的该字符数量足够,也移动head,并更新map_s;
    • 指针tail每向后扫描一个字符就检查是否可以更新最终的结果,也就是更新当前最小的窗口

    代码展示:

    class Solution {
    private:
        bool is_window_ok(int map_w[],int map_t[],vector<int>& vec_t){
            //判断当前窗口是否符合条件
            for(int i=0;i<vec_t.size();i++){
                if(map_w[vec_t[i]]<map_t[vec_t[i]]){
                    return false;
                }
            }
            return true;
        }
    public:
        string minWindow(string s, string t) {
            const int MAX_LENGTH=128;
            //记录t中各字符个数
            int map_t[MAX_LENGTH]={0};
            //记录当前窗口中个字符个数
            int map_w[MAX_LENGTH]={0};
            //记录t字符串中有哪些字符
            vector<int> vec_t;
            //记录t中字符个数
            for(int i=0;i<t.length();i++){
                map_t[t[i]]++;
            }
            //遍历,将字符串t中出现的字符存储到vec_t中
            for(int i=0;i<MAX_LENGTH;i++){
                if(map_t[i]>0){
                    vec_t.push_back(i);
                }
            }
            //窗口的头尾指针,以及最终结果
            int head=0;
            int tail=0;
            string result;
            for(;tail<s.length();tail++){
                //新字符添加到窗口
                map_w[s[tail]]++;
                //头指针不能超过尾指针
                while(head<tail){
                    char head_char=s[head];
                    //字符在t中但窗口储备足够就后移,并更新map_w
                    if(map_w[head_char]>map_t[head_char]){
                        head++;
                        map_w[head_char]--;
                    }//如果字符不在t直接后移
                    else if(map_t[head_char]==0){
                        head++;
                    }
                    else{//如果在窗口且不能删那就跳出循环
                        break;
                    }
                }
                //判断这个窗口是否可行
                if(is_window_ok(map_w,map_t,vec_t)){
                    //判断当前窗口是否比目前最优结果小
                    int new_len=(tail-head+1);
                    if(result=="" || new_len < result.length()){
                        result=s.substr(head,new_len);
                    }
                }
                
            }
            return result;
    
        }
    };

     

     

     

     

     

     

     

     

     

    展开全文
  • 数据结构(一)

    2019-11-03 09:26:00
    注:这是对个人所阅读的知识的整理,如果有瑕疵,请大家积极...最常见的数据结构,常用的数组,链表,栈,队列,哈希表属于线性结构。 b.树 如二叉树,二叉堆。 c.图 复杂的数据结构,多用于分类或者建立数据间关...

    注:这是对个人所阅读的知识的整理,如果有瑕疵,请大家积极指出。
    1.什么是数据结构
    简单地理解数据结构,是数据的一种存储方式,使用数据结构的目的是为了更高效地访问和修改计算机中的数据。从而提升效率和性能。
    2.数据结构的几种常见组成方式
    a.线性结构
    最常见的数据结构,常用的数组,链表,栈,队列,哈希表都属于线性结构。
    b.树
    如二叉树,二叉堆。
    c.图
    复杂的数据结构,多用于分类或者建立数据间关系。
    d. 其他
    其他的数据结构基本是由以上的数据结构演变而来。

    展开全文
  • 什么是Hash

    万次阅读 2018-03-21 22:52:03
    作者:知乎用户链接:...哈希表属于一种存储结构,最常用的存储结构是顺序存储结构和链式存储结构,这两种结构的共同特征就是元素与元素之间存在映射关系。而哈希表的元素之间相互独立。哈希...
  • 一 并查集结构用来解决: 元素是否在集合中, 集合合并问题 最好给出了边的关系,不然就得向上下...具体哈希表里面存储什么形式由具体情况决定,如果是int, int形式的话,用数组代替字典更好。 语法细节: STL11
  • 散列表也叫做哈希表(hash table),这种数据结构提供了键(key)和值(value)的映射关系。只要给出一个key,就可以高效查找它匹配的value,时间复杂度接近O(1); 哈希函数 哈希函数通过某种方式,把key和数组下标进行转换...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    17.以下属于逻辑结构的是(C )。【西安电子科技大学应用 2001一、1】 A.顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。( ) 【北京邮电大学 1998 一、1(2分)】【青岛大学 ...
  • Redis 属于键值(key-value)数据库,键值数据库会使用哈希表存储键值和数据,其中 key 作为唯一的标识,而且 key 和 value 可以是任何的内容,不论是简单的对象还是复杂的对象都可以存储。键值数据库的查询性能高,...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    内容及步骤: 1、 设计一个图的类,采用临接法进行存储,该图每个结点的数据类型类模板的模板参数进行定义(注:需先设计一个结点类Node); 2、 为该类分别设计一个实现深度优先搜索和广度优先搜索的成员...
  • 用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的...
  • 散列表是一种数据结构,它的英文名称叫 Hash Table, 也是我们平常称的’哈希表’,或者 ‘Hash表’。散列表是一种支持利用数组下标实现随机访问的数据结构,也可以理解成散列表是一种数组的扩展。 下面我举个例子...
  • 用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的工作...
  • 用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值, 且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的...
  • 用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的工作...
  • Java的 集合干货

    2018-09-11 10:59:19
    用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的工作...
  • teg电话一面6.3

    2016-06-06 09:51:00
    2、c++ map set为什么用红黑树,不用哈希表 3、消息队列,共享内存设计 4、mysql引擎有哪些,mysql优化,有没有跟DBA讨论过相关表结构的优化 5、https 加密算法分类,aes属于哪一类(这个我应该回答ssl,引到这个...
  • 数据结构系列的文章我们之前已经说过数组,链表,哈希表以及队列等等,上一篇也简单的介绍下了树的概念,从今天开始,我们就进入二叉树的学习,这可是面试官最喜欢的问题之一,务必掌握牢固哦!回顾树的那些事在介绍...
  • hashmap:cr:csdn

    2017-10-31 15:52:00
    用过,HashMap是基于哈希表的Map接口的非同步实现,它允许null键和null值,且HashMap依托于它的数据结构的设计,存储效率特别高,这是我用它的原因 2、你知道HashMap的工作原理吗?你知道HashMap的get()方法的工作...
  • 1.redis前言

    2020-10-24 23:45:24
    它支持字符串、哈希表、列表、集合、有序集合,位图,hyperloglogs等数据类型。内置复制、Lua脚本、LRU收回、事务以及不同级别磁盘持久化功能,同时通过Redis Sentinel提供高可用,通过Redis Cluster提供自动分区。 ...
  • 【笔试卷】QTZ

    2017-11-26 15:18:31
    简述哈希表的大致原理,冲突解决方案,以及试用环境 在容器的遍历循环内部,添加和删除该容器的元素要注意什么 冒泡排序,快速排序,插入排序,归并排序的时间复杂度分别是多少?哪些属于稳定排序? 不依赖库函数,...
  • 4、并发容器

    2020-10-10 17:06:11
    属于压缩映射,容易产生哈希冲突; 常见算法 直接取余, md4、md5、sha 哈希算法,摘要 冲突解决办法: 开放寻址 再散列 链地址法 HashMap线程为什么不安全 put操作会引起死循环,hashMap里的entry链表产生环形的...
  • 2020-08-28

    2020-08-28 09:47:48
    Redis 属于键值(key-value)数据库,键值数据库会使用哈希表存储键值和数据,其中 key 作为唯一的标识,而且 key 和 value 可以是任何的内容,不论是简单的对象还是复杂的对象都可以存储。键值数据库的查询性能高,...
  • 这道题是在LeetCode探索,队列&栈模块中刷到的,属于广度优先搜索的题目。之前没有接触过此类题目,因此用普通的广搜思想...数据结构:队列+哈希表 解题思路: ①把问题转化成图的最短路径问题,这里的最短路径...
  • 难以置信的是,这样一本C语言的入门书籍,从hello world开始讲起,却在短小的篇幅里,手把手教你写了stdio.h stdlib.h string.h当中大部分例程,实现了二分查找、快速排序、二叉树、哈希表这些重要的数据结构和算法...
  • go数据库mysql与redis

    2021-05-25 11:09:01
    MySQL 教程 MySQL 是流行的关系型数据库管理系统,在 WEB 应用... Redis 通常被称为数据结构服务器,因为值(value)可以是字符串(String)、哈希(Hash)、列表(list)、集合(sets)和有序集合(sorted sets)等类型。
  • 什么哈希函数,一个哈希函数必须具备哪些基本性质,它能应用在哪些场景 试简要说明 SHA-512 的执行过程 什么是消息验证码(MAC),对比它和哈希算法在安全性能上的不同 Feistel 模型是分组密码的经典模型;它的...
  • 想象一下自己到超市购物的情况,我们购买某些商品的次数肯定会超过总次数的1%,这些商品可能是牛奶、面包、可口可乐或百事可乐什么的。我们甚至相信,虽然我们不购买尿布,但是会有1%的顾客会购买尿布。然而,货架上...

空空如也

空空如也

1 2
收藏数 38
精华内容 15
关键字:

哈希表属于什么结构