哈希表(知识点+leetcode)以及字符串哈希

news/2024/9/14 2:16:39/ 标签: 哈希算法, 散列表, leetcode

文章目录

  • 一、什么是哈希表
  • 二、哈希表常见结构介绍
  • leetcode经典例题
    • 242 有效的字母异位词
      • 思路
      • 编程
    • 349 两个数组的交集
      • 思路
      • 编程
    • 1 两数之和
      • 思路
      • 编程
    • 454 四数相加II
      • 思路
      • 编程
  • 字符串哈希
    • 前言
    • 思路
    • 编程

一、什么是哈希表

哈希表是散列表,就是通过关键码值而直接进行访问的一种数据结构

哈希表中关键码就是数组的索引下标,然后通过下标直接访问数组中的元素

其内部由一个个key:value 样式的键值对组成。

哈希表中的key通过哈希函数得到内存地址,然后将key和value放到对应的内存地址,从而实现通过key获取Value的方式

哈希碰撞:2个不同的key通过哈希函数(hash function)得到了相同的内存地址,也就是是内存地址已经被一个占用了,解决方法是将其中之一变为链表结构,使用next指向。这样内存地址就不会重复,但是会影响查询

二、哈希表常见结构介绍

总体结构上分为数组、set、map

  • 数组也是一种意义上的哈希表
  • set的结构中每个元素都是一个值(类似于数组)
  • map的结构是一个 key:value 的数据结构

重点讲:unordered_map(哈希表)

  • unordered_map底层存储的是<key,value>键值对,可以通过key快速的索引到value unordered_map内部因为是数据是通过映射存入哈希桶内的,所以对unordered_map进行遍历得到的是一个无序的序列
  • unordered_map通过key进行访问的速度比map快,但是遍历元素的迭代效率就要低于map了。unordered_map也实现了operator[ ] 可以通过key直接访问到value

以上概念来源于:https://blog.csdn.net/qq_60831089/article/details/131465770?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522172111625416800213021917%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=172111625416800213021917&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_click~default-2-131465770-null-null.142^v100^pc_search_result_base5&utm_term=哈希表c%2B%2B&spm=1018.2226.3001.4187

leetcode_24">leetcode经典例题

242 有效的字母异位词

题目来源:https://leetcode.cn/problems/valid-anagram/description/

思路

使用哈希表下标索引,判断这两个字符串每个字符出现的次数即可。

编程

class Solution {
public:bool isAnagram(string s, string t) {int hash[27]={0};for(int i=0;i<s.size();++i){hash[s[i]-'a']++;}for(int i=0;i<t.size();++i){hash[t[i]-'a']--;}for(int i=0;i<26;++i){if(hash[i]!=0) return false;}return true;}
};

349 两个数组的交集

题目来源:https://leetcode.cn/problems/intersection-of-two-arrays/description/

思路

选择unordered_set避免数据重复,将nums1的序列存入哈希表unordered_set中,遍历查找nums2相同的值即可

编程

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> ans;unordered_set<int> a(nums1.begin(),nums1.end());for(int i=0;i<nums2.size();++i){if(a.find(nums2[i])!=a.end()){ans.insert(nums2[i]);}}return vector<int>(ans.begin(),ans.end());    }
};

1 两数之和

思路

选择unordered_map来存储数值和下标,遍历nums数列,若在unordered_map找到target-nums[i]对应的值,则输出它们的下标,找不到则将当前的值和下标存入哈希表即可

编程

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> ans;for(int i =0;i<nums.size();i++){auto t= ans.find(target-nums[i]);if(t==ans.end()){ans.insert(make_pair(nums[i],i));}else{return {t->second,i};}}return {};}
};

454 四数相加II

思路

先对式子做移项处理,nums1[i] + nums2[j] =-(nums3[k] + nums4[l] ),那么我们也是选择用unordered_map来存储数组,先将nums1[i] + nums2[j] 的所有数存入哈希表中,然后在哈希表里面找-(nums3[k] + nums4[l] ),若匹配则计数器加上哈希表-(nums3[k] + nums4[l] )的个数,最后返回计数器即可

编程

class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> m;int ans=0;for(auto i : nums1)for(auto j : nums2){m[i+j]++;}for(auto i : nums3)for(auto j : nums4){int t=-(i+j);if(m.find(t)!=m.end()) ans+=m[t];}return ans;}
};

字符串哈希

题目来源:https://www.luogu.com.cn/problem/P3370

前言

