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

【算法-哈希表2】快乐数 和 两数之和

今天,带来哈希表相关算法的讲解。文中不足错漏之处望请斧正!

理论基础点这里


1. 快乐数

分析题意

出题者已经把题意明确告诉我们了:

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

题意转化

怎么理解?

如果我们替换平方和的过程中, 发现当前的数字之前已经出现过, 那我们就陷入了无限循环.

如果没有把题意转化过来, 就会手足无措了.

解决思路

那我们只需要不断重复替换平方和的过程, 再同时判断平方和之前是否出现过:

  • 没出现过: 继续重复替换
  • 出现过: 陷入无限循环, 结束

编程实现

取每位上的数

关于取十进制数上的每位, 可以再谈谈.

如, 要取1234中的每位数.

1234 % 10 = 4 //取到最后一位
1234 /= 10; //去掉最后一位
123  % 10 = 3 //取到倒数第二位
123 /= 10; //去掉最后一位
12 % 10 = 4 //取到倒数第三位
12 /= 10; //去掉最后一位
1 % 10 = 4 //取到倒数第四位
1 /= 10; //去掉最后一位
//最终1234变为0,结束

如果是二进制, 八进制, 只需要mod8即可.

class Solution {
public:// 可能替换的过程可能一直循环:// 如果当前得到的数之前已经得到过, 则会无限循环; 反之不会bool isHappy(int n) {unordered_set<int> appearedNum;while (n != 1) {int sum = getSqureSum(n);// 只要当前的数之前没出现过, 就代表可能这个数能变到1if (appearedNum.find(sum) == appearedNum.end()) {appearedNum.insert(sum);} else { // 反之不可能变到1return false;}n = sum;}return true;}
private:int getSqureSum(int n) {int sum = 0;while (n) {sum += pow(n % 10, 2);n /= 10;}return sum;}
};

2. 两数之和

分析题意

*很好理解, 无需分析.

题意转化

找到 x 和 y, 满足 x + y = target.

解决思路

一层遍历获取 x, 查找nums内是否有这样的 y 满足 y = target - x.

关于查找:

  • for暴力查找 – O(n)
  • 哈希快速查找 – O(1)

查找某个元素在某个集合中是否用过, 这是哈希的绝活; 而且题目要求返回下标. 综合这两点, 我们用 unordered_map, 存储键值对的哈希表.

编程实现

class Solution {
public:// 找到 x 和 y, 满足 x + y = targetvector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numsMap; // <value, index>// 一层遍历获取 x, 查找nums内是否有这样的 y 满足 y = target - xfor (int i = 0; i < nums.size(); ++i) {int x = nums[i];int y = target - x;auto iter = numsMap.find(y);if (iter != numsMap.end()) {int i1 = i;int i2 = iter->first;return {i, iter->second};} else {numsMap.insert(pair<int, int>(nums[i], i));}}return {};}
};

今天的分享就到这里了,感谢您能看到这里。

这里是培根的blog,期待与你共同进步!

相关文章:

【算法-哈希表2】快乐数 和 两数之和

今天&#xff0c;带来哈希表相关算法的讲解。文中不足错漏之处望请斧正&#xff01; 理论基础点这里 1. 快乐数 分析题意 出题者已经把题意明确告诉我们了: 对于一个正整数&#xff0c;每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1&am…...

MR外包团队:MR、XR混合现实技术应用于游戏、培训,心理咨询、教育成为一种创新的各行业MR、XR形式!

随着VR、AR、XR、MR混合现实等技术逐渐应用于游戏开发、心理咨询、培训、教育各个领域&#xff0c;为教育、培训、心理咨询等行业带来了全新的可能性。MR、XR游戏开发、心理咨询是利用虚拟现实技术模拟真实场景&#xff0c;让学生身临其境地参与学习和体验&#xff0c;从而提高…...

【P1008 [NOIP1998 普及组] 三连击】

