最大堆，DP问题-LeetCode 373 374 376 377 605（DP，最大堆）
最大堆，DP问题-LeetCode 373 374 376 377 605（DP，最大堆）
1
编程题
【LeetCode #373】查找和最小的K对数字
给定两个以升序排列的整形数组 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]
解题思路：
版本一：将所有可能的两位数全都列出存入一个vector中，然后进行排序，排序的规则为：两数之和，越小的越靠前！ 版本二：使用PriorityQueue建立大根堆，排序规则与版本一相同，当堆中元素大于k时，判断堆顶元素与待插入元素大小，如果待插入元素小，则将该元素放入堆中，并且移除堆顶元素，这是为了保证堆中元素个数 <= k。这样由于事先判断，因此相比版本一效率会高很多！
（版本一：Vector+Sort版本）
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
vector<vector<int>> res;
vector<pair<int, int>> tmp;
if(k == ) return res;
auto fun = [](pair<int, int>a, pair<int, int>b){
return (a.first+b.first) < (a.second+b.second);
};
for(auto i: nums1){
for(auto j: nums2){
tmp.push_back(make_pair(i, j));
}
}
sort(tmp.begin(), tmp.end(), fun);
int n = min(k, (int)tmp.size());
int i = ;
while(i < n){
res.push_back({tmp[i].first, tmp[i].second});
i++;
}
return res;
}
};
（版本二：PriorityQueue，速度更快，内存占用更少）
class Solution {
public:
vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
auto cmp = [](pair<int, int>& a, pair<int, int>& b){
return a.first+a.second < b.first+b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que(cmp);
// decltype是为了获取lambda表达式的类型名称
vector<vector<int>> res;
for(auto i: nums1){
for(auto j: nums2){
if(que.size() < k){
que.push({i, j});
}else if(i+j < que.top().first+que.top().second){
que.pop();
que.push({i, j});
}
}
}
while(!que.empty()){
auto tmp = que.top();
res.push_back({tmp.first, tmp.second});
que.pop();
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums
【LeetCode #374】猜数字大小
我们正在玩一个猜数字游戏。游戏规则如下： 我从 1 到 n 选择一个数字。你需要猜我选择了哪个数字。 每次你猜错了，我会告诉你这个数字是大了还是小了。 你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：
-1 : 我的数字比较小 1 : 我的数字比较大 0 : 恭喜！你猜对了！
示例 : 输入: n = 10, pick = 6 输出: 6
解题思路：直接二分就好了！
int guess(int num);
class Solution {
public:
int guessNumber(int n) {
int l = , r= n;
int res = ;
while(l <= r){
int mid = l+(r-l)/;
int tmp = guess(mid);
if(tmp == ){
res = mid;
break;
}else if(tmp < ){
r = mid - ;
}else{
l = mid + ;
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower
【LeetCode #376】摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。 例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。 给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。
解题思路：
贪心算法，如果nums[i] > nums[i-1]，表示一个向上增长，即up = down + 1。假设之前的是一个下降趋势的序列长度！反之，则down = up + 1。最后返回两者最大的就好了！
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if(n < ) return n;
int up = ;
int down = ;
for(int i = ; i < n; i++){
if(nums[i] > nums[i-1]){
up = down + ;
}
if(nums[i] < nums[i-1]){
down = up + ;
}
}
return max(up, down);
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/wiggle-subsequence
【LeetCode #377】组合问题IV
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例: nums = [1, 2, 3] target = 4
解题思路：
主要是递推式，推导如下 比如nums = [1, 2, 3] dp[4] = dp[3]+dp[2]+dp[1], 也就是说，4的组合数为三个部分组成，1和dp[3], 2和dp[2], 以及3和dp[1]。其中dp[0] = 1.
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
if(nums.empty()) return ;
vector<unsigned long long> dp(target+, );
dp[] = ;
for(int i = ; i <= target; i++){
for(auto j: nums){
if(i >= j){
dp[i] += dp[i-j];
}
}
}
return dp[target];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/combination-sum-iv/
【LeetCode #605】种花问题
假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。
给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
示例 1: 输入: flowerbed = [1,0,0,0,1], n = 1 输出: True
解题思路：
每三个零之间种一枝花，但是存在左右边界问题，比如i=0或者i=len时，只需要两个连续的零就可以种一枝花了！因此需要特殊处理！
class Solution {
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = , i = ;
int len = flowerbed.size() - ;
while(i <= len){
if(flowerbed[i] ==
&& (i == || flowerbed[i-1] == )
&& (i == len || flowerbed[i+] == )){
flowerbed[i] = ;
count++; // 每三个零中间中一个，注意左右边界
}
i++;
}
return count >= n;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/can-place-flowers
腾讯云开发者
