爱 做 网站吗,网站建设 创新,河北路泰建设工程有限公司网站,网站建设 工作建议文章目录 2342. 数位和相等数对的最大和方案1方案2方案3方案4 2342. 数位和相等数对的最大和
2342. 数位和相等数对的最大和
代码仓库地址#xff1a; https://github.com/slience-me/Leetcode 个人博客 #xff1a;https://slienceme.xyz
给你一个下标从 0 开始的数组 nu… 文章目录 2342. 数位和相等数对的最大和方案1方案2方案3方案4 2342. 数位和相等数对的最大和
2342. 数位和相等数对的最大和
代码仓库地址 https://github.com/slience-me/Leetcode 个人博客 https://slienceme.xyz
给你一个下标从 0 开始的数组 nums 数组中的元素都是 正 整数。请你选出两个下标 i 和 ji ! 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
方案1
class Solution {
public:int maximumSum(vectorint nums) {vectorint sumVector; // 创建一个空的整数向量记录数位和int maxNum -1;for (const auto item: nums) {int num getSumOfNum(item);sumVector.push_back(num);}for(int i0; isumVector.size(); i){for(int ji1; jsumVector.size(); j){if(sumVector[i] sumVector[j]){if(nums[i]nums[j]maxNum){maxNum nums[i]nums[j];}}}}return maxNum;}int getSumOfNum(int num) {int sum 0; // 12345while (num ! 0) {sum (num % 10);num / 10;}return sum;}
};超出时间限制 方案2 在给定的代码中您的目标是找到满足数位和相等的两个数的和的最大值。目前的方法是使用两层嵌套的循环来检查所有数对并找到它们的数位和相等的情况下的最大和。 有一些地方可以进行优化来提高算法的效率 使用哈希表存储数位和的索引 可以使用哈希表unordered_map存储数位和及其对应的索引这样可以在一次遍历中找到符合条件的数对。. 不需要构建额外的向量存储数位和 在遍历原始数组时直接计算数位和并在哈希表中查找而不需要额外的向量来存储数位和。 class Solution {
public:int maximumSum(vectorint nums) {unordered_mapint, vectorint sumIndexMap;int maxSum -1;for (int num : nums) {int sum getSumOfNum(num);sumIndexMap[sum].push_back(num);}for (auto pair : sumIndexMap) {if (pair.second.size() 2) {sort(pair.second.rbegin(), pair.second.rend());maxSum max(maxSum, pair.second[0] pair.second[1]);}}return maxSum;}int getSumOfNum(int num) {if (num 0) {return -1;}int sum 0; // 12345while (num ! 0) {sum (num % 10);num / 10;}return sum;}
};执行用时分布 208ms 击败16.01%使用 C 的用户 消耗内存分布 65.10MB 击败19.74%使用 C 的用户 方案3 单次循环解决问题不再多一步排序 class Solution {
public:int maximumSum(vectorint nums) {unordered_mapint, int sumIndexMap; //存储数位和对应索引int maxSum -1; // 最大值// 先全部放入哈希表for (int num: nums) {int sum getSumOfNum(num);if (sumIndexMap.count(sum)) {maxSum max(maxSum, sumIndexMap[sum] num);sumIndexMap[sum] max(sumIndexMap[sum], num);} else {sumIndexMap[sum] num;}}return maxSum;}int getSumOfNum(int num) {if (num 0) {return -1;}int sum 0; // 12345while (num ! 0) {sum (num % 10);num / 10;}return sum;}
};执行用时分布 144ms 击败66.89%使用 C 的用户 消耗内存分布 57.78MB 击败39.91%使用 C 的用户 方案4 纯属组解决问题 class Solution {
public:int maximumSum(vectorint nums) {int maxArray[120]{0}; //先给够int maxSum -1; // 最大值// 先全部放入哈希表for (int num: nums) {int sum getSumOfNum(num);if (maxArray[sum]) {maxSum max(maxSum, maxArray[sum] num);maxArray[sum] max(maxArray[sum], num);} else {maxArray[sum] num;}}return maxSum;}int getSumOfNum(int num) {if (num 0) {return -1;}int sum 0; // 12345while (num ! 0) {sum (num % 10);num / 10;}return sum;}
};执行用时分布 208ms 击败16.01%使用 C 的用户 消耗内存分布 65.10MB 击败19.74%使用 C 的用户
