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

LeetCode 2342. 数位和相等数对的最大和:哈希表

【LetMeFly】2342.数位和相等数对的最大和:哈希表

力扣题目链接:https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/

给你一个下标从 0 开始的数组 nums ,数组中的元素都是 整数。请你选出两个下标 iji != j),且 nums[i] 的数位和 与  nums[j] 的数位和相等。

请你找出所有满足条件的下标 ij ,找出并返回 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.数位和相等数对的最大和&#xff1a;哈希表 力扣题目链接&#xff1a;https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/ 给你一个下标从 0 开始的数组 nums &#xff0c;数组中的元素都是 正 整数。请你选出两个下标 i 和 j&…...

Vulkan渲染引擎开发教程 一、开发环境搭建

一 安装 Vulkan SDK Vulkan SDK 就是我们要搞的图形接口 首先到官网下载SDK并安装 https://vulkan.lunarg.com/sdk/home 二 安装 GLFW 窗口库 GLFW是个跨平台的小型窗口库&#xff0c;也就是显示窗口&#xff0c;图形的载体 去主页下载并安装&#xff0c;https://www.glfw.…...

(带教程)商业版SEO关键词按天计费系统:关键词排名优化、代理服务、手机自适应及搭建教程

源码简介&#xff1a; 1、会员管理&#xff1a; 该系统分为三个级别的会员流程&#xff1a;总站管理员、代理与会员&#xff08;会员有普通会员、中级会员和高级会员三个等级&#xff09;。总站管理员可以添加代理用户并为其充值余额&#xff0c;代理用户可以为普通用户充值余…...

IDEA 快捷键汇总

目录 1、altinsert 2、ctrl/ 3、altenter 4、alt回车 5、ctrlD 6、ctrlaltL 7、ctrl点击 8、alt左键向下拉 9、ctrlaltv 10、ctrlaltwint 1、altinsert 快速创建代码&#xff0c;可以快速创建类中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分&#xff0c;共40分。在每小题给出的四个备选项中&#xff0c;选出一个正确的答案&#xff0c;并将所选项前的字母填写在答题纸的相应位置上。) C 风格的注释&#xff0c;也称块注释或多行注释&#xff0c;以&#xff08;&#xff09;…...

导航守卫有哪三种?

导航守卫主要分为三种&#xff1a; 全局前置守卫&#xff1a;使用 router.beforeEach 注册&#xff0c;作用是在路由切换开始前进行拦截和处理&#xff0c;可以用来进行一些全局的权限校验、登录状态检查等操作。 全局解析守卫&#xff1a;使用 beforeResolve 注册&#xff0c…...

强烈 推荐 13 个 Web前端在线代码IDE

codesandbox.io&#xff08;国外&#xff0c;提供免费空间&#xff09; 网址&#xff1a;https://codesandbox.io/ CodeSandbox 专注于构建完整的 Web 应用程序&#xff0c;支持多种流行的前端框架和库&#xff0c;例如 React、Vue 和 Angular。它提供了一系列增强的功能&…...

网络协议 WebSocket

一、介绍 WebSocket 是基于 TCP 的一种新的网络协议。它实现了浏览器与服务器全双工通信——浏览器和服务器只需要完成一次握手&#xff0c;两者之间就可以创建持久性的连接&#xff0c; 并进行双向数据传输 1、HTTP协议和WebSocket协议对比 HTTP 是短连接WebSocket 是长连接H…...

路径操作 合法路径名

python中路径的三种合法表示&#xff1a;在路径前面加上r、分隔符使用/。 在路径前面加上r python中在前面加上r&#xff0c;是防止字符转义。 例如&#xff1a;这样一个路径&#xff1a; \Undergraduate\School\Programme\Python_Learnpython会将这个字符串的**\和\后面的…...

JavaEE初阶 01 计算机是如何工作的

前言 今天开始进行对JavaEE的一些基本总结,希望大家能在阅读中有所收获,如有错误还望多多指正. 1.冯诺依曼体系结构 这个体系结构相信学计算机的同学都不陌生,但是你真的知道这个体系结构说的是什么嘛?请听我娓娓道来.首先我先给出一张冯诺依曼体系结构的简图 你可以理解为当前…...

【shell 常用脚本30例】

先了解下编写Shell过程中注意事项 开头加解释器&#xff1a;#!/bin/bash语法缩进&#xff0c;使用四个空格&#xff1b;多加注释说明。命名建议规则&#xff1a;全局变量名大写、局部变量小写&#xff0c;函数名小写&#xff0c;名字体现出实际作用。默认变量是全局的&#xf…...

【我和Python算法的初相遇】——体验递归的可视化篇

&#x1f308;个人主页: Aileen_0v0 &#x1f525;系列专栏:PYTHON数据结构与算法学习系列专栏&#x1f4ab;"没有罗马,那就自己创造罗马~" 目录 递归的起源 什么是递归? 利用递归解决列表求和问题 递归三定律 递归应用-整数转换为任意进制数 递归可视化 画…...

【C语言的秘密】密探—深究C语言中多组输入的秘密!

场景引入&#xff1a; 你是否在刷题过程中&#xff0c;经常遇到以下场景呢&#xff1f; 场景一&#xff1a; 场景二&#xff1a; 从这些题上都能看见输入描述中提出了一条多组输入&#xff0c;那啥是多组输入&#xff1f;如何实现它呢&#xff1f; 多组输入&#xff1a;在输入…...

ClickHouse 语法优化规则

ClickHouse 的 SQL 优化规则是基于RBO(Rule Based Optimization)&#xff0c;下面是一些优化规则 1 准备测试用表 1&#xff09;上传官方的数据集 将visits_v1.tar和hits_v1.tar上传到虚拟机&#xff0c;解压到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&#xff08;FANWEI e-Weaver&#xff09;是一款广泛应用于企业数字化转型领域的集成协同管理平台。作为中国知名的企业级软件解决方案提供商&#xff0c;泛微软件&#xff08;广州&#xff09;股份有限公司开发和推广了e-Weaver平台。 泛微e-Weaver旨在…...

「git 系列」git 如何存储代码的?

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

IDEA 集成 Docker 插件一键部署 SpringBoot 应用

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

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

MMaDA: Multimodal Large Diffusion Language Models

CODE &#xff1a; https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA&#xff0c;它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构&#xf…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

c#开发AI模型对话

AI模型 前面已经介绍了一般AI模型本地部署&#xff0c;直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型&#xff0c;但是目前国内可能使用不多&#xff0c;至少实践例子很少看见。开发训练模型就不介绍了&am…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...