首页 > 编程语言 >代码随想录算法训练营第六天|Day6哈希表基础

代码随想录算法训练营第六天|Day6哈希表基础

时间：2024-09-30 17:54:04浏览次数：12  
标签：return 哈希 Day6 HashNode 随想录 int hashTable key

242.有效的字母异位词

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

思路

1.暴力的解法，两层为循环，很明显时间复杂度是 O（n^2）。

bool isAnagram(char *s, char *t) {
    if (strlen(s) != strlen(t)) {
        return false;
    }
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        char ch = s[i];
        bool found = false;
        for (int j = 0; j < len; j++) {
            if (ch == t[j]) {
                found = true; 
                t[j] = '\0'; 
                break; 
            }
        }
        if (!found) {
            return false;
        }
    }
    return true;
}

2.哈希表

数组其实就是一个简单哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。

定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - 'a' 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

bool isAnagram(char *s, char *t) {  
    if (strlen(s) != strlen(t)) {  
        return false;  
    }  
    int charCount[26] = {0};   
    for (int i = 0; i < strlen(s); i++) {  
        charCount[s[i] - 'a']++;  
    }   
    for (int i = 0; i < strlen(t); i++) {  
        charCount[t[i] - 'a']--;  
    }  
    for (int i = 0; i < 26; i++) {  
        if (charCount[i] != 0) {  
            return false;  
        }  
    }  
    return true;  
}

学习反思

今天第一次接触哈希表的知识，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O（n），但如果使用哈希表的话， 只需要O（1）就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了哈希函数，也就是哈希函数。

349. 两个数组的交集

题目链接/文章讲解/视频讲解： https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

思路

哈希数据结构：unordered_set

这道题用暴力的解法时间复杂度是O(n^2)，那来看看使用哈希法进一步优化。那么用数组来做哈希表也是不错的选择，但要使用数组来做哈希的题目，是因为题目都限制了数值的大小。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize){   
    bool hashTable[1001] = {false};   
    int* result = (int*)malloc(nums1Size * sizeof(int)); 
    int resultIndex = 0; 
    for (int i = 0; i < nums1Size; i++) {  
        hashTable[nums1[i]] = true;  
    }  
    for (int i = 0; i < nums2Size; i++) {  
        if (hashTable[nums2[i]]) {  
            bool alreadyInResult = false;  
            for (int j = 0; j < resultIndex; j++) {  
                if (result[j] == nums2[i]) {  
                    alreadyInResult = true;  
                    break;  
                }  
            }  
            if (!alreadyInResult) {  
                result[resultIndex++] = nums2[i];  
            }  
  
        }  
    }  
    int* finalResult = (int*)malloc(resultIndex * sizeof(int));  
    for (int i = 0; i < resultIndex; i++) {  
        finalResult[i] = result[i];  
    }  
    free(result); 
    *returnSize = resultIndex;  
    return finalResult;  
}

学习反思

对哈希表的认识得到了提升。

202. 快乐数

题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

思路

1.

这道题目看上去貌似一道数学问题，其实并不是！题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现，这对解题很重要！当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法了。所以这道题目使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false，否则一直找到sum为1为止。判断sum是否重复出现就可以使用unordered_set。

#define HASH_TABLE_SIZE 1000000  
typedef struct HashNode {  
    int key;  
    struct HashNode* next;  
} HashNode;  
 
HashNode** createHashTable(int size) {  
    HashNode** hashTable = (HashNode**)malloc(size * sizeof(HashNode*));  
    for (int i = 0; i < size; i++) {  
        hashTable[i] = NULL;  
    }  
    return hashTable;  
}  
 
int hashFunction(int key, int size) {  
    return abs(key) % size;  
}  

void insertHashTable(HashNode** hashTable, int key, int size) {  
    int hashIndex = hashFunction(key, size);  
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));  
    newNode->key = key;  
    newNode->next = hashTable[hashIndex];  
    hashTable[hashIndex] = newNode;  
}  

