LeetCode 2342. 数位和相等数对的最大和:哈希表
【LetMeFly】2342.数位和相等数对的最大和:哈希表
力扣题目链接:https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/
给你一个下标从 0 开始的数组 nums
,数组中的元素都是 正 整数。请你选出两个下标 i
和 j
(i != j
),且 nums[i]
的数位和 与 nums[j]
的数位和相等。
请你找出所有满足条件的下标 i
和 j
,找出并返回 nums[i] + nums[j]
可以得到的 最大值 。
示例 1:
输入:nums = [18,43,36,13,7] 输出:54 解释:满足条件的数对 (i, j) 为: - (0, 2) ,两个数字的数位和都是 9 ,相加得到 18 + 36 = 54 。 - (1, 4) ,两个数字的数位和都是 7 ,相加得到 43 + 7 = 50 。 所以可以获得的最大和是 54 。
示例 2:
输入:nums = [10,12,19,14] 输出:-1 解释:不存在满足条件的数对,返回 -1 。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 109
方法一:哈希表
我们只需要建立一个哈希表,维护哈希表中“和为 k e y key key的最大的两个数”即可。
具体怎么做呢?
遍历数组中的元素 t t t,如果 t t t的和在哈希表中,那么就保留“哈希表中”和“ t t t”中较大的两个元素。
这里有一个小技巧:可以保持哈希表中的两个元素的相对顺序为第一个元素不小于第二个元素,这样替换时只需要比较 t t t和哈希表对应元素的第二个元素即可。
- 时间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
- 空间复杂度 O ( l e n ( n u m s ) ) O(len(nums)) O(len(nums))
AC代码
C++
inline int getSum(int n) {int ans = 0;while (n) {ans += n % 10;n /= 10;}return ans;
}class Solution {
public:int maximumSum(vector<int>& nums) {unordered_map<int, pair<int, int>> ma;int ans = -1;for (int t : nums) {int s = getSum(t);if (t > ma[s].second) {ma[s].second = t;}if (ma[s].first < ma[s].second) {swap(ma[s].first, ma[s].second);}if (ma[s].second) {ans = max(ans, ma[s].first + ma[s].second);}}return ans;}
};
Python
class Solution:def getSum(self, n: int) -> int:ans = 0while n:ans += n % 10n //= 10return ansdef maximumSum(self, nums: List[int]) -> int:ans = -1ma = dict()for t in nums:s = self.getSum(t)if s in ma:if t > ma[s][1]:ma[s][1] = tif ma[s][0] < ma[s][1]:ma[s][0], ma[s][1] = ma[s][1], ma[s][0]ans = max(ans, sum(ma[s]))else:ma[s] = [t, 0]return ans
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134476645
相关文章:
LeetCode 2342. 数位和相等数对的最大和:哈希表
【LetMeFly】2342.数位和相等数对的最大和:哈希表 力扣题目链接:https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/ 给你一个下标从 0 开始的数组 nums ,数组中的元素都是 正 整数。请你选出两个下标 i 和 j&…...

Vulkan渲染引擎开发教程 一、开发环境搭建
一 安装 Vulkan SDK Vulkan SDK 就是我们要搞的图形接口 首先到官网下载SDK并安装 https://vulkan.lunarg.com/sdk/home 二 安装 GLFW 窗口库 GLFW是个跨平台的小型窗口库,也就是显示窗口,图形的载体 去主页下载并安装,https://www.glfw.…...

(带教程)商业版SEO关键词按天计费系统:关键词排名优化、代理服务、手机自适应及搭建教程
源码简介: 1、会员管理: 该系统分为三个级别的会员流程:总站管理员、代理与会员(会员有普通会员、中级会员和高级会员三个等级)。总站管理员可以添加代理用户并为其充值余额,代理用户可以为普通用户充值余…...

IDEA 快捷键汇总
目录 1、altinsert 2、ctrl/ 3、altenter 4、alt回车 5、ctrlD 6、ctrlaltL 7、ctrl点击 8、alt左键向下拉 9、ctrlaltv 10、ctrlaltwint 1、altinsert 快速创建代码,可以快速创建类中get set tostring等方法 2、ctrl/ 单行注释 3、altenter…...
目标检测YOLO实战应用案例100讲-基于机器视觉的水稻病虫害监测预警
目录 前言 国内外研究现状 国外研究现状 国内研究现状 2 相关理论与技术...
OrthoNets:正交信道注意网络
文章目录 摘要1、简介2、相关工作3、方法4、实验设置及结果5、论述6、结论摘要 链接:https://arxiv.org/pdf/2311.03071v2.pdf 设计有效的通道注意力机制要求人们找到一种有损压缩方法,以实现最佳特征表示。尽管该领域近年来取得了进展,但仍然存在一个未解决的问题。FcaNet…...