[NOIP1998 普及组] 三连击 题目背景 本题为提交答案题&#xff0c;您可以写程序或手算在本机上算出答案后&#xff0c;直接提交答案文本&#xff0c;也可提交答案生成程序。 题目描述 将 1 , 2 , … , 9 1, 2, \ldots , 9 1,2,…,9 共 9 9 9 个数分成 3 3 3 组&#xff…...

机器学习算法——集成学习

目录 1. Bagging 1. Bagging Bagging&#xff08;bootstrap aggregating&#xff1a;自举汇聚法&#xff09;也叫装袋法&#xff0c;其思想是通过将许多相互独立的学习器的结果进行结合&#xff0c;从而提高整体学习器的泛化能力&#xff0c;是一种并行集成学习方法。 工作流…...

java springboot在当前测试类中添加临时属性 不影响application和其他范围

目前 我们的属性基本都写在 application.yml 里面了 但是 如果 我们只是想做一下临时变量的测试 有没有办法实现呢&#xff1f; 显然是有的 这里 我们还是先在application.yml中去写一个 test属性 下面加个prop 然后 我们尝试在测试类中 获取一下这个属性 直接用 Value 读取…...

原型网络Prototypical Network的python代码逐行解释,新手小白也可学会!!由于工作量大,准备整8个系列完事,-----系列5

文章目录 前言一、原始程序---计算原型&#xff0c;开始训练&#xff0c;计算损失二、每一行代码的详细解释2.1 粗略分析2.2 每一行代码详细分析 前言 承接系列4&#xff0c;此部分属于原型类中的计算原型&#xff0c;开始训练&#xff0c;计算损失函数。 一、原始程序—计算原…...

milvus数据库的数据管理-插入数据

一、插入数据 1.准备数据 数据必须与数据库中定义的字段元数据一致&#xff0c;与集合的模式匹配 import random data [[i for i in range(2000)],[str(i) for i in range(2000)],[i for i in range(10000, 12000)],[[random.random() for _ in range(2)] for _ in range(2…...

系列一、请谈谈你对JVM的理解?Java8的虚拟机有什么更新?

一、请谈谈你对JVM的理解&#xff1f;Java8的虚拟机有什么更新&#xff1f; JVM是Java虚拟机的意思。它是建立在操作系统之上的&#xff0c;由类加载器子系统、本地方法栈、Java栈、程序计数器、方法区、堆、本地方法库、本地方法接口、执行引擎组成。 &#xff08;1&#xff0…...

恕我直言,大模型对齐可能无法解决安全问题,我们都被表象误导了

是否听说过“伪对齐”这一概念&#xff1f; 在大型语言模型&#xff08;LLM&#xff09;的评估中&#xff0c;研究者发现了一个引人注目的现象&#xff1a;当面对多项选择题和开放式问题时&#xff0c;模型的表现存在显著差异。这一差异根源在于模型对复杂概念的理解不够全面&…...

Apache Airflow (九) :Airflow Operators及案例之BashOperator及调度Shell命令及脚本

&#x1f3e1; 个人主页&#xff1a;IT贫道_大数据OLAP体系技术栈,Apache Doris,Clickhouse 技术-CSDN博客 &#x1f6a9; 私聊博主&#xff1a;加入大数据技术讨论群聊&#xff0c;获取更多大数据资料。 &#x1f514; 博主个人B栈地址&#xff1a;豹哥教你大数据的个人空间-豹…...

IJ中配置TortoiseSVN插件:

文章目录 一、报错情况&#xff1a;二、配置TortoiseSVN插件&#xff1a; 一、报错情况&#xff1a; 由于公司电脑加密&#xff0c;TortoiseSVN菜单没有提交和更新按钮&#xff0c;所以需要使用IJ的SVN进行代码相关操作 二、配置TortoiseSVN插件&#xff1a; 需要设置一个svn.…...

个人实现在线支付,一种另类的在线支付解决方案

Hi, I’m Shendi 个人实现在线支付&#xff0c;一种另类的在线支付解决方案 个人实现在线支付的方式 对于在线支付&#xff0c;最多的是接入微信与支付宝。但都需要营业执照&#xff0c;不适用于个人。 当然&#xff0c;可以去办理一个个体工商户&#xff0c;但对我这种小额收…...

