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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2020-03-15
共 31 个讨论

半个小时做完前两题 然后就开始摸鱼

14

矩阵中的幸运数

思路

  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

最后一道题被取模误导了, 太坑爹了. 还好最后机智地发现了它就是想误导我, 然后顺利做出来了, 哈哈.

最后一题做法:
由于要每次乘以效率最小的, 因此我们可以按照每个人效率进行升序排序. 排序之后你可以发现, 第i个人后面的人效率都比它大, 所以如果选k个人(包括i的话), 那么就是它后面人里挑k-1个speed最大的,不用再管efficient了. 怎么挑k-1个最大的呢? 小顶堆啊! capacity限制为k. 同时维护一个堆的total值避免每次去计算. 所以就是先对efficient排序, 然后倒序枚举, 同时维护堆. 数据范围一你算发现int64存得下, 狗日的, 害得我写了半天高精度...

最终:

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
    pub fn max_performance(n: i32, speed: Vec<i32>, efficiency: Vec<i32>, k: i32) -> i32 {
        const M: i64 = 1000000007;
        // Vec<(效率, 速度)>
        let mut tuple: Vec<(i32, i32)> = efficiency.into_iter().zip(speed).map(|t| t).collect();
        tuple.sort_by(|a,b| {
            if a.0 == b.0 { // 按efficient排序, 相同的则按speed排序
                return a.1.cmp(&b.1);
            }
            a.0.cmp(&b.0)
        });
        let uk = k as usize;
        let mut heap = BinaryHeap::new();
        let mut total = 0;
        let n = n as usize;
        let mut ans = 0;
        for i in (n-uk..n).rev() { // 枚举最后k个, 因为题目是最多k, 可以小于k
            heap.push(Reverse(tuple[i].1 as i64));
            total += tuple[i].1 as i64;
            ans = ans.max(tuple[i].0 as i64 * total);
        }
        for i in (0..n-uk).rev() {
            let peek = heap.peek().unwrap_or(&Reverse(0)).0; // 取堆顶值, 也就是k个数中的最小值
            let maybe_new_total = total+tuple[i].1 as i64-peek; // 由于要把当前这个人选中, 而又要选k个人, 因此就需要把堆中speed最小那个人排除,加上当前这个人的speed
            let cur = tuple[i].0 as i64 * maybe_new_total;
            ans = ans.max(cur);
            if tuple[i].1 as i64 > peek { // 如果当前人的speed大于堆的最小值, 那么就更新堆
                heap.pop();
                heap.push(Reverse(tuple[i].1 as i64));
                total = maybe_new_total;
            }
        }
        (ans % M) as i32
    }
}
4

周赛题解报告

5356. 矩阵中的幸运数

题目类型:暴力枚举
枚举每个元素,然后检查是否符合幸运数的要求。

class Solution { 
    public:
        vector<int> luckyNumbers (vector<vector<int>>& matrix) {
            vector<int> res; 
            for(int i = 0, n = matrix.size(); i < n; i++) { 
                for(int j = 0, m = matrix[i].size(); j < m; j++) {
                    bool flag = true;
                    for(int k = 0; flag && k < m; k++) {
                        if(k == j) { continue; }
                        if(matrix[i][j] > matrix[i][k]) { flag = false;}
                    }
                    for(int k = 0; flag && k < n; k++) {
                        if(k == i) { continue; }
                        if(matrix[i][j] < matrix[k][j]) { flag = false;}
                    }
                    if (flag) {
                        res.push_back(matrix[i][j]);
                    }
                }
            }
            return res;
        } 
};

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

题目类型:模拟,栈
使用 size 变量记录栈的容量,使用 top 变量记录栈顶位置。
坑点:进行 increment 操作时,栈内的元素可能不足 k 个。

const int MAXN = 1000;

class CustomStack {
	int data[MAXN];
	int size;
	int top;
	public:
		CustomStack(int maxSize): size(maxSize), top(0) {}

		void push(int x) {
			if (top < size) {
				data[top++] = x;
			}
		}

		int pop() {
			if(top > 0) {
				return data[--top];
			}
			return -1;
		}

		void increment(int k, int val) {
			for(int i = 0, n = min(k, top); i < n; i++) {
				data[i] += val;
			}
		}
};

5179. 将二叉搜索树变平衡

