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

Hash table类算法【leetcode】

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

那么哈希表能解决什么问题呢,一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n),但如果使用哈希表的话, 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里,在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ,也就是哈希函数

242.有效的字母异位词

题目:给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。力扣题目链接

思路:定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上,因为字符a到字符z的ASCII是26个连续的数值,所以字符a映射为下标0,相应的字符z映射为下标25。

再遍历 字符串s的时候,只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可,并不需要记住字符a的ASCII,只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数,统计出来了。

那看一下如何检查字符串t中是否出现了这些字符,同样在遍历字符串t的时候,对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下,record数组如果有的元素不为零0,说明字符串s和t一定是谁多了字符或者谁少了字符,return false。

最后如果record数组所有元素都为零0,说明字符串s和t是字母异位词,return true。

时间复杂度为O(n),空间上因为定义是的一个常量大小的辅助数组,所以空间复杂度为O(1)。

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

349. 两个数组的交集

题目:给定两个数组,编写一个函数来计算它们的交集。力扣题目链接

思路:注意题目特意说明:输出结果中的每个元素一定是唯一的,也就是说输出的结果的去重的, 同时可以不考虑输出结果的顺序

std::set和std::multiset底层实现都是红黑树,std::unordered_set的底层实现是哈希表, 使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};

 unordered_set<int> nums_set(nums1.begin(), nums1.end()); 解释:

 这行代码将 nums1 中的所有元素插入到 nums_set 中。nums1.begin()nums1.end() 分别是 nums1 向量的起始迭代器和结束迭代器,表示整个 nums1 向量的范围。

 for (int num : nums2) 解释:

是 C++ 中的一种范围基于的循环(range-based for loop)语法。这种语法用于遍历容器或数组中的每个元素,而无需显式地使用迭代器或索引。它使代码更加简洁和易读。

具体来说,for (int num : nums2) 的含义是:

  • int num:声明一个变量 num,其类型为 int。在每次循环迭代中,num 会依次取 nums2 中的每个元素的值。
  • nums2:要遍历的容器或数组。在这个例子中,nums2 是一个 std::vector<int> 类型的向量。

因此,for (int num : nums2) 的完整意思是:对于 nums2 中的每个元素,将该元素的值赋给 num,然后执行循环体内的代码。

在 C++ 中,unordered_set(以及 setmap 等关联容器)提供了一个成员函数 find,用于查找容器中是否存在某个特定的键。find 函数的返回值是一个迭代器,指向找到的元素;如果未找到该元素,则返回一个特殊的迭代器,通常称为“结束迭代器”(end iterator),即 end()。 

第202题. 快乐数

题目:

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

  • 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1,那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ;不是,则返回 false 。

思路:题目中说了会 无限循环,那么也就是说求和的过程中,sum会重复出现,这对解题很重要!【对哈希表的算法我也不大会,只能说是多积累吧】

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

相关文章:

Hash table类算法【leetcode】

哈希表中关键码就是数组的索引下标&#xff0c;然后通过下标直接访问数组中的元素 那么哈希表能解决什么问题呢&#xff0c;一般哈希表都是用来快速判断一个元素是否出现集合里。 例如要查询一个名字是否在这所学校里。 要枚举的话时间复杂度是O(n)&#xff0c;但如果使用哈希…...

windows实现VNC连接ubuntu22.04服务器

最近弄了一个700块钱的mini主机&#xff0c;刷了ubuntu22.04系统&#xff0c;然后想要在笔记本上通过VNC连接&#xff0c;这样就有了一个linux的开发环境。最后实现的过程为&#xff1a; 安装vnc服务器 安装 VNC 服务器软件&#xff1a; sudo apt update sudo apt install t…...

中国电信星辰大模型:软件工厂与文生视频技术的深度解析

在科技日新月异的今天,人工智能(AI)技术正以惊人的速度改变着我们的生活和工作方式。作为这一领域的领军企业之一,中国电信凭借其强大的研发实力和深厚的技术积累,推出了星辰大模型,旨在为用户带来更加智能、高效、便捷的服务体验。本文将重点介绍中国电信星辰大模型中的…...

项目实战:基于Vue3实现一个小相册

相册的示例效果图 注意看注释... 要实现图片的相册效果&#xff0c;图片命名可以像{img1.jpg,img2.jpg,img3.jpg}类似于这种的命名方式。 CSS部分&#xff1a; <style>/* 伪元素选择器&#xff0c;用于在具有clear_ele类的元素内部的末尾添加一个新的元素 */.clear_ele:…...

macOS安装nvm node

macOS安装nvm macOS安装nvm创建 nvm 工作目录配置环境变量使用 nvm查看可用的 Node.js 版本安装特定版本 macOS安装nvm brew install nvm创建 nvm 工作目录 mkdir ~/.nvm配置环境变量 vim ~/.zshrc# nvm export NVM_DIR"$HOME/.nvm" [ -s "/opt/homebrew/opt…...

解决整合Django与Jinja2兼容性的问题

提问 解决整合Django与Jinja2时遇到了一些兼容性问题。已经按照常规步骤在我的settings.py中配置了Jinja2作为模板引擎&#xff0c;同时保留了Django默认的模板设置。然而尝试同时使用Django和Jinja2时&#xff0c;系统报错提示我没有指定模板。如果我尝试移除Django的默认模板…...

Elasticsearch面试内容整理-高级特性

Elasticsearch 提供了一系列高级特性,这些特性可以极大地增强其搜索、分析和管理能力,使得它在大数据场景中表现出色。以下是 Elasticsearch 的一些重要高级特性: 近实时搜索(Near Real-Time Search) Elasticsearch 的一个关键特性是 近实时搜索(NRT),这意味着数据写入…...