浅谈智能安全配电装置应用在银行配电系统中

【摘要】银行是国家重点安全保护部分&#xff0c;关系到社会资金的稳定&#xff0c;也是消防重点单位。消防安全是银行工作的重要组成部分。在银行配电系统中应用智能安全配电装置&#xff0c;可以提高银行的智能控制水平&#xff0c;有效预防电气火灾。 【关键词】银行&#…...

macOS下如何使用Flask进行开发

&#x1f468;&#x1f3fb;‍&#x1f4bb; 热爱摄影的程序员 &#x1f468;&#x1f3fb;‍&#x1f3a8; 喜欢编码的设计师 &#x1f9d5;&#x1f3fb; 擅长设计的剪辑师 &#x1f9d1;&#x1f3fb;‍&#x1f3eb; 一位高冷无情的编码爱好者 大家好&#xff0c;我是全栈工…...

记一次服务器配置文件获取OSS

一、漏洞原因 由于网站登录口未做双因子校验,导致可以通过暴力破解获取管理员账号,成功进入系统;未对上传的格式和内容进行校验,可以任意文件上传获取服务器权限;由于服务器上配置信息,可以进一步获取数据库权限和OSS管理权限。二、漏洞成果 弱口令获取网站的管理员权限通…...

合众汽车选用风河Wind River Linux系统

导读合众新能源汽车股份有限公司近日选择了Wind River Linux 用于开发合众智能安全汽车平台。 合众智能安全汽车平台(Hozon Automo-tive Intelligent Security Vehicle Plat-form)是一个面向高性能服务网关及车辆控制调度的硬件与软件框架&#xff0c;将于2024年中开始投入量产…...

PTA平台-2023年软件设计综合实践_5(指针及引用)

第一题 6-1 调和平均 - C/C 指针及引用 函数hmean()用于计算整数x和y的调和平均数&#xff0c;结果应保存在指针r所指向的浮点数对象中。当xy等于0时&#xff0c;函数返回0表示无法计算&#xff0c;否则返回1。数学上&#xff0c;两个数x和y的调和平均数 z 2xy/(xy) 。 直接…...

智慧卫生间

智慧卫生间 获取ApiKey/SecretKey获取Access_token获取卫生间实时数据返回说明 获取ApiKey/SecretKey ApiKey/SecretKey采用 线下获取的方式&#xff0c;手动分配。 获取Access_token 向授权服务地址http://xxxxxx:12345/token(示意)发送post请求&#xff0c;并在data中带上…...

Cadence virtuoso drc lvs pex 无法输入

问题描述&#xff1a;在PEX中的PEX options中 Ground node name 无法输入内容。 在save runset的时候也出现无法输入名称的情况 解决办法&#xff1a; copy一个.bashrc文件到自己的工作目录下 打开.bashrc文件 在.bashrc中加一行代码&#xff1a;unset XMODIFIERS 在终端sour…...

反序列化漏洞(2), 分析调用链, 编写POC

反序列化漏洞(2), 反序列化调用链分析 一, 编写php漏洞脚本 http://192.168.112.200/security/unserial/ustest.php <?php class Tiger{public $string;protected $var;public function __toString(){return $this->string;}public function boss($value){eval($valu…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Leetcode33( 搜索旋转排序数组)

题目表述 整数数组 nums 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...

阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)

cd /home 进入home盘 安装虚拟环境&#xff1a; 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境&#xff1a; virtualenv myenv 3、激活虚拟环境&#xff08;激活环境可以在当前环境下安装包&#xff09; source myenv/bin/activate 此时&#xff0c;终端…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...

DAY 45 超大力王爱学Python

来自超大力王的友情提示&#xff1a;在用tensordoard的时候一定一定要用绝对位置&#xff0c;例如&#xff1a;tensorboard --logdir"D:\代码\archive (1)\runs\cifar10_mlp_experiment_2" 不然读取不了数据 知识点回顾&#xff1a; tensorboard的发展历史和原理tens…...