当前位置: 首页 > 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软件…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

Python竞赛环境搭建全攻略

Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型&#xff08;算法、数据分析、机器学习等&#xff09;不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...

PH热榜 | 2025-06-08

1. Thiings 标语&#xff1a;一套超过1900个免费AI生成的3D图标集合 介绍&#xff1a;Thiings是一个不断扩展的免费AI生成3D图标库&#xff0c;目前已有超过1900个图标。你可以按照主题浏览&#xff0c;生成自己的图标&#xff0c;或者下载整个图标集。所有图标都可以在个人或…...

深入浅出WebGL:在浏览器中解锁3D世界的魔法钥匙

WebGL&#xff1a;在浏览器中解锁3D世界的魔法钥匙 引言&#xff1a;网页的边界正在消失 在数字化浪潮的推动下&#xff0c;网页早已不再是静态信息的展示窗口。如今&#xff0c;我们可以在浏览器中体验逼真的3D游戏、交互式数据可视化、虚拟实验室&#xff0c;甚至沉浸式的V…...