题目类型:树的遍历,递归,构造
先遍历给出的二叉搜索树,按照中序遍历的顺序将树中元素保存下来。

根据升序数组构造平衡二叉搜索树:

  1. 如果数组为空,则对应的树亦为空。
  2. 如果数组不为空,设长度为 n,那么位置n2\frac{n}{2}处的元素应为根节点。子数组 [1,n21][1, \frac{n}{2}-1][n2+1,n][\frac{n}{2}+1, n] 分别对应左右子树。因为两个子数组的长度相差不会超过 1,所以保证了左右子树的高度相差不会超过 1。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
    void dfs(TreeNode *root, vector<int> &vec) {
        if(root == nullptr) { return; }
        dfs(root->left, vec);
        vec.push_back(root->val);
        dfs(root->right, vec);
    }
    TreeNode* construct(const vector<int> &vec, int L, int R) {
        if(L > R) {
            return nullptr;
        }
        int mid = (L+R)>>1;
        auto ptr = new TreeNode(vec[mid]);
        ptr->right = construct(vec, mid+1, R);
        ptr->left = construct(vec, L, mid-1);
        return ptr;
    }
public:
    TreeNode* balanceBST(TreeNode* root) {
        if(root == nullptr) {
            return nullptr;
        }
        vector<int> data;
        dfs(root, data);
        return construct(data, 0, data.size()-1);
    }
};

5359. 最大的团队表现值

题目类型:快速排序,堆排序,枚举
C++知识点:std::priority_queue,std::greater,运算符重载
坑点:注意在运算过程中数据范围有可能超出 int32。

std::priority_queue 可以参见 http://www.cplusplus.com/reference/queue/priority_queue/
std::greater 可以参见 http://www.cplusplus.com/reference/functional/greater/

思考路书
当两种方案的efficiency相等时,speed之和更大的方案显然更优。
题目的输入决定了最多有 n 种 efficiency。
对于每种 efficiency 肯定都会存在最优的方案。
最终答案肯定就是这个n种方案里面最优的那个。
问题转化成了如何快速求出每种 efficiency 的最优方案:

  • 从大到小枚举efficiency,使用一个数组维护可选的职员。因为efficiency不断减小,所以职员只会被加入这个数组,而绝不会被删除。
  • 在数组种选取 k 个最大的 speed(可使用堆排序维护),使用当前枚举到 efficiency 与 k个最大的speed之和相乘作为当前 efficiency 的最优解。

注意: 选取的 k 个最大speed对应的efficiency可能都大于当前枚举的 efficiency,但是这并不影响最终答案的正确性。因为如果这个选择方案的确为最终答案的话,则其值必然记录在其他 efficiency 的最优解中。
编程技巧:使用 std::priority_queue 代替堆排序代码,提高编码速度。

class Solution {
	struct Engineer {
		int64_t s;
		int64_t e;
		Engineer(int64_t _s, int64_t _e) : s(_s), e(_e) {}
		bool operator < (const Engineer &r) const {
			return this->e > r.e;
		}
	};
	vector<Engineer> data;
	priority_queue<int, vector<int>, greater<int>> pq;
	public:
	int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
		for(int i = 0; i < n; i++) {
			data.push_back(Engineer(speed[i], efficiency[i]));
		}
		sort(data.begin(), data.end());
		int64_t sum = 0, anw = 0;
		for(int i = 0; i < n; i++) {
            sum += data[i].s;
			pq.push(data[i].s);
			if(pq.size() > size_t(k)) {
				int64_t tmp = pq.top();
				pq.pop();
				sum -= tmp;
			}
			anw = max(anw, sum * data[i].e);
		}
		return anw%(1000000007);
	}
};
5

今天题目好像有点简单。

3

一个小时做掉三条题目,然后就开始摸鱼

2

最后一道题,用了dfs,超时,知道考的贪心,但是请问大佬怎么个贪心的思路?

2

第三题没看到搜索二字,白给两次……
第四题没取模,白给两次……
稳稳的掉分QAQ
不过很高兴看到Leetcode在比赛规则里写明了特判所有测试数据属于作弊。

2

有大佬能解释下int *matrixColSize指的是啥吗 我用sizeof()/sizeof()的方法算的 三个例子依次给我 3 2 2
我一直以为是一行有多少个数,现在有点蒙了

1

想问一下那些比赛开始十几分钟就全部做完的大佬,真的是一个人做完的吗--

1