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

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...