最大堆，DP问题-LeetCode 373 374 376 377 605（DP，最大堆）

• 2019 年 12 月 13 日
• 筆記

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