码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • ​LeetCode解法汇总2342. 数位和相等数对的最大和


    目录链接:

    力扣编程题-解法汇总_分享+记录-CSDN博客

    GitHub同步刷题项目:

    https://github.com/September26/java-algorithms

    原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台


    描述:

    给你一个下标从 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 <= 10^5
    • 1 <= nums[i] <= 10^9

    解题思路:

    这道题的数组长度范围是10^5,所以时间复杂度应该是O(N)到O(N*lgN的级别。这道题,是根据数位和来确定唯一的,所以最合适的方式是使用哈希表的解题思路。

    这题的核心其实是找到数位和一样,并且累加值最大的那两个数。所以我们首先设置mMaxValue记录最大的两个数之和。因为我们只需要记录最大的那两个数,所以没有必要使用List记录所有的,因此使用NumModel记录数位和相同的所有数的状态,其实也就是只记录最大的两个,value1对应当前数组和最大的那个,value2对应次大的。

    遍历的过程中,如果发现当前数组和所对应的数大于最大值,则更新value1,value2,value。

    如果当前数组和所对应的数大于次大值,则更新value2和value。

    最后返回maxValue即可。

    代码:

    1. public class Solution2342 {
    2. int mMaxValue = -1;
    3. public int maximumSum(int[] nums) {
    4. Map<Integer, NumModel> map = new HashMap<>();
    5. for (int num : nums) {
    6. int key = getKey(num);
    7. NumModel numModel = map.get(key);
    8. if (numModel == null) {
    9. numModel = new NumModel();
    10. numModel.key = key;
    11. numModel.value1 = num;
    12. map.put(key, numModel);
    13. } else {
    14. insertModel(numModel, num);
    15. }
    16. }
    17. return mMaxValue;
    18. }
    19. private void insertModel(NumModel numModel, int num) {
    20. if (num > numModel.value1) {
    21. numModel.value2 = numModel.value1;
    22. numModel.value1 = num;
    23. numModel.value = numModel.value2 + numModel.value1;
    24. mMaxValue = Math.max(mMaxValue, numModel.value);
    25. return;
    26. }
    27. if (num > numModel.value2) {
    28. numModel.value2 = num;
    29. numModel.value = numModel.value2 + numModel.value1;
    30. mMaxValue = Math.max(mMaxValue, numModel.value);
    31. }
    32. }
    33. private int getKey(int num) {
    34. int sum = 0;
    35. while (num > 0) {
    36. sum += num % 10;
    37. num /= 10;
    38. }
    39. return sum;
    40. }
    41. static class NumModel {
    42. int key = 0;
    43. int value1 = 0;
    44. int value2 = 0;
    45. int value = 0;
    46. }
    47. }

  • 相关阅读:
    BSN解构元宇宙产业结构(一)- VR设备和数字资产
    全电注塑机硬件选型
    LeetCode_Array_1004. Max Consecutive Ones III 最大连续1的个数 III【滑动数组】【Java】【中等】
    利用根升余弦滤波器和整数倍内插的多相结构生成含采样频偏的过采样信号
    HTML+CSS+JavaScript七夕情人节表白网页【樱花雨3D相册】超好看
    Asp .Net Core 系列:集成 Consul 实现 服务注册与健康检查
    ffmpeg之去除视频水印
    前端TypeScript学习day01-TS介绍与TS常用类型
    挑战杯 基于机器学习与大数据的糖尿病预测
    pytorch中的归一化函数
  • 原文地址:https://blog.csdn.net/AA5279AA/article/details/134505438
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号