首页 > 编程语言 >有关哈希表算法

有关哈希表算法

时间:2024-04-05 19:59:49浏览次数:27  
标签:下标 哈希 有关 元素 算法 数组 表中 例题

例题一

解法(哈希表): 算法思路: • 如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中,然后直接在哈希表中查找每⼀个元素的 target - nums[i] ,就能快速的找到「⽬标和的下标」。 • 这⾥有⼀个⼩技巧,我们可以不⽤将元素全部放⼊到哈希表之后,再来⼆次遍历(因为要处理元素相同的情况)。⽽是在将元素放⼊到哈希表中的「同时」,直接来检查表中是否已经存在当前元素所对应的⽬标元素(即 target - nums[i] )。如果它存在,那我们已经找到了对应解,并⽴即将其返回。⽆需将元素全部放⼊哈希表中,提⾼效率。 • 因为哈希表中查找元素的时间复杂度是 O(1) ,遍历⼀遍数组的时间复杂度为 O(N) ,因此可以 将时间复杂度降到 O(N) 。这是⼀个典型的「⽤空间交换时间」的⽅式。

例题二

解法(哈希表): 算法思路: 1. 当两个字符串的⻓度不相等的时候,是不可能构成互相重排的,直接返回 false ; 2. 如果两个字符串能够构成互相重排,那么每个字符串中「各个字符」出现的「次数」⼀定是相同 的。因此,我们可以分别统计出这两个字符串中各个字符出现的次数,然后逐个⽐较是否相等即 可。这样的话,我们就可以选择「哈希表」来统计字符串中字符出现的次数。

例题三

解法(哈希表): 算法思路: 分析⼀下题⽬,出现「⾄少两次」的意思就是数组中存在着重复的元素,因此我们可以⽆需统计元素出现的数⽬。仅需在遍历数组的过程中,检查当前元素「是否在之前已经出现过」即可。 因此我们可以利⽤哈希表,仅需存储数「组内的元素」。在遍历数组的时候,⼀边检查哈希表中是否已经出现过当前元素,⼀边将元素加⼊到哈希表中。

例题四

解法(哈希表): 算法思路: 解决该问题需要我们快速定位到两个信息: • 两个相同的元素; • 这两个相同元素的下标。 因此,我们可以使⽤「哈希表」,令数组内的元素做 key 值,该元素所对应的下标做 val 值,将 「数组元素」和「下标」绑定在⼀起,存⼊到「哈希表」中。 思考题: 如果数组内存在⼤量的「重复元素」,⽽我们判断下标所对应的元素是否符合条件的时候,需要将不同下标的元素作⽐较,怎么处理这个情况呢? 答:这⾥运⽤了⼀个「⼩贪⼼」。 我们按照下标「从⼩到⼤」的顺序遍历数组,当遇到两个元素相同,并且⽐较它们的下标时,这两个下标⼀定是距离最近的,因为: • 如果当前判断符合条件直接返回 true ,⽆需继续往后查找。 • 如果不符合条件,那么前⼀个下标⼀定不可能与后续相同元素的下标匹配(因为下标在逐渐变⼤),那么我们可以⼤胆舍去前⼀个存储的下标,转⽽将其换成新的下标,继续匹配。

例题五

解法(哈希表 + 排序): 算法思路: 互为字⺟异位词的单词有⼀个特点:将它们「排序」之后,两个单词应该是「完全相同」的。 所以,我们可以利⽤这个特性,将单词按照字典序排序,如果排序后的单词相同的话,就划分到同⼀组中。 这时我们就要处理两个问题: • 排序后的单词与原单词需要能互相映射; • 将排序后相同的单词,「划分到同⼀组」; 利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点: • 将排序后的字符串( string )当做哈希表的 key 值; • 将字⺟异位词数组( string[] )当成 val 值。 定义⼀个「哈希表」即可解决问题。

标签:下标,哈希,有关,元素,算法,数组,表中,例题
From: https://blog.csdn.net/2301_79881188/article/details/137400623

