leecode刷题算法总结----哈希表（C语言）

leecode刷题算法总结----哈希表（C语言）

附：C语言哈希表uthash的使用方法详解（附下载链接）

leecode刷题算法总结----哈希表 一、哈希表常用函数 结构构建

//哈希表结构体的构建
//1、key值为int型
struct HashEntry_int {
    int key;                    
    UT_hash_handle hh;         
};
//2、key值为字符串
struct HashEntry_str {
    char* key;                    
    UT_hash_handle hh;         
};

哈希表增加

//HASH_ADD_INT表示添加的键值为int类型
//HASH_ADD_STR表示添加的键值为字符串类型
//HASH_ADD_PTR表示添加的键值为指针类型
//HASH_ADD表示添加的键值可以是任意类型

//哈希表添加模板 int型
void HashAddItem_int(struct HashEntry_int **head, int key)
{
	struct HashEntry_int * temp;
    //申请节点空间
    temp = malloc(sizeof(struct HashEntry_int));
    //节点参数赋值
    temp->key = key;
    //添加到哈希表中
    HASH_ADD_INT(*head,key,temp);
}

//哈希表添加模板 字符串型
void HashAddItem_str(struct HashEntry_str **head, char *s)
{
    struct HashEntry_str * temp;
    //申请节点空间
    temp = malloc(sizeof(struct HashEntry_str));
    //节点参数赋值
    temp->key = malloc(sizeof(char)*(strlen(s)+1));
    strcpy(temp->key, s);
    //添加到哈希表中
    HASH_ADD_STR(*head, key, temp);
}

哈希表查找

// 哈希查找模板 int型
struct HashEntry_int* find_int(struct HashEntry_int **head, int key)
{
    struct HashEntry_int* temp = NULL;
    HASH_FIND_INT(*head, &key, temp);
    return temp;
}

struct HashEntry_str* find_str(struct HashEntry_str **head, char* s)
{
    struct HashEntry_str* temp = NULL;
    HASH_FIND_STR(*head, s, temp);
    return temp;
}

哈希表遍历

//哈希表遍历
// HASH_ITER(hh_name, head, item_ptr, tmp_item_ptr)
//两种通用
struct HashEntry *curr, *next;
HASH_ITER(hh, *obj, curr, next)
{
    //执行要做的 *** 作      
}

//举例
//如删除
void hashFreeAll(struct HashEntry_str **head)
{
	struct HashEntry_str *cur, *next;
	HASH_ITER(hh, *head, cur, next){
    	//执行要做的 *** 作 
        free(cur->key);
    	HASH_DEL(*head,cur);  
    	free(cur);
	}
}
void hashFreeAll(struct HashEntry_int **head)
{
	struct HashEntry_int *curr, *next;
	HASH_ITER(hh, *head, curr, next){
    	//执行要做的 *** 作 
    	HASH_DEL(*head,curr);  
    	free(curr);
	}
}

其他函数详情请见下面链接

C语言哈希表uthash的使用方法详解（附下载链接）

二、实战模板使用

ps：（说明，题目可能有更好的解法，但是为了展示哈希表的使用，就使用hash表解题）

字符串模板 884. 两句话中的不常见单词

解题思路：

两句话中只出现一次的单词算不常见单词

所以只需要将两句话的单词分别加入哈希表中，并且统计该单词的出现次数，将次数为1的单进行输出

第一步、确定哈希结构

struct HashEntry{
  char *key; //字符串键值
  int times; //出现次数
  UT_hash_handle hh;
};

第二步、将字符串1和字符串2加入哈希表中

// 需要使用 查找和添加函数

自定义插入函数写逻辑 逻辑如下

对于一个字符串，先在哈希表中查找，如果找到了数量+1，没找到就加入哈希表中

第三步、遍历哈希表，将次数为1的字符串进行输出

代码部分（直接套模板）：

#define MAX 200

struct HashEntry_str{
    char *key;
    int times;
    UT_hash_handle hh;
};

