算法思想总结：哈希表

一、哈希表剖析

1、哈希表底层：通过对C++的学习，我们知道STL中哈希表底层是用的链地址法封装的开散列。

2、哈希表作用：存储数据的容器，插入、删除、搜索的时间复杂度都是O（1），无序。

3、什么时候使用哈希表：需要频繁查找数据的场景。

4、OJ中如何使用哈希表？？？

（1）STL中的容器（适用所有场景，比如字符串相关、数据映射下标）

（2）数组模拟简易哈希表（减小时间损耗，容器的封装有一定代价）—>大多以下两种情况适用

情况1：（char）涉及到字符串中的“字符” ，hash[26]可以映射所有的字母。

情况2：（int）数据范围较小的时候

二、两数之和

. - 力扣（LeetCode）

解法2代码： 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        unordered_map<int,int> hash; //数值和下标的映射关系
        int n=nums.size();
        for(int i=0;i<n;++i)
        {
            int x=target-nums[i];
            if(hash.count(x)) return {hash[x],i};
            hash[nums[i]]=i;
        }
        return {-1,-1};
    }
};

 三、判定是否互为字符重排

. - 力扣（LeetCode）

 解法2代码：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) 
    {
        //小优化
        if(s1.size()!=s2.size()) return false;
        //用哈希表
        int hash[26]={0};
        for(char&ch:s1) ++hash[ch-'a'];
        //检测第二个数组
        for(char&ch:s2)  if(--hash[ch-'a']<0)  return false;
        return true;
    }
};

四、存在重复元素I

. - 力扣（LeetCode）

解法2代码：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
       unordered_set<int> hash; //有负数，所以必须用库里面的哈希表
       for(auto&e:nums) 
            if(hash.count(e)) return true;
              else hash.insert(e);
         return false;
    }
};

 五、存在重复元素II

. - 力扣（LeetCode）

解法1代码：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
        unordered_map<int,size_t> hash;//数值和下标的映射
        size_t n=nums.size();
        for(size_t i=0;i<n;++i)
        {
            //如果哈希表中有这个数
            if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true;
            hash[nums[i]]=i;//存下标的映射
        }
        return false;
    }
};

解法2代码：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
    //滑动窗口解题，让set始终保存着k个元素，如果发现了区间内有重复元素，那么就可以返回true
    unordered_set<int> s;
    size_t n=nums.size();
    for(size_t i=0;i<n;++i)
    {
        if(s.count(nums[i])) return true;
        s.emplace(nums[i]);//不断将数字丢进去
        if(i>=k) s.erase(nums[i-k]); //窗口超出区间了，就将最前面那个给删掉
    }
    return false;
    }
};

六、存在重复元素III(经典)

. - 力扣（LeetCode）

 解法1代码：

class Solution {
public:
    //绝对值尽量拆解掉
    //滑动窗口解决问题（控制区间）  需要支持插入、查找、删除  尽可能有序 set
    //k是下标的差值  t是元素的差值
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
        //lower_bound 利用二分找到第一个>=num的迭代器 降序就是<=
        //upper_bound 利用二分找到第一个>num的迭代器  降序就是<
        set<long> s;//需要一个有序集合
        for(size_t i=0;i<nums.size();++i)
           { 
             //在下标范围为 [max(0,i−k),i] 内找到值范围在 [u−t,u+t]的数。
             set<long>::iterator it=s.lower_bound((long)nums[i]-t);
             if(it!=s.end()&&*it<=(long)nums[i]+t) return true;
             s.insert(nums[i]);
             if(i>=k)  s.erase(nums[i - k]);
           }
           return false;
    }
};

 思路2：分桶（非常精巧的思路）

思路来源：. - 力扣（LeetCode）分桶思路详细讲解

     因为这个思路来源写得非常的详细，所以直接看就行，以往我们的分桶，更多的是针对整数的分桶，但是在该题中，扩展了存在负数的时候如何分桶，保证每个桶内的元素个数是一样的。这是一种非常巧妙的方法！！！要结合具体的实例去看！！

核心思路：保证每个桶内的绝对值相差小于t，k个桶。当我们遍历到这个数的时候，如果对应的桶的存在，就是true，如果相邻桶存在，看看差值是否符合要求。每个桶中只会有一个元素，因为有多的我们就会直接返回结果。

class Solution {
public:
    int getid(long u,long t)
    {
        return u>=0?u/(t+1):(u+1)/(t+1)-1;
    }
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
      //桶排序   
      size_t n=nums.size();
      //分成k个桶  每个桶的大小是t+1 (0,1,2,3) ->保证一个桶里面是符合的
      unordered_map<int,int> hash;  //第一个是存id  第二个是存元素
      for(size_t i=0;i<n;++i)
      {
        long u=nums[i];
        int id= getid(u,t); //找编号
        //看看当前桶存不存在
        if(hash.count(id)) return true;
        //看看相邻桶在不在，如果在的话 就看看差值
        if(  hash.count(id-1)&&u-hash[id-1]<=t
           ||hash.count(id+1)&&hash[id+1]-u<=t) return true;
        if(i>=k) hash.erase(getid(nums[i-k],t));//桶数多了，就去掉一个
        hash[id]=u;//开新的桶
      }
      return false;
    }
};

