当前位置： 首页 > article >正文

哈希表算法题

article 2024/12/1 4:01:56

目录

题目一——1. 两数之和 - 力扣（LeetCode）

1.1.暴力解法1

1.2.暴力解法2 

1.2.哈希表解法 

题目二——面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode） 

2.1.哈希表解法

2.2.排序解法 

 题目三——217. 存在重复元素 - 力扣（LeetCode）

3.1.哈希表解法

3.2.排序解法 

题目四——219. 存在重复元素 II - 力扣（LeetCode） 

题目五—— 49. 字母异位词分组 - 力扣（LeetCode）

我们这里不讲哈希表的原理那些，如果想要学习其他更多的，去其他地方，这里只讲实用的东西

  • 哈希表是什么？

就是一个存储数据的容器。

  • 哈希表有什么用？

可以快速查询某个元素，时间复杂度是O(1).

  • 什么时候使用哈希表？

我们需要频繁的查询一个数据的时候，我们就得想到使用哈希表。

判断某个元素只出现一次的时候，我们就得想到使用哈希表。

虽然二分查找也很快，但是它的使用条件太苛刻了。

  • 怎么使用哈希表？
  1. 任何高级语言都有哈希表的容器，像我们的C++的unorder_map
  2. 其次我们可以使用数组模拟哈希表（比如大小为26的数组，每个元素都可以代表哈希表的值，其次只要元素是比较小的整数的情况，我们也可以使用数组模拟哈希表）

其实我们在滑动窗口算法-CSDN博客就已经使用过哈希表了！感兴趣的可以去看一下

  • unordered_map的常用成员函数——count成员函数

在C++的std::unordered_map中，count成员函数用于查找特定键（key）在哈希表中的出现次数。然而，对于std::unordered_map来说，一个键最多只能出现一次（即映射到一个值），因此count函数实际上只会返回0或1。

  • 如果键存在于哈希表中，count返回1。
  • 如果键不存在于哈希表中，count返回0。

题目一——1. 两数之和 - 力扣（LeetCode）

 

1.1.暴力解法1

这个直接两个for循环零帧起手。不必多讲。

  1. 固定一个数
  2. 往右边遍历查询
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建一个空的整数数组result，用于存储找到的索引
        vector<int> result;
        
        // 使用两层循环遍历数组nums，外层循环变量i从0开始，内层循环变量w从i+1开始
        for(int i=0; i<nums.size(); i++) { // 外层循环，遍历数组中的每一个元素
            for(int w=i+1; w<nums.size(); w++) { // 内层循环，从i的下一个元素开始遍历，避免重复计算i和i的组合
                // 如果当前两个元素的和等于目标值target
                if(nums[i] + nums[w] == target) {
                    // 将外层循环的索引i添加到结果数组result中
                    result.push_back(i);
                    // 将内层循环的索引w添加到结果数组result中
                    result.push_back(w);    
                }
            }
        }
        
        // 返回找到的结果数组
        return result; 
    }
};

 

1.2.暴力解法2 

我们依然是先固定一个数，但是我们不再是往后面遍历寻找另外一个数了，我们这次是往前遍历

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        
        for(int i=1; i<nums.size(); i++) { 
            for(int w=i-1;w>=0; w--) {              
                if(nums[i] + nums[w] == target) {
                    result.push_back(i);    
                    result.push_back(w);    
                }
            }
        }
        // 返回找到的结果数组
        return result; 
    }
};

1.2.哈希表解法 

暴力枚举为什么慢？因为每个数都被遍历了好多遍。如果说我们能保证每个元素都能被遍历一次，甚至不用所有数，那是不是快很多了？？

哈希表就能做到

  1. 哈希表的键存该数组元素的值，哈希表的值存该数组元素的下标
  2. 从左边往右边遍历的过程中
  3. 我们要在哈希表里面找的有没有元素的值是target-nums[i]的
  4. 这个时候再将对应数组元素nums[i]丢入哈希表
class Solution 
{
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) 
    {
        // 创建一个哈希表，用于存储数组元素的值和对应的索引
        // 键是数组元素的值，值是该元素在数组中的索引
        std::unordered_map<int, int> hash;
        
        // 遍历数组nums
        for(int i = 0; i < nums.size(); i++)
        {
            // 计算当前元素需要的配对值，即target减去当前元素的值
            int x = target - nums[i];
            
            // 检查哈希表中是否已经存在需要的配对值
            // 如果存在，说明找到了两个数的和等于target
            // 此时，hash[x]是配对值的索引，i是当前元素的索引
            if(hash.count(x)) 
            {
                // 返回一个包含两个索引的数组
                return {hash[x], i};
            }
            
            // 将当前元素的值和索引存入哈希表
            // 这样，在后续的遍历中就可以通过查找哈希表来快速判断是否存在需要的配对值
            hash[nums[i]] = i;
        }
        
         return {-1, -1}; //这个只是为了照顾编译器
    }
};

题目二——面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode） 

2.1.哈希表解法

 这题不就是判断两个字符串里面的字符种类，个数是不是一样吗？

