当前位置: 首页 > news >正文

[代码随想录06]哈希表的使用,有效字母异位词,两数组交集,快乐数,两数之和

前言

哈希表是什么?一句话带你理解,简单来说我们对于杂乱的数据,怎么快速找到数据,如何做呢?一般的做法就是遍历复杂度为o(N)去找寻一个数据,但是吧,我们这样思考的话,还是花了大量时间去检查其他元素是否存在这个集合里面,如何优化呢?我们通过特定的计算把每个值都用特定的值来唯一表示起来,我们每次查询只需要通过计算,然后看这个特定的结构里面是否有对应映射的值,这种情况下,我们的查询效率就能达到o(1),这个做法也就是前文提到的空间换时间。

有了特定的索引值去表示,这个数据是否存在,那么就会存在哈希冲突,哈希冲突就是多个值对应一个索引值,我们就无法判断。这个时候一般的做法就是再哈希,线性探测(闭散列),拉链法(开散列)拉一个链表在冲突的地方。

HashTable的三种结构:①数组 ②set ③unordered_map对应底层的数据结构也是不一样的

题目链接

242. 有效的字母异位词 - 力扣(LeetCode)

349. 两个数组的交集 - 力扣(LeetCode)

202. 快乐数 - 力扣(LeetCode)

1. 两数之和 - 力扣(LeetCode)

一、有效的字母异位词

思路:三个for循环搞定,一个for循环就是把数据存进去,第二个for循环就是把数据取走,第三个for循环就是检查还有没有数据在里面。就能判定字母是否是异位词。

 tips:使用数组可以在空间的效率上有提升。这道题建议使用数组能起到联系的作用。

class Solution {
public:
//使用数组bool isAnagram1(string s, string t) {if(s.length()!=t.length())return false;int records[26]={0};for(auto it:s)  records[it-'a']++;for(auto it:t)  records[it-'a']--;for(auto it:records){if(it!=0)return false;}return true;}
//使用map表bool isAnagram2(string s, string t) {if(s.length()!=t.length())return false;unordered_map<int,int>dic;for(auto it:s)  dic[it]+=1;for(auto it:t)  dic[it]-=1;for(auto it:dic){if(it.second!=0)return false;}return true;}
};

二、两个数组的交集

思路:两个数组的交集,我们首先想到的就是用哈希的思想去找到两个共同元素,这样就强迫我们私用不能重复的结构set,然后用一个对结果集合进行去重,一个就是单纯用来存放一组数据的,方便我们去遍历查找,最后我们使用。

//使用set去重,然后循环遍历查找入结果集。vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>result_set;unordered_set<int>nums_set(nums1.begin(),nums1.end());for(auto num:nums2){if(nums_set.find(num)!=nums_set.end())result_set.insert(num);}return vector<int>(result_set.begin(),result_set.end());}

leetcode 对数值的大小修订之后我们就可以使用数组来解决这个问题。

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int>result_set;int hash[1005]={0};for(auto num:nums1){hash[num]=1;}for(int num:nums2){if(hash[num]==1)result_set.insert(num);}return vector<int>(result_set.begin(),result_set.end());}

三、快乐数

思路:题目说了直到1为止就会跳出循环。

int bitsum(int n){int sum=0;while(n){sum+=(n%10)*(n%10);n=n/10;}return sum;
}
bool isHappy(int n) {unordered_set<int>set;while(1){int sum=bitsum(n);if(sum==1)return true;if(set.find(sum)!=set.end()) return false;set.insert(sum);n=sum;}
}

 使用快慢指针的方法,循环两者终将会相遇

int bitsum(int n){int sum=0;while(n){sum+=(n%10)*(n%10);n=n/10;}return sum;}bool isHappy(int n) {int slow=n,fast=n;do{slow=bitsum(slow);fast=bitsum(fast);fast=bitsum(fast);}while(slow!=fast);return slow==1;}

四、两数之和

哈希表的精髓所在:直接使用target-num[i]去查找一个元素的是否存在集合中。

vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();unordered_map<int,int>mp;for(int i=0;i<n;i++){auto it=mp.find(target-nums[i]);if(it!=mp.end()) return {it->second,i};mp[nums[i]]=i;}return {};}

总结

