算法打卡|Day5 哈希表part01

这篇具有很好参考价值的文章主要介绍了算法打卡|Day5 哈希表part01。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

哈希表 part01

今日任务
● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和


目录
    • 哈希表 part01
  • 链表理论基础
  • Problem: 242. 有效的字母异位词
    • 思路
    • 解题方法
    • Code
  • Problem: 349. 两个数组的交集
    • 思路
    • 解题方法
    • Code
  • Problem: 202. 快乐数
    • 思路
    • 解题方法
    • Code
  • Problem: 1. 两数之和
    • 思路
    • 解题方法
    • Code

链表理论基础

文章链接:https://programmercarl.com/哈希表理论基础.html#哈希表

重点:

  1. 哈希表是根据关键码的值而直接进行访问的数据结构。

  2. 一般哈希表都是用来快速判断一个元素是否出现集合里。

  3. 哈希表的关键是哈希函数。哈希函数如下图所示,通过hashCode把名字转化为数值,一般hashcode是通过特定编码方式,可以将其他数据格式转化为不同的数值,这样就把学生名字映射为哈希表上的索引数字了。
    算法打卡|Day5 哈希表part01

4.哈希函数映射到数组的同一个下标可能会产生哈希碰撞。如图所示,小李和小王都映射到了索引下标 1 的位置,这一现象叫做哈希碰撞。
算法打卡|Day5 哈希表part01

5.哈希碰撞可以用两种方法解决:第一是拉链法,冲突结点可以转换成链表结构存储。第二是线性检测法,需要有足够大的尺寸,让冲突结点存到其他地方去。

6.C++中的哈希表实现
算法打卡|Day5 哈希表part01
算法打卡|Day5 哈希表part01


Problem: 242. 有效的字母异位词

思路

首先我们因为字母是有限个,所以我们可以利用数组去存储。一共26个字母,所以数组大小为26,并且不用记住字母下标,只要计算与'a'的相对距离即可。遍历一遍数组a,遍历一遍数组b,最后我们通过查看结果数组即可判断是否是异位词。

解题方法

哈希表文章来源地址https://www.toymoban.com/news/detail-710419.html

Code


//时间复杂度: O(n)
//空间复杂度: O(1)


class Solution {
public:
  bool isAnagram(string s, string t) {
       int count[26] ={0};
       for(int i = 0; s[i] != '\0';i++){
          count[ (int)s[i]-'a']++;
       }
      for(int i = 0; t[i] != '\0';i++){
          count[ (int)t[i]-'a']--;
      }
      for(int i = 0; i < (sizeof (count) / sizeof (count[0]));i++){
          if(count[i] != 0) return false;
      }

      return true;
  }
};

Problem: 349. 两个数组的交集

思路

首先,用一个哈希表set去初始化第一个数组,用一个空哈希表专门保存结果数据,然后遍历第二个数组里的所有数字,如果有数字出现在哈希表中就插入结果哈希表中,最后返回这个结果哈希表。

解题方法

哈希表

Code


//时间复杂度: O(mn)
//空间复杂度: O(n)

class Solution {
public:
  vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
      unordered_set<int> res; // 存放结果,之所以用set是为了给结果集去重
      unordered_set<int> nums_set(nums1.begin(), nums1.end());

      for(auto num : nums2){
          if(nums_set.find(num) != nums_set.end()){
              res.insert(num);
          }
      }
      return vector<int>(res.begin(),res.end());
  }
};

Problem: 202. 快乐数

思路

首先我们每求到一个数字的快乐数,先判断这个快乐数曾经在哈希表出现过,如果出现过,那么说明这个数的求快乐数的过程会进入死循环,永远求不到快乐数==1的情况,就立刻返回false。如果没出现过就将该结果插入哈希表。

解题方法

先判断是否重复,再插入,如果有重复直接返回false,快乐数==1退出循环。

Code


//时间复杂度: O(logn)
//空间复杂度: O(logn)


class Solution {
public:

  int getSum(int n){
      int sum = 0;
      while(n){
          sum+=(n%10)*(n%10);
          n = n/10;
      }
      return sum;
  }
  bool isHappy(int n) {
      unordered_set<int> sum_res;
      while(1){
          int sum = getSum(n);
          if(sum == 1){
              return true;
          }

          if(sum_res.find(sum) != sum_res.end()){
              return false;
          }else{
              sum_res.insert(sum);
          }
          n = sum;
      }

  }
};

Problem: 1. 两数之和

思路

为什么会想到用哈希表?因为当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法。

哈希表为什么用map?因为我们问题要求我们返回的是下标。