我们用哈希表来记录每种字符的个数，如果两个字符串的哈希表不一样，则说明不是字符重排。

但是，哈希表的实现方式有两种

  1. unordered_map
  2. 数组

我将会提供两种实现方式

unordered_map版本

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        // 如果两个字符串的长度不相等，它们不能是彼此的排列，直接返回false
        if(s1.length()!=s2.length()) {
            return false;
        }
        
        bool res=true;  // 初始化结果变量为true，假设它们是彼此的排列
        
        // 使用两个unordered_map来存储每个字符串中字符的出现次数
        unordered_map<char,int> hash1;
        unordered_map<char,int> hash2;
 
        // 遍历s1，统计每个字符的出现次数
        for(char x:s1) {
            hash1[x]++;
        }
        // 遍历s2，统计每个字符的出现次数
        for(char x:s2) {
            hash2[x]++;
        }
 
        // 遍历s1中的每个字符（因为我们已经检查了长度，所以s1和s2长度相同）
        for(int i=0;i<s1.length();i++) {
            // 检查当前字符在两个字符串中的出现次数是否相同
            // 如果不相同，说明它们不是彼此的排列，设置res为false并跳出循环
            if(hash1[s1[i]]!=hash2[s1[i]]) {
                res=false;
                break;
            }
        }
        // 返回最终的结果
        return res;
    }
};

数组模拟版本 

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        // 如果两个字符串的长度不相等，它们不能是彼此的排列，直接返回false
        if(s1.size() != s2.size()) return false;
        
        // 定义一个长度为26的数组，用于统计小写字母a到z在每个字符串中的出现次数
        // 初始化数组为0，表示开始时没有字符被统计
        int hash[26] = { 0 };
        
        // 遍历第一个字符串s1，统计每个字符的出现次数
        // 使用字符的ASCII码值减去'a'的ASCII码值，得到0-25的索引，表示a-z
        for(auto ch : s1) {
            hash[ch - 'a']++;
        }
        
        // 遍历第二个字符串s2，对每个字符的出现次数进行递减操作
        // 如果递减后的次数小于0，说明s2中某个字符的数量超过了s1中该字符的数量，
        // 因此s1和s2不能是彼此的排列，返回false
        for(auto ch : s2) {
            hash[ch - 'a']--;
            if(hash[ch - 'a'] < 0) return false;
        }
        
        // 如果遍历完s2后，没有返回false，说明s1和s2中每个字符的出现次数都相同，
        // 因此它们是彼此的排列，返回true
        return true;
    }
};

 

2.2.排序解法 

这题其实，我们只需要对两个字符串分别按字典序排序，如果说是字符重排的情况，那排序后的两个字符串一定是一样的。

class Solution {
public:
    // 定义一个公开的成员函数，用于检查两个字符串是否为彼此的排列
    bool CheckPermutation(string s1, string s2) {
        // 如果两个字符串的长度不相等，那么它们不能是彼此的排列，因为排列意味着
        // 两个字符串包含完全相同的字符，只是顺序可能不同。长度不同则直接返回false。
        if(s1.size() != s2.size()) return false;
        
        // 对两个字符串进行排序。排序的目的是将两个字符串的字符按照相同的顺序排列，
        // 如果它们是彼此的排列，排序后的字符串应该是相同的。
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        
        // 比较排序后的两个字符串。如果它们不相同，说明原始字符串不是彼此的排列，
        // 返回false。否则，如果相同，说明它们是彼此的排列，返回true。
        if(s1 != s2) {
            return false;
        }
        
        // 如果所有检查都通过，返回true，表示两个字符串是彼此的排列。
        return true;
    }
};

 题目三——217. 存在重复元素 - 力扣（LeetCode）

3.1.哈希表解法

 这道题目其实有很多解法，我先讲哈希表版本

就是使用哈希表记录每个元素的出现次数，如果哪个元素的出现次数大于1，就直接返回true就好了

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        std::unordered_map<int, int> hash;
        for (int num : nums) {
            // 直接增加计数，并检查是否已经大于1
            if (++hash[num] > 1) {
                // 如果计数大于1，说明找到了重复元素
                return true;
            }
        }
        // 遍历完整个数组都没有找到重复元素
        return false;
    }
};

 

3.2.排序解法 

我们完全可以先对这个数组排序，然后遍历数组看看是不是有两个相邻的元素是相同的，就行了

class Solution {
public:
    bool containsDuplicate(std::vector<int>& nums) {
        // 对整数向量进行排序。排序的目的是将相同的元素放在一起，以便后续检查。
        std::sort(nums.begin(), nums.end());
        
        // 遍历排序后的向量（从第二个元素开始，因为我们要比较当前元素与前一个元素）。
        for (int i = 1; i < nums.size(); i++) {
            // 如果当前元素与前一个元素相同，说明向量中包含重复元素。
            if (nums[i - 1] == nums[i]) {
                // 返回true，表示向量中包含重复元素。
                return true;
            }
        }
        
        // 如果遍历完整个向量都没有找到重复元素，返回false。
        return false;
    }
};

 