七、字母异位词分组(经典)

. - 力扣（LeetCode）

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //字母异位词->排序后都是相同的
        unordered_map<string,vector<string>> hash; //将异位词绑定起来
        for(auto&s:strs)
         {
            string temp=s;
            sort(temp.begin(),temp.end());
            hash[temp].emplace_back(s);
         }
         //提取出来
         vector<vector<string>> ret;
         for(auto&[x,y]:hash)  ret.emplace_back(y); //取哈希表中键值对的方法C++14支持
         //for(auto&kv:hash)  ret.push_back(kv.second);
         return ret;
    }
};

八、前K个高频单词（经典）

 . - 力扣（LeetCode）

解法1：map+vector+稳定排序+lambda优化
          map的底层是红黑树，插入的时候map<string,int> 会按照字典序排好，而我们现在要按照出现次序去排序，同时对于出现次数相同的保证字典序在前面，所以我们其中之一的策略就是vector+sort ,但是sort底层是快排，并不具备稳定性，但是库里面有一个stable_sort是稳定的排序

class Solution {
public:
     typedef pair<string,int> PSI;
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        //此时已经按照字典序排好了，将其拷贝到vector中
        vector<PSI> nums(countmap.begin(),countmap.end());
        //要用一个稳定的排序 我们排序的是比较value，所以要修改比较逻辑
        stable_sort(nums.begin(),nums.end(),
        [](const PSI&kv1,const PSI&kv2) {return kv1.second>kv2.second;});
        vector<string> ret(k);
        for(int i=0;i<k;++i)  ret[i]=nums[i].first;
        return ret;
    }
};

解法2：unordered_map+vector+sort+调整比较逻辑+lambda优化 

class Solution {
public:
    typedef pair<string,int> PSI;
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        //此时已经按照字典序排好了，将其拷贝到vector中
        vector<PSI> nums(countmap.begin(),countmap.end());
        //要用一个稳定的排序 我们排序的是比较value，所以要修改比较逻辑
        sort(nums.begin(),nums.end(),
        [](const PSI&kv1,const PSI&kv2){ 
            return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);});
        vector<string> ret(k);
        for(int i=0;i<k;++i)  ret[i]=nums[i].first;
        return ret;
    }
};

上面两种解法都是借助vector容器+sort去解决的。

 解法3：unordered_map+priority_queue+compare类

class Solution {
public:
   typedef pair<string,int> PSI;
    struct compare//要注意仿函数要+const修饰，否则可能编译不过
     {
        bool operator()(const PSI&kv1,const PSI&kv2) const
        {
            if(kv1.second==kv2.second) return kv1.first<kv2.first;
            return kv1.second>kv2.second;
        }
     };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        //丢到优先级队列里
        priority_queue<PSI,vector<PSI>,compare> heap;
        for (auto& it : countmap) {
            heap.push(it);
            if (heap.size() > k) heap.pop();
        }
        vector<string> ret(k);
       for(int i=k-1;i>=0;--i) 
        {
            ret[i]=heap.top().first;
            heap.pop();
        }
       return ret;
    }
};

 解法4：unordered_map+multiset+compare类

class Solution {
public:
   typedef pair<string,int> PSI;
    struct compare//要注意仿函数要+const修饰，否则可能编译不过
     {
        bool operator()(const PSI&kv1,const PSI&kv2) const
        {
            return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);
        }
     };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        unordered_map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        multiset<PSI,compare> sortmap(countmap.begin(),countmap.end());
        vector<string> ret(k);
        multiset<PSI,compare>::iterator it=sortmap.begin();
        size_t i=0;
        while(k--) 
        {
            ret[i++]=it->first;
            ++it;
        }
    return ret;
    }
};

 解法5：map+multimap+compare类（能过 但这是巧合）

       这题能过的原因是map实现了字典序的排序。而底层的multimap封装中对于相同的键值是优先插入到其右侧。