学会了哈希表的用法,我们主要掌握一个思想,判断一个数是否在集合里,使用什么最快,当然是哈希表。当然这个比较对比的方式可以不同,比如第二题,两个比较,第三题和自己比较,第四题相减比较。共同进步!兄弟们!!!!!!!

相关文章:

[代码随想录06]哈希表的使用,有效字母异位词,两数组交集,快乐数,两数之和

前言 哈希表是什么&#xff1f;一句话带你理解&#xff0c;简单来说我们对于杂乱的数据&#xff0c;怎么快速找到数据&#xff0c;如何做呢&#xff1f;一般的做法就是遍历复杂度为o(N)去找寻一个数据&#xff0c;但是吧&#xff0c;我们这样思考的话&#xff0c;还是花了大量时…...

【CSS】一篇掌握CSS

不是因为有了希望才去坚持,而是坚持了才有了希望 目录 一.导入方式 1.行内样式 2.内部样式 3.外部样式(常用) 二.选择器 1.基本选择器(常用) 1.1标签选择器 1.2类选择器 1.3id选择器 2.层次选择器 2.1后代选择器 2.2子选择器 2.3相邻兄弟选择器 2.4通用兄弟选择器…...

分层图最短路

常见情形&#xff1a; 对于边有k次操作的题。。 整体思想&#xff1a; 分层图最短路可以视作是dijkstra的一个扩展&#xff0c;通常用于处理N小于10000&#xff0c;或者是k不大的情形。整体有点类似于拆点。将一个点拆成k个点处理。层与层之间互不影响。 好了我就说这么多&…...

vue3 基本使用

Vue 3 提供了多种方式来构建用户界面&#xff0c;包括选项式 API 和 Composition API。下面我将详细介绍 Vue 3 的基本使用和语法&#xff0c;主要集中在选项式 API 上&#xff0c;因为这对于初学者来说更容易上手。 1. 创建 Vue 项目 如果你还没有一个 Vue 项目&#xff0c;…...

【maven-4】IDEA 配置本地 Maven 及如何使用 Maven 创建 Java 工程

IntelliJ IDEA&#xff08;以下简称 IDEA&#xff09;是一款功能强大的集成开发环境&#xff0c;广泛应用于 Java 开发。下面将详细介绍如何在 IDEA 中配置本地 Maven&#xff0c;并创建一个 Maven Java 工程&#xff0c;快速上手并高效使用 Maven 进行 Java 开发。 1. Maven …...

种花问题算法

假设有一个很长的花坛&#xff0c;一部分地块种植了花&#xff0c;另一部分却没有。可是&#xff0c;花不能种植在相邻的地块上&#xff0c;它们会争夺水源&#xff0c;两者都会死去。 给你一个整数数组 flowerbed 表示花坛&#xff0c;由若干 0 和 1 组成&#xff0c;其中 0 …...

对于大规模的淘宝API接口数据,有什么高效的处理方法?

1.数据分批处理 原理&#xff1a;当处理大规模数据时&#xff0c;一次性将所有数据加载到内存中可能会导致内存溢出。将数据分成较小的批次进行处理可以有效避免这个问题。示例代码&#xff1a;假设通过淘宝 API 获取到了一个包含大量商品详情的 JSON 数据列表&#xff0c;每个…...

openharmony 使用uvc库获取摄像头数据使用nativewindow显示

界面代码&#xff1a; XComponent({ id: xcomponentId, type: texture, libraryname: entry }).width(800).height(500) Natvie代码&#xff1a; 1、头文件 //NativeWindow #include <ace/xcomponent/native_interface_xcomponent.h> #include <cstdint> #incl…...

SQL Server 实战 - 多种连接

目录 背景 一、多种连接 1. 复合连接条件 2. 跨数据库连接 3. 隐连接 4. 自连接 5. 多表外连接 6. UNION ALL 二、一个对比例子 背景 本专栏文章以 SAP 实施顾问在实施项目中需要掌握的 sql 语句为偏向进行选题&#xff1a; 用例&#xff1a;SAP B1 的数据库工具&am…...

【手术显微镜】市场高度集中,由于高端手术显微镜的制造技术主要掌握于欧美企业

