【学习笔记】一些LeetCode的题目的题解

【学习笔记】一些LeetCode的题目的题解

panedioic
2022-10-01 / 0 评论 / 2 阅读 / 正在检测是否收录...

前言

与一些其他的oj不同,leetcode主要是一个面向与面试的oj,因此,其题目设计以及写代码的方式也都有着一些独特之处。
因为我刷题主要用的是C++,因此就必须对C++的语法有着足够的了解。所以在这里放一些我做过的题的题解,就用来当做未来再刷题时可参考的模板了。

题目

LeetCode 786. 第 K 个最小的素数分数

题目

给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr1 和若干 素数  组成,且其中所有整数互不相同。

对于每对满足 0 <= i < j < arr.lengthij ,可以得到分数 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

评论 (0)

取消