LeetCode热题100(25.10.14)

一：前K个高频元素

1. 堆

可以使用哈希表将元素出现的次数记录下来，然后对出现次数排序，复杂度为$O(n\log(n))$。但题目要求优于$O(n\log(n))$，需要使用其他方案。这里的时间主要花在了排序上，可以使用堆或快排来对元素进行不完全排序，从而降低时间复杂度。该方法使用最小堆将出现次数小的元素放在栈顶

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> result;
        result.reserve(k);
        int len = nums.size();
        unordered_map<int, int> occour;
        occour.reserve(len);
        for (auto& num : nums) ++occour[num];
        auto commpare = [](const pair<int, int>& a, const pair<int, int>& b){return a.second > b.second;};
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(commpare)> pq(commpare);
        for (auto& [num, count] : occour)
        {
            if (pq.size() < k) pq.emplace(num, count);
            else if (pq.top().second < count) 
            {
                pq.pop();
                pq.emplace(num, count);
            }
        }
        while (!pq.empty())
        {
            result.emplace_back(pq.top().first);
            pq.pop();
        }
        return result;
    }
};

2. 基于快速排序

其核心思想在于快排的一次循环过后能够将数据按照选定的某个值分为≥和≤两部分，通过比较左右长度便可判断前k最大值所在位置

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> result;
        result.reserve(k);
        int len = nums.size();
        unordered_map<int, int> occour;
        occour.reserve(len);
        for (auto& num : nums) ++occour[num];
        vector<pair<int, int>> values;
        for (auto& value : occour) values.emplace_back(value);
        QuickChoose(values, k, 0, values.size() - 1, result);
        return result;
    }
    void QuickChoose(vector<pair<int, int>>& values, int k, int left, int right, vector<int>& result)
    {
        if (left > right) return;
        if (left == right) {                 // 基本情形
            result.push_back(values[left].first);
            return;
        }
        int picked = rand() % (right - left + 1) + left;
        swap(values[picked], values[left]);
        int pivot = values[left].second;
        int i = left - 1;
        int j = right + 1;
        while (i < j)
        {
            do ++i; while (values[i].second > pivot);
            do --j; while (values[j].second < pivot);
            if (i < j) swap(values[i], values[j]);
        }
        int leftCount = j - left + 1;  
        if (k <= leftCount) QuickChoose(values, k, left, j, result);
        else 
        {
            for (int i = left; i <= j; ++i)
                result.emplace_back(values[i].first);
            QuickChoose(values, k - leftCount, j + 1, right, result);
        }
    }
};

二：跳跃游戏

1. 贪心

假设当前位于x，那么x+nums[x]范围内的元素都是可达的，因此我们只需要维护一个最大的可达范围即可，如果该范围能够覆盖终点，则意味着终点可达

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        int maxSkip = 0;
        for (int i = 0; i < len; ++i)
        {
            if ( i <= maxSkip) maxSkip = max(maxSkip, i + nums[i]);
            if (maxSkip >= len - 1) return true;
        }
        return false;
    }
};

三：跳跃游戏Ⅱ

1. 反向查找出发位置

我们从最后一个点出发，先找出最后一步到达终点的前面所有点，取最远位置，然后循环直到出发点即可。为什么可行？我们假设终点为n - 1，其最远距离为x，那么x~n - 1区间内的所有位置都是可达的，假设区间中存在一个点的第二步的上一个位置为y，那么y~该点的距离一定包含x，所以x的第二步一定大于等于y，所以求解出来的步数最优

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size() - 1;
        int cur = len;
        int step = 0;
        while (cur > 0)
        {
            for (int i = 0; i <= cur; ++i)
            {
                if (i + nums[i] >= cur)
                {
                    cur = i;
                    ++step;
                    break;
                }
            }
        }
        return step;
    }
};

2. 正向查找可到达的最大位置

这里假设第一步的距离为x，由题意知一定会到达终点，那么第二步应该选择0~x之间能够跳出最远的位置，理论和上一个方法相同，最远位置一定包含其中的点，步骤只会小于等于其他元素

class Solution {
public:
    int jump(vector<int>& nums) {
        int len = nums.size() - 1;
        int step = 0, maxStep = 0, end = 0;
        for (int i = 0; i < len; ++i)
        {
            if (i <= maxStep)
                maxStep = max(maxStep, i + nums[i]);
            if (i == end)
            {
                end = maxStep;
                ++step;
            }
        }
        return step;
    }
};