struct HashEntry_str* find_str(struct HashEntry_str **head, char* s)
{
    struct HashEntry_str* temp = NULL;
    HASH_FIND_STR(*head, s, temp);
    return temp;
}

//哈希表添加模板 字符串型
void HashAddItem_str(struct HashEntry_str **head, char *s)
{
    struct HashEntry_str * temp;
    //申请节点空间
    temp = malloc(sizeof(struct HashEntry_str));
    //节点参数赋值
    temp->times = 1;
    temp->key = malloc(sizeof(char)*(strlen(s)+1));
    strcpy(temp->key, s);
    //添加到哈希表中
    HASH_ADD_STR(*head, key, temp);
}

void insertHash(struct HashEntry_str **head, char *s)
{
    struct HashEntry_str * temp = NULL;
    temp = find_str(head,s);
    if(temp){
        temp->times++;
    }else{
        HashAddItem_str(head,s);
    }
}

void hashFreeAll(struct HashEntry_str **head)
{
	struct HashEntry_str *cur, *next;
	HASH_ITER(hh, *head, cur, next){
    	//执行要做的 *** 作 
        free(cur->key);
    	HASH_DEL(*head,cur);  
    	free(cur);
	}
}

char ** uncommonFromSentences(char * s1, char * s2, int* returnSize){
    char **ans = malloc(sizeof(char*)*MAX);
    *returnSize = 0;
    struct HashEntry_str *head = NULL;
    //添加字符串到哈希表中
    char *c = strtok(s1," ");
    while(c != NULL){
        insertHash(&head,c);
        c = strtok(NULL, " ");
    }
    c = strtok(s2," ");
    while(c != NULL){
        insertHash(&head,c);
        c = strtok(NULL, " ");
    }

    //遍历哈希表
    struct HashEntry_str *cur,*next;
    HASH_ITER(hh,head,cur,next){
        if(cur->times == 1){
            ans[(*returnSize)] = malloc(sizeof(char)*(strlen(cur->key)+1));
            strcpy(ans[(*returnSize)++],cur->key);
        }
    }

    hashFreeAll(&head);
    return ans;
}

int值模板 1. 两数之和

解题思路：

先把数组中的元素加入到哈希表中，然后遍历数组，查找对应和为target的值，如果找到了就返回两个数值对应的下标

第一步、确认哈希结构

struct HashEntry_int {
    int key;                    
    int pos;					
    UT_hash_handle hh;         
};

第二步、在哈希表中查找相加等于target的值

​ 如果有值返回该值下标和当前下标

​ 如果没有值 将当前值和下标加入哈希表中

代码部分

struct HashEntry_int {
    int key;                    
    int pos;					
    UT_hash_handle hh;         
};

// 哈希表添加模板 int型
// 对添加函数稍微做了一些调整，多了一个参数
void HashAddItem_int(struct HashEntry_int **head, int key, int pos)
{
	struct HashEntry_int * temp;
    //申请节点空间
    temp = malloc(sizeof(struct HashEntry_int));
    //节点参数赋值
    temp->key = key;
    temp->pos = pos;
    //添加到哈希表中
    HASH_ADD_INT(*head,key,temp);
}

// 哈希查找模板 int型
struct HashEntry_int* find_int(struct HashEntry_int **head, int key)
{
    struct HashEntry_int* temp = NULL;
    HASH_FIND_INT(*head, &key, temp);
    return temp;
}


int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ans = malloc(sizeof(int)*2);
    *returnSize = 0;
    struct HashEntry_int* head;
    struct HashEntry_int* temp = NULL;
    
    for(int i = 0; i < numsSize; i++){
        // 查找符合目标的值
        temp = find_int(&head,target-nums[i]);
        if(temp){
            // 找到了，赋值
            ans[0] = temp->pos;
            ans[1] = i;
            (*returnSize) = 2;
            break; 
        }else{
            // 没找到，把当前值加入哈希表中
            HashAddItem_int(&head,nums[i],i);
        }
    }
    return ans;
}

相关题目链接 1. 两数之和 884. 两句话中的不常见单词

-----后面做了其他题目会陆续增加相关内容