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

  • 相关阅读:
    基于Java web的论坛BBS系统设计与实现
    电子表格软件怎么选？
    JMeter的基本使用
    俄罗斯方块c语言
    “企业级零代码黑客马拉松”决赛圆满落幕
    PG-PFC-17E、PG-PEV-16A、PG-PEV-18A插装式比例流量阀控制器
    Java复制文件和目录
    WPF 上位机 Modbus 入门必备的信息 C# 开发对接
    使用TS 封装 自定义hooks，实现不一样的 CRUD
    1023 组个最小数
  • 原文地址：https://blog.csdn.net/AA5279AA/article/details/134505438