您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【leetcode游记】竞赛题 1877

数组中最大数对和的最小值。

这道题,老实说光看懂我就看了很久。论刷题的重要性。

总结为:排序题

题目链接:
https://leetcode-cn.com/problems/minimize-maximum-pair-sum-in-array/

数对和,就是两个数相加。
两个数相加的值要最小。

在这个条件下划分数对,然后返回最小的最大数对和。

老实说我一开始被绕晕了。
什么最小的最大数对和。

看到最优划分,我就以为是动态规划之类的,想想我还不大会动态规划,算了这题肯定不会做。而且还是medium,肯定是动规。

结果朋友在边儿上刚好闲着看看我这在干嘛。然后说,排个序,把最大的总是和最小的结合,那出来的数对的最大的相加不就是最小的吗。

我觉得,很有道理。最大的总是和最小的在一起,那相加和可不就是最小的吗。

试试呗。

然后就开始写。

写出来了,如下:
(这是本地调试版本)

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;



class Solution {
public:
    int minPairSum(vector<int>& nums) {
        //找出最优数对划分
        sort(nums.begin(),nums.end());
        int max=0;
        int temp=0;
        for(int i=0;i<nums.size()/2;i++){
            temp=nums[i]+nums[nums.size()-1-i];
            if (temp>max) max=temp;
        }

        //求和 取最大值
        return max;
    }
};



int main() {
    Solution s;
    vector<int> v={3,5,2,3};
    cout<<s.minPairSum(v);
    return 0;
}

ok。总结。

逻辑上,有问题。
细节上,一点点要注意。
实现上,有点儿问题。

逻辑上:
题目理解不到位,看到最优被吓到。其实就是排序,涉及到这种相加的,排序本身就是一种最优化的过程,看到最优怎么能忘了排序呢。
排序好了之后直接最大的加最小的,循环到一半。

细节上:
最大的数加上最小的数,就是第一个加上最后一个,注意nums[i]+nums[nums.size()-1-i] 要减1。有时候这些小细节就是挺蛋疼的。

实现上:
这里用到了vector,vector是个啥。就是个不定长的数组。逻辑上就是数组。特别好的就是可以用sort(.begin(), .end()),不用自己写排序算法。

over.


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进