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 <= 1051 <= 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是一款备受青睐的框架,然而&…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
