前言
与一些其他的oj不同,leetcode主要是一个面向与面试的oj,因此,其题目设计以及写代码的方式也都有着一些独特之处。
因为我刷题主要用的是C++,因此就必须对C++的语法有着足够的了解。所以在这里放一些我做过的题的题解,就用来当做未来再刷题时可参考的模板了。
题目
LeetCode 786. 第 K 个最小的素数分数
题目
给你一个按递增顺序排序的数组 arr
和一个整数 k
。数组 arr
由 1
和若干 素数
组成,且其中所有整数互不相同。
对于每对满足 0 <= i < j < arr.length
的 i
和 j
,可以得到分数 arr[i] / arr[j]
。
那么第 k 个最小的分数是多少呢? 以长度为 2
的整数数组返回你的答案, 这里 answer[0] == arr[i]
且 answer[1] == arr[j]
。
示例 1:
输入:arr = [1,2,3,5], k = 3
输出:[2,5]
解释:已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5
示例 2:
输入:arr = [1,7], k = 1
输出:[1,7]
分析
这道题的做法有很多。
最简单的一种做法自然就是先把所有可能的排列组合都存到数组里,然后进行排序,再找到符合要求的结果进行输出。就是时间复杂度会有点高。
虽然也有更好的算法,不过这种办法也是在官方题解里的了,而且并没有超时。这里就暂时跳过其他的解法了。
代码
class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
int n = arr.size();
vector<pair<int, int>> frac;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
frac.emplace_back(arr[i], arr[j]);
}
}
sort(frac.begin(), frac.end(), [&](const auto& x, const auto& y) {
return x.first * y.second < x.second * y.first;
});
return {frac[k - 1].first, frac[k - 1].second};
}
};
总结
这道题中组成每个分数的两个素数是密不可分的。因此我们需要一种数据结构把他们关联起来。std库的pair就能比较好的满足我们的需求。但之后需要使用sort进行排序,pair是不好直接排序的,因此我们需要制定排序的方法,而这道题就当做之后可以复制的模板了。
LeetCode 698. 划分为k个相等的子集
题目
给定一个整数数组 nums
和一个正整数 k
,找出是否有可能把这个数组分成 k
个非空子集,其总和都相等。
示例 1:
输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
示例 2:
输入: nums = [1,2,3,4], k = 3
输出: false
分析
这道题我最先想到的是使用了DFS的解法的。但无奈超时了,有想不到其他更好的解法,就只能先去看题解了。
题解是运用了回溯枝剪的解法。基本上还是在分成k个桶之后,在尝试把数字放到各个桶中。如果超出要求就取出来重新放,找不到满足的解就返回False。在查找的时候可以剪枝一部分,以降低整体的复杂度。
题解
class Solution {
public:
bool canPartitionKSubsets(vector<int>& nums, int k) {
int n = nums.size();
int sum = accumulate(nums.begin(), nums.end(), 0);
if(sum % k != 0){
return false;
}
sum /= k;
sort(nums.rbegin(), nums.rend());
vector<int> sec(k, 0);
auto dfs = [&, end = nums.end()](auto&& dfs, auto&& it){
if(it == end){
return true;
}
for(size_t i = 0; i < k; i += 1){
if (sec[i] + *it > sum || (i && sec[i - 1] == sec[i])) continue;
sec[i] += *it;
if (dfs(dfs, it + 1)){
return true;
}
sec[i] -= *it;
}
return false;
};
return nums[0] <= sum && dfs(dfs, nums.cbegin());
}
};
总结
至于这道题我可以得到的收获嘛,一方面是了解了一个回溯枝剪的思想以及可以参考的解题模板。
另一方面,自己也了解了C++中lambda表达式的运用,以后可以借鉴。
但是需要注意的是,题解之中的size_t是个正整形的变量。不可以是负值。我今天就在这里吃了个bug。qwq。
评论 (0)