相关文章

  • 逐点插入法【二叉查找(排序)树的插入算法】
    问题描述:利用逐点插入法建立序列{50,72,43,85,75,20,35,45,65,30}对应的二叉树排序后,查找元素30要进行多少次元素间的比较?首先我来解释以下什么是二叉查找树:二叉查找树是一棵空树,或者是具有如下性质的二叉树:(1)若它的左子树非空,则左子树中所有结点的值均小于根节点的值(2)若它的右......
  • 代码随想录算法训练营第二天 | 数组 209.长度最小的子数组
    leetcode209.长度最小的子数组题目209.长度最小的子数组给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的连续子数组[numsl,numsl+1,...,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。......
  • 蓝桥杯备考随手记: 常用的三种排序算法(冒泡排序、插入排序、选择排序)
    1.冒泡排序(BubbleSort)冒泡排序是一种简单直观的排序算法,在待排序序列中不断地交换相邻两个元素的位置,通过多次遍历,将最大(或最小)的元素逐渐向右(或左)移动到正确的位置,直到整个序列有序。冒泡排序的基本思想如下:从序列的第一个元素开始,比较相邻两个元素的大小。如果前一个元......
  • 算法分析与设计——实验1: 递归与分治
    实验一 递归与分治一、实验目的        1、理解分治算法的概念和基本要素;        2、理解递归的概念;        3、掌握设计有效算法的分治策略。二、实验内容和要求实验要求:通过上机实验进行算法实现,保存和打印出程序的运行结果,并结合程序进行......
  • 常见面试算法题-发广播
    ■ 题目描述某地有N个广播站,站点之间有些有连接,有些没有。有连接的站点在接受到广播后会互相发送。给定一个N*N的二维数组matrix,数组的元素都是字符’0’或者’1’。matrix[i][j]=‘1’,则代表i和j站点之间有连接,matrix[i][j]=‘0’代表没连接,现在要发一条广播,问初始最少......
  • Java中常用的加密算法及其实现原理详解(二)
    本系列文章简介:        随着互联网的快速发展,信息的安全保护愈发重要。在软件开发中,加密算法被广泛应用于数据的加密和解密过程中,以保护敏感信息的机密性和完整性。Java作为一种广泛应用于企业级开发的编程语言,也提供了丰富的加密算法库。        本文将介绍......
  • 文心一言 VS 讯飞星火 VS chatgpt (230)-- 算法导论17.1 1题
    一、如果栈操作包括MULTIPUSH操作,它将k个数据项压入栈中,那么栈操作的摊还代价的界还是O(1)吗?文心一言:在栈的基本操作中,我们通常考虑的是单个元素的压入(push)和弹出(pop)操作,这些操作的摊还代价通常是O(1)。摊还代价考虑的是一系列操作的平均代价,而不是单个操作的最坏......
  • 代码随想录算法训练营第二十四天 二十五 | 回溯的理论基础,77. 组合 216. 组合总和 II
    77.组合https://leetcode.cn/problems/combinations/description/List<List<Integer>>res=newArrayList<>();List<Integer>path=newArrayList<>();publicList<List<Integer>>combine(intn,intk){......
  • 九、算法-排序-堆排序
    常见六大排序:冒泡、选择、插入、快速、归并、堆。在了解堆排序之前,需要了解数据结构-二叉树的知识。二叉树:树中的每个节点下最多只有两个叶子节点;根节点:二叉树的首个节点;叶子节点:非根的节点;父节点-子节点:父节点下方归属的为子节点,是相对而言的关系,在顺序存储的数据结构里......
  • 分类预测 | Matlab实现CPO-LSSVM冠豪猪算法优化最小支持向量机数据分类预测
    分类预测|Matlab实现CPO-LSSVM冠豪猪算法优化最小支持向量机数据分类预测目录分类预测|Matlab实现CPO-LSSVM冠豪猪算法优化最小支持向量机数据分类预测分类效果基本介绍程序设计参考资料分类效果基本介绍1.Matlab实现CPO-LSSVM冠豪猪算法优化最小支持......