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