linux通过手工删除文件卸载oracle 11g rac的具体步骤

在linux操作系统中&#xff0c;有些时候我们自己学习和测试会临时搭建的oracle rac。事情完成后&#xff0c;我们想回收资源&#xff0c;需要去卸载oracle rac。为了快速卸载oracle rac&#xff0c;今天我们介绍下如何通过手工删除文件的方式来完成工作&#xff08;操作都需要在…...

【ArcGISPro】根据yaml构建原始Pro的conda环境

使用场景 我们不小心把原始arcgispro-py3的conda环境破坏了,我们就可以使用以下方法进行修复 查找文件 在arcgis目录下找到yaml文件 如果没找到请复制以下内容到新的yaml文件 channels: - esri - defaults dependencies: - anyio=4.2.0=py311haa95532_0 - appdirs=1.4.4=p…...

刷题笔记15

问题描述 小M和小F在玩飞行棋。游戏结束后&#xff0c;他们需要将桌上的飞行棋棋子分组整理好。现在有 N 个棋子&#xff0c;每个棋子上有一个数字序号。小M的目标是将这些棋子分成 M 组&#xff0c;每组恰好5个&#xff0c;并且组内棋子的序号相同。小M希望知道是否可以按照这…...

【LeetCode热题100】队列+宽搜

这篇博客是关于队列宽搜的几道题&#xff0c;主要包括N叉树的层序遍历、二叉树的锯齿形层序遍历、二叉树最大宽度、在每个数行中找最大值。 class Solution { public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ret;if(!root) …...

【阵列信号处理】相干信号和非相干信号生成

文章目录 一、总结二、知识点相干&#xff08;coherent&#xff09;和非相干&#xff08;incoherent&#xff09;信号相干信号生成代码 相关信号&#xff08;correlated signal&#xff09;相关信号生成代码 正交信号定义 本文记录博主的科研日记。如果对博主的其他文章感兴趣&…...

React 组件生命周期

React 组件生命周期 React 组件生命周期是React框架中一个核心概念,它描述了一个组件从创建到销毁的过程。理解组件生命周期对于高效开发React应用至关重要,因为它允许开发者在一个组件的不同阶段执行特定的逻辑。本文将详细介绍React组件的生命周期方法,并解释它们在组件的…...

Kylin Server V10 下基于Sentinel(哨兵)实现Redis高可用集群

一、什么是哨兵模式 Redis Sentinel 是一个分布式系统,为 Redis 提供高可用性解决方案。可以在一个架构中运行多个 Sentinel 进程(progress)这些进程使用流言协议(gossip protocols)来接收关于主服务器是否下线信息,并使用投票协议(agreement protocols)来决定是否执行…...

07-Making a Bar Chart with D3.js and SVG

课程链接 Curran的课程&#xff0c;通过 D3.js 的 scaleLinear, max, scaleBand, axisLeft, axisBottom&#xff0c;根据 .csv 文件生成一个横向柱状图。 【注】如果想造csv数据&#xff0c;可以使用通义千问&#xff0c;关于LinearScale与BandScale不懂的地方也可以在通义千…...

硅谷甄选前端项目环境配置笔记

此教程来自于尚硅谷 文章目录 **此教程来自于尚硅谷**硅谷甄选运营平台一、搭建后台管理系统模板1.1项目初始化1.1.1环境准备1.1.2初始化项目 1.2项目配置一、eslint配置1.1vue3环境代码校验插件1.2修改.eslintrc.cjs配置文件1.3.eslintignore忽略文件1.4运行脚本 二、配置**pr…...

6.7机器学习期末复习题

空间 样本空间 就是属性的所有可能情况&#xff0c;包括了一切可能出现或不可能出现的所有样本情况 版本空间&假设空间 假设空间就是在样本空间的基础上&#xff0c;给所有属性都加了一个通配符&#xff0c;表示任意即可&#xff1b;以及加上了一个空集&#xff0c;表示…...

1123--日期类

目录 一 java 1. Date类 2. calendar类 3. 第三代日期类‘ 3.1 常用方法 3.2 格式化操作 一 java 1. Date类 2. calendar类 3. 第三代日期类‘ 3.1 常用方法 3.2 格式化操作...

YOLOV5 /onnx模型转换成rknn

上两篇文章讲述了pytorch模型下best.pt转换成onnx模型&#xff0c;以及将onnx进行简化成为best-sim.onnx, 接下来这篇文章讲述如何将onnx模型转换成rknn模型&#xff0c;转换成该模型是为了在rk3568上运行 1.创建share文件夹 文件夹包含以下文件best-sim.onnx,rknn-tookit2-…...

Echarts+VUE饼图的使用(基础使用、多个饼图功能、单组饼图对应颜色使用)

安装&#xff1a;npm install echarts --save 配置:main.js // 引入echarts import * as echarts from echarts Vue.prototype.$echarts echarts一、基础饼图&#xff08;直接拷贝就能出效果&#xff09; <div class"big-box" ref"demoEhart"><…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Java 语言特性(面试系列1)

一、面向对象编程 1. 封装&#xff08;Encapsulation&#xff09; 定义&#xff1a;将数据&#xff08;属性&#xff09;和操作数据的方法绑定在一起&#xff0c;通过访问控制符&#xff08;private、protected、public&#xff09;隐藏内部实现细节。示例&#xff1a; public …...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...

MyBatis中关于缓存的理解

MyBatis缓存 MyBatis系统当中默认定义两级缓存&#xff1a;一级缓存、二级缓存 默认情况下&#xff0c;只有一级缓存开启&#xff08;sqlSession级别的缓存&#xff09;二级缓存需要手动开启配置&#xff0c;需要局域namespace级别的缓存 一级缓存&#xff08;本地缓存&#…...