本题map是用来存什么的?键存的是数值,方面find函数查找,值存的的下标,通过迭代器返回。

解题方法

哈希表

Code

/*
用unordered_map不是不能存储两个相同的key吗,那如果数组里两个出现相同的两个元素都要存储会怎么样呢?
注意它存入的方式,它是在循环的过程中边检验边存的,如果没有对应的数字就存入map,如果有就计数,这样不会遇到重复的
*/

//时间复杂度: O(n)
//空间复杂度: O(n)


class Solution {
public:
  vector<int> twoSum(vector<int>& nums, int target) {
      unordered_map<int, int> res;//创建一个map用来查找结果
      for(int i = 0; i < nums.size(); i++){
          //这里必须先判断再插入数据,因为如果先插入的话就会将自己算一遍
          auto iter = res.find(target-nums[i]);
          if(iter!=res.end()){
              return {iter->second,i};
          }
          else{
              res.insert(pair<int,int>(nums[i],i));
          }
      }
      return {}; 
  }
};

到了这里,关于算法打卡|Day5 哈希表part01的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯备赛 | 洛谷做题打卡day5

    题目描述 小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。 假设洛谷

    2024年01月17日
    浏览(58)
  • Day31 贪心算法 part01 理论基础 455.分发饼干 376.摆动序列 53.最大子序和

    什么是贪心 贪心的本质是选择每一阶段的局部最优,从而达到全局最优 。 这么说有点抽象,来举一个例子: 例如,有一堆钞票,你可以拿走十张,如果想达到最大的金额,你要怎么拿? 指定每次拿最大的,最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优,最

    2024年01月19日
    浏览(43)
  • 刷题笔记day07-哈希表part03

    2024年02月06日
    浏览(40)
  • ● day5:哈希表理论基础 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    ● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和 哈希表理论基础 建议:大家要了解哈希表的内部实现原理,哈希函数,哈希碰撞,以及常见哈希表的区别,数组,set 和map。 什么时候想到用哈希法, 当我们遇到了要快速判断一

    2024年02月05日
    浏览(51)
  • Leetcoder Day12|二叉树part01

    语言:Java/C++  目录 二叉树理论基础 二叉树种类 满二叉树 完全二叉树 二叉搜索树 平衡二叉搜索树 二叉树的存储方式 二叉树的遍历方式 二叉树的定义 二叉树的递归遍历 二叉树的迭代遍历 二叉树的统一迭代法 今日心得 二叉树种类 在数据结构中对二叉树的考察往往是重点

    2024年01月20日
    浏览(64)
  • 代码随想录 day38 第九章 动态规划part01

    ●  理论基础 ●  509. 斐波那契数 ●  70. 爬楼梯 ●  746. 使用最小花费爬楼梯 理论基础 解决动态规划必须要想清楚的点 dp数组以及下标的含义 递推公式 dp数组如何初始化 遍历顺序 打印数组 检查结果 关联 leetcode 509. 斐波那契数 思路 动规五部曲 dp数组以及下标的含义

    2024年04月17日
    浏览(48)
  • day1-数组part01| 704. 二分查找、27. 移除元素

    数组是存放在连续内存空间上的相同类型数据的集合。 数组下标从0开始 数组内存空间的地址是连续的 1、vector是顺序容器,其利用连续的内存空间来存储元素,但是其 内存空间大小是能够改变的 。 2、array是顺序容器,其也是利用连续的内存空间来存储元素,但它的 内存空

    2024年02月05日
    浏览(46)
  • 【迎战蓝桥】 算法·每日一题(详解+多解)-- day5

    🤞目录🤞 💖1. 数组中出现次数超过一半的数字 💖2. 二进制中1的个数 💖3. 替换空格 【大家好,我是 爱干饭的猿 ,如果喜欢这篇文章, 点个赞 👍, 关注一下吧, 后续会一直分享题目与算法思路 】 描述 给一个长度为 n 的数组,数组中有一个数字出现的次数超过数组长

    2023年04月08日
    浏览(39)
  • 贪心算法part01 算法

    ● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和 https://leetcode.cn/problems/assign-cookies/description/ https://leetcode.cn/problems/wiggle-subsequence/description/ https://leetcode.cn/problems/maximum-subarray/description/

    2024年02月02日
    浏览(40)
  • 每日算法打卡:波动数列 day 16

    1214. 波动数列 题目难度:中等 题目来源:第五届蓝桥杯省赛C++ A组,第五届蓝桥杯省赛Java A组 观察这个数列: 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加2或者减少3, 且每一项都为整数 。 栋栋对这种数列很好奇,他想知道长度为 n 和为 s 而且后一项总是比前一项增

    2024年01月16日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包