字符串哈希是一种将字符串映射为整数的算法。哈希函数将字符串映射到一个固定大小的整数,这个整数通常称为哈希值或哈希码。

思路

首先防止数据溢出,我们需要用到unsigned long long(当数据超出264时会自动取模),参数p取131防止哈希碰撞,对于这题来说用的是进制哈希(把每个字符看作每个进制位上的一个数字,这个串转换为一个基于进制p的数),将字符串通过进制哈希转换完后进行排序,最后比较相邻元素即可

编程

const int N=1e4+5;
ULL a[N],p=131,h=0;
void solve(){int n;cin >> n;for(int i=0;i<n;++i){string s;cin >> s;h=0;for(int i=0;i<s.size();++i){h=h*p+s[i];}a[i]=h;}int ans=0;sort(a,a+n);for(int i=0;i<n;++i){if(a[i]!=a[i+1]) ans++;}cout << ans;return ;
}

http://www.ppmy.cn/news/1475887.html

相关文章

16_Shell好用工具:sed

16_Shell好用工具&#xff1a;sed 零、语法解析 sed [选项参数] [模式匹配/sed命令] 文件 命令说明aadd&#xff0c;新增iinsert&#xff0c;新增cchange&#xff0c;修改ssubstitute&#xff0c;替换ddelete&#xff0c;删除pprint, 打印 通常与 -n 连用 一、增&#xff08;…

五、 计算机网络(考点篇)

1 网络概述和模型 计算机网络是计算机技术与通信技术相结合的产物&#xff0c;它实现了远程通信、远程信息处理和资源共享。计算机网络的功能&#xff1a;数据通信、资源共享、管理集中化、实现分布式处理、负载均衡。 网络性能指标&#xff1a;速率、带宽(频带宽度或传送线路…

Lua协程(同步的多线程)

1.coroutine.create( func ) 创建一个协程&#xff0c;返回co&#xff08;coroutine&#xff09;&#xff0c;参数是一个函数&#xff0c;当调用resume时就唤醒co并调用函数 2.coroutine.resume(co, 函数参数们) 启动协程co并传入协程调用函数的参数&#xff0c;可以带回协程…

PHP恋爱话术微信小程序系统源码

&#x1f496;恋爱高手的秘密武器&#xff01;恋爱话术微信小程序&#xff0c;让情话信手拈来✨ &#x1f4ad;【开场白&#xff1a;恋爱路上的甜蜜助手】&#x1f4ad; 还在为跟心仪的TA聊天时找不到话题而尴尬&#xff1f;或是担心自己说的每句话都显得那么“直男/女”&…

zookeeper和Kafka消息队列群集部署

消息队列概念 什么是消息队列 消息&#xff08;Message&#xff09;是指在应用间传送的数据消息队列&#xff08;Message Queue&#xff09;是一种应用间通信方式解决方法&#xff0c;确保消息的可靠传输 消息队列的特征 存储 将消息存储在某种类型的缓冲区中&#xff0c;…

电脑如何快速删除相同的文件?分享5款重复文件删除工具

您有没有发现最近电脑运行速度变慢了&#xff1f;启动时间变得更长&#xff0c;甚至完成简单任务也难以如常&#xff1f;这可能是因为重复文件堆积所致。我们发现&#xff0c;清理或移动这些重复的文件和文件夹可以产生惊人的效果。通过删除不必要的重复文件和垃圾文件&#xf…

传输层协议之UDP

1、端口号 我们在应用层创建的套接字&#xff0c;是需要通过bind()接口绑定我们的IP地址与端口号的&#xff0c;这是因为数据从传输层向上交付到应用层时&#xff0c;需要用端口号来查找特定的服务进程。一般在网络通信时&#xff0c;用IP地址标识一台主机&#xff0c;用端口号…

一文学会鉴别“套壳”ChatGPT模型

一文学会鉴别“套壳”ChatGPT模型 随着ChatGPT等明星模型的诞生&#xff0c;市场上也开始出现一些“套壳”现象&#xff0c;即部分模型表面标榜原创或先进&#xff0c;实则在核心算法上与知名模型高度相似。作为技术探索者&#xff0c;如何拨开迷雾&#xff0c;识别这些“李鬼…

蓝桥杯14小白月赛题解

直接输出pi/ti,for遍历 #include <iostream> using namespace std; #define int long long int a,b,c ; double t1.00; signed main() {cin>>a;int an0;for(int i1;i<a;i){cin>>b>>c;if(t>c*1.00/b){tc*1.00/b;ani;} }cout<<an<<e…

MYSQL--第八次作业