bool containsHashTable(HashNode** hashTable, int key, int size) {  
    int hashIndex = hashFunction(key, size);  
    HashNode* currentNode = hashTable[hashIndex];  
    while (currentNode != NULL) {  
        if (currentNode->key == key) {  
            return true;  
        }  
        currentNode = currentNode->next;  
    }  
    return false;  
}  
void freeHashTable(HashNode** hashTable, int size) {  
    for (int i = 0; i < size; i++) {  
        HashNode* currentNode = hashTable[i];  
        while (currentNode != NULL) {  
            HashNode* tempNode = currentNode;  
            currentNode = currentNode->next;  
            free(tempNode);  
        }  
    }  
    free(hashTable);  
}  
int getNext(int n) {  
    int sum = 0;  
    while (n > 0) {  
        int digit = n % 10;  
        sum += digit * digit;  
        n /= 10;  
    }  
    return sum;  
}  
bool isHappy(int n) {  
    HashNode** hashTable = createHashTable(HASH_TABLE_SIZE);  
      
    int current = n;  
    while (current != 1) {  
        if (containsHashTable(hashTable, current, HASH_TABLE_SIZE)) {  
            freeHashTable(hashTable, HASH_TABLE_SIZE);  
            return false;  
        }  
        insertHashTable(hashTable, current, HASH_TABLE_SIZE);  
        current = getNext(current);  
    }  
    freeHashTable(hashTable, HASH_TABLE_SIZE);  
    return true;  
}

2.双指针

#define SET_SIZE 1000000  
bool seen[SET_SIZE] = {false};  
int getNext(int n) {  
    int sum = 0;  
    while (n > 0) {  
        int digit = n % 10;  
        sum += digit * digit;  
        n /= 10;  
    }  
    return sum;  
}  
  
bool isHappy(int n) {  
    int slow = n, fast = getNext(n);  
    while (slow != 1 && fast != 1) {  
        if (seen[fast]) {  
            return false;  
        }  
        seen[fast] = true;  
        slow = getNext(slow);  
        fast = getNext(getNext(fast));  
    }  
    return slow == 1 || fast == 1;  
}

学习反思

看了给的示例有一些反思

  1. 数学观察：
    • 快乐数问题涉及将一个数的每一位数字平方后求和，然后重复此过程，直到结果为1（表示是快乐数）或进入循环（表示不是快乐数）。
    • 通过观察，发现经过几次迭代后，得到的和的范围会变得相当有限。这意味着我们不需要一个非常大的数组来存储已经出现过的和。
  2. 编程技巧：
    • 使用了一个固定大小的数组visited来跟踪已经出现过的和。由于观察到的和的范围有限（在您的例子中，最大为162，但为了安全起见，您选择了163作为数组大小），因此这种方法非常有效。
    • 还通过预计算（int sum = get_sum(get_sum(n));）来减少循环中的迭代次数。虽然这可能会增加一些初始计算量，但它有助于更快地进入可能的循环，从而减少了总计算时间。
  3. 代码简洁性：
    • 示例代码非常简洁且易于理解。它使用了基本的循环和条件语句，以及一个固定大小的数组来解决问题。
    • 函数get_sum和isHappy都相对较短，这使得代码更易于调试和维护。
  4. 效率：
    • 尽管这种方法在理论上可能不是最优的（例如，它使用了额外的空间来存储已经出现过的和，并且预计算可能不是必需的），但在实践中，它对于解决快乐数问题是非常有效的。
    • 由于快乐数问题的特性（即和的增长和可能的循环），这种方法通常能够在合理的时间内给出结果。
  5. 易于实现：
    • 这种方法不需要复杂的数据结构或算法。它仅使用了基本的数组和循环结构，这使得它非常适合我这种初学者或那些希望快速实现解决方案的人。

1. 两数之和

题目链接/文章讲解/视频讲解： https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

 思路

本题，我就需要一个集合来存放我们遍历过的元素，然后在遍历数组的时候去询问这个集合，某元素是否遍历过，也就是 是否出现在这个集合。那么我们就应该想到使用哈希法了。因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

 typedef struct {
     int key;
     int value;
     UT_hash_handle hh; 
 } map;
map* hashMap = NULL;
 void hashMapAdd(int key, int value){
     map* s;
     // key already in the hash?
     HASH_FIND_INT(hashMap, &key, s);
     if(s == NULL){
         s = (map*)malloc(sizeof(map));
         s -> key = key;
         HASH_ADD_INT(hashMap, key, s);
     }
     s -> value = value;
 }
map* hashMapFind(int key){
     map* s;
     // *s: output pointer
     HASH_FIND_INT(hashMap, &key, s);   
     return s;
 }
 void hashMapCleanup(){
     map* cur, *tmp;
     HASH_ITER(hh, hashMap, cur, tmp){
         HASH_DEL(hashMap, cur);
         free(cur);
     }
 }
 void hashPrint(){
     map* s;
     for(s = hashMap; s != NULL; s=(map*)(s -> hh.next)){
         printf("key %d, value %d\n", s -> key, s -> value);
     }
 } 
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i, *ans;
    // hash find result
    map* hashMapRes; 
    hashMap = NULL;
    ans = malloc(sizeof(int) * 2);
    for(i = 0; i < numsSize; i++){
        hashMapAdd(nums[i], i);
    }
    hashPrint();
    for(i = 0; i < numsSize; i++){
        hashMapRes = hashMapFind(target - nums[i]);
        if(hashMapRes && hashMapRes -> value != i){
            ans[0] = i;
            ans[1] = hashMapRes -> value ;
            *returnSize = 2;
            return ans;
        }
    }    
    hashMapCleanup();
    return NULL;
}