C_12练习题
一、单项选择题(本大题共20小题,每小题2分,共40分。在每小题给出的四个备选项中,选出一个正确的答案,并将所选项前的字母填写在答题纸的相应位置上。) C 风格的注释,也称块注释或多行注释,以()…...
导航守卫有哪三种?
导航守卫主要分为三种: 全局前置守卫:使用 router.beforeEach 注册,作用是在路由切换开始前进行拦截和处理,可以用来进行一些全局的权限校验、登录状态检查等操作。 全局解析守卫:使用 beforeResolve 注册,…...

强烈 推荐 13 个 Web前端在线代码IDE
codesandbox.io(国外,提供免费空间) 网址:https://codesandbox.io/ CodeSandbox 专注于构建完整的 Web 应用程序,支持多种流行的前端框架和库,例如 React、Vue 和 Angular。它提供了一系列增强的功能&…...
网络协议 WebSocket
一、介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手,两者之间就可以创建持久性的连接, 并进行双向数据传输 1、HTTP协议和WebSocket协议对比 HTTP 是短连接WebSocket 是长连接H…...
路径操作 合法路径名
python中路径的三种合法表示:在路径前面加上r、分隔符使用/。 在路径前面加上r python中在前面加上r,是防止字符转义。 例如:这样一个路径: \Undergraduate\School\Programme\Python_Learnpython会将这个字符串的**\和\后面的…...

JavaEE初阶 01 计算机是如何工作的
前言 今天开始进行对JavaEE的一些基本总结,希望大家能在阅读中有所收获,如有错误还望多多指正. 1.冯诺依曼体系结构 这个体系结构相信学计算机的同学都不陌生,但是你真的知道这个体系结构说的是什么嘛?请听我娓娓道来.首先我先给出一张冯诺依曼体系结构的简图 你可以理解为当前…...
【shell 常用脚本30例】
先了解下编写Shell过程中注意事项 开头加解释器:#!/bin/bash语法缩进,使用四个空格;多加注释说明。命名建议规则:全局变量名大写、局部变量小写,函数名小写,名字体现出实际作用。默认变量是全局的…...

【我和Python算法的初相遇】——体验递归的可视化篇
🌈个人主页: Aileen_0v0 🔥系列专栏:PYTHON数据结构与算法学习系列专栏💫"没有罗马,那就自己创造罗马~" 目录 递归的起源 什么是递归? 利用递归解决列表求和问题 递归三定律 递归应用-整数转换为任意进制数 递归可视化 画…...

【C语言的秘密】密探—深究C语言中多组输入的秘密!
场景引入: 你是否在刷题过程中,经常遇到以下场景呢? 场景一: 场景二: 从这些题上都能看见输入描述中提出了一条多组输入,那啥是多组输入?如何实现它呢? 多组输入:在输入…...
ClickHouse 语法优化规则
ClickHouse 的 SQL 优化规则是基于RBO(Rule Based Optimization),下面是一些优化规则 1 准备测试用表 1)上传官方的数据集 将visits_v1.tar和hits_v1.tar上传到虚拟机,解压到clickhouse数据路径下 // 解压到clickhouse数据路径 sudo tar -xvf…...
3-运行第一个docker image-hello world
CentOS7.9下安装完成docker后,我们开始部署第一个docker image-hello world 1.以root用户登录CentOS7.9服务器,拉取centos7 images 命令: docker pull hello-world [root@centos79 ~]# docker pull hello-world Using default tag: latest latest: Pulling from library…...

【漏洞复现】泛微e-Weaver SQL注入
漏洞描述 泛微e-Weaver(FANWEI e-Weaver)是一款广泛应用于企业数字化转型领域的集成协同管理平台。作为中国知名的企业级软件解决方案提供商,泛微软件(广州)股份有限公司开发和推广了e-Weaver平台。 泛微e-Weaver旨在…...

「git 系列」git 如何存储代码的?
这里写自定义目录标题 git 文件存储位置git 数据模型示例分析分析前准备命令哈希值 具体示例 不同版本的提交,git 做了什么工作?snapshot vs delta-based vs backup参考资料 git 文件存储位置 想要了解如何存储,首先需要知道存储位置。 当我…...

IDEA 集成 Docker 插件一键部署 SpringBoot 应用
目录 前言IDEA 安装 Docker 插件配置 Docker 远程服务器编写 DockerFileSpringBoot 部署配置SpringBoot 项目部署结语 前言 随着容器化技术的崛起,Docker成为了现代软件开发的关键工具。在Java开发中,Spring Boot是一款备受青睐的框架,然而&…...

网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型
CVPR 2025 | MIMO:支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题:MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者:Yanyuan Chen, Dexuan Xu, Yu Hu…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了: 这一篇我们开始讲: 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下: 一、场景操作步骤 操作步…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...

有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...