摘要 HengCe (恒策咨询&#xff09;是全球知名的大型咨询机构&#xff0c;长期专注于各行业细分市场的调研。行业层面&#xff0c;重点关注可能存在“卡脖子”的高科技细分领域。企业层面&#xff0c;重点关注在国际和国内市场在规模和技术等层面具有代表性的企业&#xff0c;…...

IDEA 2024 配置Maven

Step 1:确定下载Apache Maven版本 在IDEA 2024中&#xff0c;随便新建一个Maven项目&#xff1b; 在File下拉菜单栏中&#xff0c;找到Setings&#xff1b; 在Build&#xff0c;Execution&#xff0c;Deployment中找到Maven 确定下载的Apache Maven版本应略低于或等于IDEA绑…...

Admin.NET框架使用宝塔面板部署步骤

文章目录 Admin.NET框架使用宝塔面板部署步骤&#x1f381;框架介绍部署步骤1.Centos7 部署宝塔面板2.部署Admin.NET后端3.部署前端Web4.访问前端页面 Admin.NET框架使用宝塔面板部署步骤 &#x1f381;框架介绍 Admin.NET 是基于 .NET6 (Furion/SqlSugar) 实现的通用权限开发…...

Flutter中的Future和Stream

在 Flutter 中&#xff0c;Future 和 Stream 都是用于处理异步操作的类&#xff0c;它们都基于 Dart 的异步编程模型&#xff0c;但是它们的使用场景和工作方式有所不同。以下是它们的区别以及各自适用的场景。 目录 一、Future1、基本使用2、异常处理1. catchError2. onError…...

107.【C语言】数据结构之二叉树求总节点和第K层节点的个数

目录 1.求二叉树总的节点的个数 1.容易想到的方法 代码 缺陷 思考:能否在TreeSize函数内定义静态变量解决size的问题呢? 其他写法 运行结果 2.最好的方法:分而治之 代码 运行结果 2.求二叉树第K层节点的个数 错误代码 运行结果 修正 运行结果 其他写法 1.求二…...

spring boot支持那些开发工具?

Spring Boot 支持多种开发工具&#xff0c;以帮助开发者更高效地进行应用开发。以下是小编给大家分享几种常用的开发工具及其特点&#xff1a; IntelliJ IDEA&#xff1a; IntelliJ IDEA 是一款非常流行的 Java IDE&#xff0c;它提供了对 Spring Boot 的全面支持&#xff0c;…...

Go-MediatR:Go语言中的中介者模式

在Go语言中&#xff0c;确实存在一个与C#中的MediatR类似的组件包&#xff0c;名为Go-MediatR。 Go-MediatR是一个受.NET中MediatR库启发的Go语言实现&#xff0c;它专注于通过中介者模式简化命令查询责任分离&#xff08;CQRS&#xff09;模式的处理和在事件驱动架构中的应用…...

5.11【机器学习】

先是对图像进行划分 划分完后&#xff0c; 顺序读取文件夹&#xff0c;在文件夹里顺序读取图片&#xff0c; 卷积层又称为滤波器&#xff0c;通道是说滤波器的个数&#xff0c;黑白通道数为1&#xff0c;RGB通道个数为3 在输入层&#xff0c;对于输入层而言&#xff0c;滤波…...

在 CentOS 上安装 Docker:构建容器化环境全攻略

一、引言 在当今的软件开发与运维领域&#xff0c;Docker 无疑是一颗璀璨的明星。它以轻量级虚拟化的卓越特性&#xff0c;为应用程序的打包、分发和管理开辟了崭新的高效便捷之路。无论是开发环境的快速搭建&#xff0c;还是生产环境的稳定部署&#xff0c;Docker 都展现出了…...

Python练习(2)

重复元素判定续。利用集合的无重复性来编写一个程序如果有一个元素出现了不止一次则返回true但不要改变原来列表的值&#xff1a; 一&#xff1a; def has_duplicates(lst): # 使用集合来存储已经见过的元素 seen set() for item in lst: if item in seen: # 如果元素已经在…...

如何实现一套键盘鼠标控制两台计算机(罗技Options+ Flow功能快速实现演示)

需求背景 之前我写过一篇文章如何实现一套键盘鼠标控制两台计算机&#xff08;Mouse Without Borders快速上手教程&#xff09;_一套键鼠控制两台电脑-CSDN博客 当我们在局域网内有两台计算机&#xff0c;想使用一套键鼠操控时&#xff0c;可以安装Mouse Without Borders软件…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

使用LangGraph和LangSmith构建多智能体人工智能系统

现在&#xff0c;通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战&#xff0c;比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

虚拟电厂发展三大趋势:市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...