学习反思

感觉c语言还是很麻烦什么都要手搓，感觉最好不要用c语言学算法。

总结

今天初步认识到了哈希表，感觉运用不是很熟练，加油！！！

标签：return,哈希,Day6,HashNode,随想录,int,hashTable,key
From： https://blog.csdn.net/a6666999d/article/details/142660443

相关文章

  • 代码随想录算法训练营第六天|理解hash表
    WhatisHashTable?引用自文章链接：https://programmercarl.com/哈希表理论基础.html#哈希表哈希表是根据关键码的值而直接进行访问的数据结构。直白来讲其实数组就是一张哈希表，哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素。哈希函数通过hashCode把......
  • Java-数据结构-Map和Set-(二)-哈希表 |ू･ω･` )
    文本目录：❄️一、哈希表：  ☑1、概念：    ☑2、冲突-概念：    ☑3、冲突-避免：     ☞1）、避免冲突-哈希函数的设计：     ☞2）、避免冲突-负载因子调节(重点)：    ☑4、冲突-解决：      ➷1）、解决冲突-闭散列： ......
  • Java哈希表
    哈希主要用于快速查找、存储和比较数据。哈希的核心在于哈希函数（HashFunction），它将输入（通常称为键，key）映射到一个固定范围的输出值，这个输出值称为哈希值（HashValue)或哈希码。HashMapHashMap<Integer,String>hashmap=newHashMap<Integer,String>();增：hashmap.put(1,"......
  • 代码随想录一刷day2
    T27移除元素   注意复习思路快慢指针：快指针：指向遍历的元素慢指针：指向需要替换的元素实现：slowIndex=0；通过遍历fastIndex，当target！=nums【fastIndex】，nums【slowIndex++】=nums【fastIndex】； T26理解快慢指针 nums[fast]!=nums[slow]时，交换两个的值且slow++；其他就f......
  • 洛谷每日一题（P2580 于是他错误的点名开始了）字典树/哈希表
    原题目链接：P2580于是他错误的点名开始了-洛谷|计算机科学教育新生态(luogu.com.cn)原题目截图：思路分析：解法一：哈希表法显而易见的一种思路，我们不妨模拟一下：当教练每次点名，我作为特派员，便查看一下有没有这个学生，是不是点过了这个学生。我们查看的过程，就依赖于一张表......
  • 代码随想录算法训练营第四天|24. 两两交换链表中的节点，19.删除链表的倒数第N个节点，面
    24.两两交换链表中的节点文章链接：https://programmercarl.com/0024.两两交换链表中的节点.html#思路视频讲解：https://www.bilibili.com/video/BV1YT411g7br代码链接：https://leetcode.cn/problems/swap-nodes-in-pairs/此题注意点：注意由于交换节点，head已经变换了位置，故最终......
  • 代码随想录算法训练营Day16 | 513.找树左下角的值、112.路径总和、113.路径总和Ⅱ、10
    目录513.找树左下角的值112.路径总和113.路径总和Ⅱ106.从中序与后序遍历序列构造二叉树105.从前序与中序遍历序列构造二叉树513.找树左下角的值题目513.找树左下角的值-力扣（LeetCode）给定一个二叉树的根节点root，请找出该二叉树的最底层最左边节点的值。假......
  • 代码随想录算法训练营Day03-链表 | LC203移除链表元素、LC707设计链表、LC206反转链表
    目录前言LeetCode203.移除链表元素思路完整代码LeetCode707.设计链表思路完整代码LeetCode206.反转链表思路完整代码今日总结前言拖延症犯了，哈哈，拖了一天LeetCode203.移除链表元素给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val......
  • 代码随想录算法训练营第三天|203.移除链表元素,707.设计链表,206.反转链表
    203.移除链表元素文章链接：https://programmercarl.com/0203.移除链表元素.html#算法公开课视频讲解：https://www.bilibili.com/video/BV18B4y1s7R9题目出处：https://leetcode.cn/problems/remove-linked-list-elements/卡哥在这里讲解了为什么要使用虚拟头节点，以及使用和不使......
  • CF2014H Robin Hood Archery(异或哈希)
    题目链接题意Alice和Bob将进行一场射击比赛题解点击查看代码#include<bits/stdc++.h>usingi64=longlong;i64seed=std::chrono::high_resolution_clock::now().time_since_epoch().count();std::mt19937_64rng(seed^std::random_device{}());constexp......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99