class Solution {
public:
     struct compare//要注意仿函数要+const修饰，否则可能编译不过
     {
        bool operator()(const int&k1,const int&k2) const
        {
            return k1>k2;
        }
     };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string,int> countmap;//计数
        for(auto&s:words) ++countmap[s];
        multimap<int,string,compare> sortmap;
        for(auto &kv:countmap) sortmap.insert(make_pair(kv.second,kv.first));
        vector<string> ret(k);
        auto it=sortmap.begin();
        size_t i=0;
        while(k--) 
        {
            ret[i++]=it->second;
            ++it;
        }
    return ret;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/664723.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Android HIDL接口添加

Android HIDL接口添加

一.HIDL介绍 HIDL的全称是HAL interface definition language&#xff08;硬件抽象层接口定义语言&#xff09;&#xff0c;是Android Framework 与Android HAL之间的接口。HIDL 旨在用于进程间通信 (IPC)&#xff0c;进程之间的通信 采用 Binder 机制。 二.HIDL 与AIDL 的对…
阅读更多...
客户文章｜难能可贵，非模式生物的功能研究与创新

客户文章｜难能可贵，非模式生物的功能研究与创新

菜豆&#xff08;Phaseolus vulgaris&#xff09;&#xff0c;又名四季豆、芸豆、油豆角&#xff0c;是全球第一大豆类蔬菜&#xff0c;我国是世界上最主要的菜豆生产国和销售国。在田间生产过程中&#xff0c;菜豆常面临着各种生物和非生物逆境的胁迫&#xff0c;对其产量品质…
阅读更多...
FOC - BLDC六步换相驱动原理

FOC - BLDC六步换相驱动原理

文章目录 1 . 前言2 . 电机旋转原理3 . BLDC特点4 . BLDC反电动势投影位置5 . BLDC换相时刻6 . BLDC换相注意事项7 . 小结 【全文大纲】 : https://blog.csdn.net/Engineer_LU/article/details/135149485 1 . 前言 无刷直流电机在这里区分为两种&#xff0c;一是永磁无刷直流电…
阅读更多...
【Linux-LCD 驱动】

【Linux-LCD 驱动】

Linux-LCD 驱动 ■ Framebuffer 简称 fb■ LCD 驱动程序编写■ 1、LCD 屏幕 IO 配置■ 2、LCD 屏幕参数节点信息修改■ 3、LCD 屏幕背光节点信息■ 4、使能 Linux logo 显示 ■ 设置 LCD 作为终端控制台■ 1、设置 uboot 中的 bootargs■ 2、修改/etc/inittab 文件 ■ LCD 背光…
阅读更多...
python前端streamlit模型部署

python前端streamlit模型部署

简单介绍使用前端streamlit框架快速部署本地模型&#xff1a; 1、模型训练&#xff1a; import pandas as pd # 流程整合 from sklearn.pipeline import make_pipeline, Pipeline # 数据处理 from sklearn.impute import SimpleImputer from sklearn.preprocessing import Min…
阅读更多...
探索 Android Studio 中的 Gemini：加速 Android 开发的新助力

探索 Android Studio 中的 Gemini：加速 Android 开发的新助力

探索 Android Studio 中的 Gemini&#xff1a;加速 Android 开发的新助力 在 Gemini 时代的下一篇章中&#xff0c;Gemini融入了更多产品中&#xff0c;Android Studio 正在使用 Gemini 1.0 Pro 模型&#xff0c;使 Android 开发变得更快、更简单。 Studio Bot 现已更名为 And…
阅读更多...
深度学习知识与心得

深度学习知识与心得

目录 深度学习简介 传统机器学习 深度学习发展 感知机 前馈神经网络 前馈神经网络&#xff08;BP网络&#xff09; 深度学习框架讲解 深度学习框架 TensorFlow 一个简单的线性函数拟合过程 卷积神经网络CNN&#xff08;计算机视觉&#xff09; 自然语言处理NLP Wo…
阅读更多...
C# WinForm —— 23 Timers.Timer 组件介绍与使用

C# WinForm —— 23 Timers.Timer 组件介绍与使用

1. 简介 System.Timers.Timer 计时器 轻量 每隔一段时间触发Elapsed事件&#xff0c;执行操作(不是由UI线程执行的)&#xff0c;即使事件中执行了比较耗时的操作&#xff0c;也不会造成 UI 失去响应 如果要获取服务器的计时功能的话&#xff0c;可以使用System.Timers.Timer …
阅读更多...
unity2020打包webGL时卡进程问题

unity2020打包webGL时卡进程问题

我使用的2020.3.0f1c1&#xff0c;打包发布WEB版的时候会一直卡到asm2wasm.exe这个进程里&#xff0c;而且CPU占用率90%以上。 即使是打包一个新建项目的空场景也是同样的问题&#xff0c;我尝试过一直卡在这里会如何&#xff0c;结果还真打包成功了。只是打包一个空场景需要20…
阅读更多...
C++(入门基础版本)

C++(入门基础版本)

1&#xff0c;什么是C C 是一种通用的、面向对象的编程语言&#xff0c;是 C 语言的一个超集&#xff0c;也就是说&#xff0c;任何有效的 C 程序都是有效的 C 程序。C 通过添加诸如类和对象、继承和多态等概念&#xff0c;扩展了 C 语言的功能&#xff0c;使其更适用于大型软…
阅读更多...
CSS学习笔记目录

CSS学习笔记目录

CSS学习笔记之基础教程&#xff08;一&#xff09; CSS学习笔记之基础教程&#xff08;二&#xff09; CSS学习笔记之中级教程&#xff08;一&#xff09; CSS学习笔记之中级教程&#xff08;二&#xff09; CSS学习笔记之中级教程&#xff08;三&#xff09; CSS学习笔记之高级…
阅读更多...
国产身份域管架构图集合（信创政策AD域替换必看）

国产身份域管架构图集合（信创政策AD域替换必看）

几类典型架构 双机架构 单点单机房 集群架构 多点单机房 两地三中心架构 多点多机房 多地分布式架构 多点多机房 全栈信创方案架构&#xff0c;欢迎探讨交流~
阅读更多...
[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别

[数据集][目标检测]喝水检测数据集VOC+YOLO格式995张3类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;995 标注数量(xml文件个数)&#xff1a;995 标注数量(txt文件个数)&#xff1a;995 标注类别…
阅读更多...
校园导航系统C++

校园导航系统C++

制作一个简单的大学城导航系统&#xff0c;根据用户指定的起点和终点&#xff0c;求出最短路径长度以及具体路径。 项目要求&#xff1a; 1&#xff09;程序与数据相分离&#xff0c;地图中的所有数据都是从文件读入&#xff0c;而不是写在代码中 2&#xff09;最短路径算法…
阅读更多...
抖音电商经验分享，揭秘做好抖店的七个关键细节，不容忽视

抖音电商经验分享，揭秘做好抖店的七个关键细节，不容忽视

大家好&#xff0c;我是电商花花。 随着抖音电商和大量商家的不断入驻&#xff0c;大家对于电商的玩法也逐渐变多&#xff0c;拿到结果的商家也是越来越多&#xff0c;更多的做店玩法和步骤被更多人熟知。 现在想要做好抖店&#xff0c;其实也没有想象中那么复杂和困难。 新…
阅读更多...
网络安全基础技术扫盲篇名词解释之“证书“

网络安全基础技术扫盲篇名词解释之“证书“

用通俗易懂的话说&#xff1a; 证书就好比是一张身份证&#xff08;类似&#xff0c;但不完全相同&#xff09;&#xff0c;用来证明一个网站的身份是否可信。就像你要确认一个陌生人的身份需要看他的身份证一样&#xff0c;电脑在连接一个网站时&#xff0c;也会查看网站的证…
阅读更多...
停车场车位引导系统方案升级实施步骤流程是什么，有什么注意事项

停车场车位引导系统方案升级实施步骤流程是什么，有什么注意事项

停车场车位引导系统是一种现代化的停车管理系统&#xff0c;它通过实时监测车位占用情况&#xff0c;并向驾驶员提供准确的空闲车位导航信息&#xff0c;从而提高停车场的使用效率和用户体验。随着城市交通的快速发展和车辆数量的不断增加&#xff0c;停车场车位引导系统已成为…
阅读更多...
树形结构-CRUD接口

树形结构-CRUD接口

先看一下效果&#xff1a;整体的效果 新增效果 --默认值是 default 修改效果 - 大致效果如上 --------------------------------------------------------------------------------------------------------------------------------- 下面讲解代码如何实现的 根据你使用…
阅读更多...
Pytorch中的torch.save()文件保存格式探索以及mmdetection加载预训练模型参数对不齐和收到意外参数报错解决方案

Pytorch中的torch.save()文件保存格式探索以及mmdetection加载预训练模型参数对不齐和收到意外参数报错解决方案

使用mmdetection时遇到的问题比较多&#xff0c;首先要对自己要使用的预训练模型有一定的了解&#xff0c;并且懂得使用各种分类模型时不同的模型不同任务执行阶段需要参数上的对其。&#xff08;比如mask-rcnn和它的三个头之间的参数&#xff09;。 首先&#xff0c;谈谈torc…
阅读更多...
一个案例告诉你，MySQL如何查询今天、昨天、近7天、近30天、本月、上个月、本季度、上季度、本年、上一年数据

一个案例告诉你，MySQL如何查询今天、昨天、近7天、近30天、本月、上个月、本季度、上季度、本年、上一年数据

参考博客 mysql查询当天/昨天/近7天/近30天/本月/上个月/本季度/上季度/本年/上一年 数据 正文内容 创建测试案例&#xff08;也可直接使用附录MySQL脚本生成数据&#xff09; 1、新建测试表 CREATE TABLE example (id INT AUTO_INCREMENT PRIMARY KEY,date_column DATE,d…
阅读更多...
最新文章

Copyright @ 2022~2023