题目四——219. 存在重复元素 II - 力扣（LeetCode） 

 

解决该问题需要我们快速定位到两个信息： 

  1. 两个相同的元素；
  2. 这两个相同元素的下标。

因此，我们可以使⽤「哈希表」，令数组内的元素做key 值，该元素所对应的下标做val 值，将 「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。

        思考题： 将 如果数组内存在⼤量的「重复元素」，⽽我们判断下标所对应的元素是否符合条件的时候，需要将不 同下标的元素作⽐较，怎么处理这个情况呢？

答：这⾥运⽤了⼀个「⼩贪⼼」。

我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：

  • 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
  • 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变 ⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。 
class Solution 
{
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        // 使用 unordered_map 来存储每个数字最近出现的索引
        unordered_map<int, int> hash;
        
        // 遍历数组 nums
        for(int i = 0; i < nums.size(); i++)
        {
            // 检查当前数字 nums[i] 是否已经在哈希表中
            if(hash.count(nums[i]))
            {
                // 如果在哈希表中找到了相同的数字，检查索引差是否小于等于 k
                if(i - hash[nums[i]] <= k) 
                {
                    // 如果索引差小于等于 k，说明找到了符合条件的两个数字，返回 true
                    return true;
                }
            }
            
            // 更新哈希表中当前数字的最新索引
            hash[nums[i]] = i;
            
            // 注意：原代码中的 14, 15, 16, 17 行是空的，这里没有实际的代码需要解释或修改
        }
        
        // 如果遍历完整个数组都没有找到符合条件的两个数字，返回 false
        return false;
    }
};

题目五—— 49. 字母异位词分组 - 力扣（LeetCode）

这个题目其实我们可以 

互为字⺟异位词的单词有⼀个特点：

  • 将它们「排序」之后，两个单词应该是「完全相同」的。

所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀ 组中。

这时我们就要处理两个问题：

  1. 排序后的单词与原单词需要能互相映射；
  2. 将排序后相同的单词，「划分到同⼀组」；

利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点：

  1. 将排序后的字符串（ string ）当做哈希表的key值
  2. 将字⺟异位词数组（ string数组 ）当成val值

定义⼀个「哈希表」即可解决问题。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // 使用 unordered_map 存储排序后的字符串作为键，原始字符串的向量作为值
        unordered_map<string, vector<string>> hash;

        // 遍历字符串数组
        for (auto& s : strs) {
            // 创建一个临时字符串，用于存储排序后的结果
            string tmp = s;
            // 对临时字符串进行排序，这样字母异位词将具有相同的排序后字符串
            sort(tmp.begin(), tmp.end());

            // 将排序后的字符串作为键，将原始字符串添加到对应的值向量中
            // 这样就实现了将字母异位词分组存储
            hash[tmp].push_back(s);
        }

        // 准备一个向量，用于存储最终的结果
        vector<vector<string>> ret;

        // 遍历哈希表，将每个值向量（即一组字母异位词）添加到结果向量中
        // 使用传统的first和second成员访问方式遍历哈希表
        for (auto& elem : hash) {
            string x = elem.first;          // 键（排序后的字符串）
            vector<string> y = elem.second; // 值（包含原始字符串的vector）

            // 将值向量y添加到结果向量ret中
            ret.push_back(y);
        }

        // 返回最终结果
        return ret;
    }
};


http://www.kler.cn/a/416522.html

相关文章：

  • [Java]微服务配置管理
  • Docker desktop 改变存储位置
  • C++算法练习-day50——538.把二叉树转换为累加树
  • pageoffice最新版本浏览器点击没反应解决办法
  • Vuex —— Day1
  • 大数据新视界 -- 大数据大厂之 Hive 数据质量保障：数据清洗与验证的策略（上）（17/ 30）
  • Oracle系列---【关闭归档日志】
  • RL78/G15 Fast Prototyping Board Arduino IDE 平台开发过程
  • 【数据湖仓】-- 阿里云 EMR 和 AWS EMR 工具对比
  • 【Redis】Redis介绍
  • word2vec
  • 娱乐API：快速生成藏头诗、藏尾诗和藏中诗
  • 详解Ethereum交易当中的Input Data
  • 论文笔记：RAR: Retrieving And Ranking Augmented MLLMs for Visual Recognition
  • 算法思维初学者指南
  • XRD精修教程：CMPR软件介绍-测试狗
  • Spring Boot 开发环境搭建及示例应用
  • 数据分析-52-时间序列分解之变分模态分解VMD
  • 【论文笔记】Tool Learning with Foundation Models 论文笔记
  • 泷羽sec-蓝队基础之网络七层杀伤链（上） 学习笔记
  • 【Datawhale组队学习】模型减肥秘籍：模型压缩技术6——项目实践
  • 工业一体机在自动化产线的作用及核心优势有哪些
  • Docker for Everyone Plus——Unbreakable!
  • uni-app写的微信小程序每次换账号登录时出现缓存上一个账号数据的问题
  • （转）Uni-app 之IOS生成Universal Link(通用链接)
  • 【数据结构-队列】力扣641. 设计循环双端队列