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

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

React hook之useRef

React useRef 详解 useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 基本概念 1. 创建 ref const refContainer useRef(initialValue);initialValu…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

算术操作符与类型转换:从基础到精通

目录 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 算术操作符超级详解 算术操作符&#xff1a;、-、*、/、% 赋值操作符&#xff1a;和复合赋值 单⽬操作符&#xff1a;、--、、- 前言&#xff1a;从基础到实践——探索运算符与类型转换的奥秘 在先前的文…...