题目

给定两个以升序排列的整数数组 nums1 和 nums2, 以及一个整数 k。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。

请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

提示:

1 <= nums1.length, nums2.length <= 104
-109 <= nums1[i], nums2[i] <= 109
nums1, nums2 均为升序排列

1 <= k <= 1000

思路

抄的题解的思路
使用最大堆来对已经保存的数据对排序。
最大堆保存两者的值之和，在两个数组中对应的下标。
首先将一个数组A的第一个和另一个数组B的全部进行组合，记录下数组A、B的下标（这里对于数组A都是0），第一个最小的对一定在这两个之间。
之后每取出一个对（i，j），就以数组B的下标j为不变，数组A的下标后移一个加入到当前的优先队列中。
每次新增的数组，下标一定与其中某一个已有下标，一定为之和相差1的关系
因此每次选一个，加一个，能够把所有情况都考虑到。

代码

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        if(k>nums1.size()*nums2.size()) k = nums1.size()*nums2.size();
        if(!nums2.size()||!nums1.size()) return {};
        priority_queue<pair<int,pair<int,int>>> h;
        for(int i=0;i<nums1.size();++i) h.push({-nums1[i]-nums2[0],{i,0}});
        vector<vector<int>> res;
        while(res.size()<k){
            auto t = h.top();
            h.pop();
            int i = t.second.first,j=t.second.second;
            res.push_back({nums1[i],nums2[j++]});
            if(j<nums2.size()) h.push({-nums1[i]-nums2[j],{i,j}});
        }
        return res;
    }
};

2021-09-08发表2021-09-08更新算法 / 动态规划4 分钟读完 (大约576个字)

502.IPO

题目

假设力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣希望在 IPO 之前开展一些项目以增加其资本。由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助力扣设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释： 由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

1 <= k <= 105
0 <= w <= 109
n == profits.length
n == capital.length
1 <= n <= 105
0 <= profits[i] <= 104
0 <= capital[i] <= 109
思路

银行家算法*
将capital和profits配对，并按照captial从小到大进行排序。
每次对比w和capitali，如果w比capitali大，则将对应的profitsi加入到优先队列中。
全部加完后，从优先队列中选择最大的profits加到w中。
重复上述k次。

代码

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int,int>> arr(n);
        priority_queue<int,vector<int>,less<int>> pq;
        for(int i=0;i<n;++i){ arr[i] = {capital[i],profits[i]}; }
        int idx = 0;
        sort(arr.begin(),arr.end());
        for(int i=0;i<k;++i){
            while(idx<n&&arr[idx].first<=w){
                pq.push(arr[idx++].second);
            }
            if(!pq.empty()){
                w+=pq.top();
                pq.pop();
            }else{
                break;
            }
        }
        return w;
    }
}

373.查找和最小的K对数字

题目

思路

代码

502.IPO

题目

思路

代码

链接

分类

最新文章

归档

标签