MYSQL–第八次作业 一、备份与恢复 环境搭建&#xff1a; CREATE DATABASE booksDB; use booksDB;CREATE TABLE books ( bk_id INT NOT NULL PRIMARY KEY, bk_title VARCHAR(50) NOT NULL, copyright YEAR NOT NULL );CREATE TABLE authors ( auth_id INT NOT NULL PRI…

老物件线上3D回忆展拓宽了艺术作品的展示空间和时间-深圳华锐视点

在数字技术的浪潮下&#xff0c;3D线上画展为艺术家们开启了一个全新的展示与销售平台。这一创新形式不仅拓宽了艺术作品的展示空间&#xff0c;还为广大观众带来了前所未有的观赏体验。 3D线上画展制作以其独特的互动性&#xff0c;让艺术不再是单一的视觉享受。在这里&#x…

大数据之路 读书笔记 Day6 离线数据开发之数据开发平台

回顾 Day5 数据同步遇到的问题与解决方案Day4 数据同步 1. 统一计算平台 1.1 MaxCompute概述 MaxCompute&#xff08;原名 ODPS&#xff0c;Open Data Processing Service&#xff09;是阿里云提供的一种快速、完全托管的EB级数据仓库解决方案。它为用户提供了海量数据存储和实…

STM32智能无人机控制系统教程

目录 引言环境准备智能无人机控制系统基础代码实现&#xff1a;实现智能无人机控制系统 4.1 数据采集模块 4.2 数据处理与控制算法 4.3 通信与网络系统实现 4.4 用户界面与数据可视化应用场景&#xff1a;无人机管理与优化问题解决方案与优化收尾与总结 1. 引言 智能无人机控…

[终端安全]-6 移动终端之应用程序安全

笔者在终端安全专题前面的文章中介绍了移动终端硬件安全和操作系统安全&#xff0c;本文主要介绍移动终端应用安全。在本文最前面&#xff0c;笔者想先解答一位朋友的疑问&#xff0c;为什么需要费心打造一个完整的面面俱到的安全体系&#xff1f; 1 移动终端安全的重要性 移…

C++——类和对象(上)

文章目录 一、类的定义1.类定义格式2.访问限定符3.类域 二、实例化1.实例化概念2.对象⼤⼩ 三、 this指针 一、类的定义 1.类定义格式 与定义结构体类似 class ST {//成员变量int val;//成员函数void print(){cout << val << endl;}};class为定义类的关键字&…

P2p网络性能测度及监测系统模型

P2p网络性能测度及监测系统模型 网络IP性能参数 IP包传输时延时延变化误差率丢失率虚假率吞吐量可用性连接性测度单向延迟测度单向分组丢失测度往返延迟测度 OSI中的位置-> 网络层 用途 面相业务的网络分布式计算网络游戏IP软件电话流媒体分发多媒体通信 业务质量 通过…

【机器学习】Exam4

实现线性不可分logistic逻辑回归 我们目前所学的都是线性回归&#xff0c;例如 y w 1 x 1 w 2 x 2 b y w_1x_1w_2x_2b yw1​x1​w2​x2​b 用肉眼来看数据集的话不难发现&#xff0c;线性回归没有用了&#xff0c;那么根据课程所学&#xff0c;我们是不是可以增加 x 3 x…

【Linux】Vim 使用教程

Linux - Vim Vim 是一款在 Linux 系统中广泛使用的文本编辑器&#xff0c;它是 Vi 编辑器的升级版。Vim 不仅功能强大&#xff0c;而且可高度定制化&#xff0c;是许多程序员和系统管理员的首选工具。以下是 Vim 在 Linux 系统中的安装、配置和使用过程的详细讲解。 附注&…

Gitea 仓库事件触发Jenkins远程构建

文章目录 引言I Gitea 仓库事件触发Jenkins远程构建1.1 Jenkins配置1.2 Gitea 配置引言 应用场景:测试、生产环境的项目自动构建和部署 手动构建和部署 Gitea 仓库事件触发Jenkins远程构建I Gitea 仓库事件触发Jenkins远程构建 Gitea支持用于仓库事件的Webhooks 1.1 Jenkin…

3-2 多层感知机的从零开始实现

import torch from torch import nn from d2l import torch as d2lbatch_size 256 # 批量大小为256 train_iter, test_iter d2l.load_data_fashion_mnist(batch_size) # load进来训练集和测试集初始化模型参数 回想一下&#xff0c;Fashion-MNIST中的每个图像由 28 28 784…