讨论/题目交流/🏆 第 180 场力扣周赛/
🏆 第 180 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 矩阵中的幸运数
4 分 - 设计一个支持增量操作的栈
4 分 - 将二叉搜索树变平衡
6 分 - 最大的团队表现值

展开讨论

矩阵中的幸运数

思路

  1. 模拟

答题

vector<int> luckyNumbers(vector<vector<int>>& matrix)
{
    for (int i = 0; i < matrix.size(); i++)
    {
        int mnj = 0;
        for (int j = 1; j < matrix[i].size(); j++)
        {
            if (matrix[i][j] > matrix[i][mnj]) continue;
            mnj = j;
        }
        int mxi = 0;
        for (int i = 1; i < matrix.size(); i++)
        {
            if (matrix[i][mnj] < matrix[mxi][mnj]) continue;
            mxi = i;
        }
        if (mxi == i) return { matrix[mxi][mnj] };
    }
    return {};
}

设计一个支持增量操作的栈

思路

  1. 就跟普通栈几乎没区别吧

答题

class CustomStack {
public:
    CustomStack(int maxSize) : m_maxSize(maxSize) {

    }
    
    void push(int x) {
        if (m_data.size() == m_maxSize) return;
        m_data.push_back(x);
    }
    
    int pop() {
        if (m_data.empty()) return -1;
        int n = m_data.back();
        m_data.pop_back();
        return n;
    }
    
    void increment(int k, int val) {
        for (int i = 0; i < k && i < m_data.size(); i++)
        {
            m_data[i] += val;
        }
    }
private:
    vector<int> m_data;
    int m_maxSize;
};

将二叉搜索树变平衡

思路

  1. 中序遍历得到有序数组 94. 二叉树的中序遍历
  2. 将有序数组转化为平衡二叉树 108. 将有序数组转换为二叉搜索树

答题

TreeNode* sortedArrayToBSTHelper(vector<int>& nums, int start, int end) 
{
    if (start > end) return nullptr;

    TreeNode* root = nullptr;
    int mid = start + (end - start) / 2;
    root = new TreeNode(nums[mid]);
    root->left = sortedArrayToBSTHelper(nums, start, mid - 1);
    root->right = sortedArrayToBSTHelper(nums, mid + 1, end);
    return root;
}

void inorderTraversal(TreeNode* root, vector<int>& nums)
{
    if (root == nullptr) return;
    inorderTraversal(root->left, nums);
    nums.push_back(root->val);
    inorderTraversal(root->right, nums);
}

TreeNode* balanceBST(TreeNode* root)
{
    vector<int> nums;
    inorderTraversal(root, nums);
    TreeNode* node = sortedArrayToBSTHelper(nums, 0, nums.size() - 1);
    return node;
}

最大的团队表现值

思路

  1. speedefficiency 同步排序,按照效率降序
  2. 遍历,对每一项数据
    21. 累加和 sum ,当超过 k 个的数据时,选最小的将其排除
    22. 使用优先队列来找到 k 个中最小的数据
    23. 效率的最低值就是当前项的效率
    24. 计算结果,注意这里不能取余
  3. 返回最终结果时取余

答题

int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) 
{
    const int mod = 1000000007;

    vector<vector<int>> es;
    for (int i = 0; i < efficiency.size(); i++)
    {
        es.push_back({ efficiency[i], speed[i] });
    }
    sort(es.rbegin(), es.rend());

    long long ans = 0;
    long long sum = 0;
    long long eff = INT_MAX;
    priority_queue<int, vector<int>, greater<int>> que;
    for (int i = 0; i < es.size(); i++)
    {
        eff = es[i][0];
        sum += es[i][1];
        que.push(es[i][1]);
        if (--k < 0)
        {
            sum -= que.top();
            que.pop();
        }
        ans = max(ans, sum * eff);
    }
    return ans % mod;
}

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

我的leetcode

4
展开全部 31 讨论