On the shoulders of giants.

weekly-contest-180

矩阵中的幸运数

给你一个 m * n 的矩阵,矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。

幸运数是指矩阵中满足同时下列两个条件的元素:

  • 在同一行的所有元素中最小
  • 在同一列的所有元素中最大

示例 1:

输入:matrix = [[3,7,8],[9,11,13],[15,16,17]]
输出:[15]
解释:15 是唯一的幸运数,因为它是其所在行中的最小值,也是所在列中的最大值。

示例 2:

输入:matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
输出:[12]
解释:12 是唯一的幸运数,因为它是其所在行中的最小值,也是所在列中的最大值。

示例 3:

输入:matrix = [[7,8],[1,2]]
输出:[7]

提示:

  • m == mat.length
  • n == mat[i].length
  • 1 <= n, m <= 50
  • 1 <= matrix[i][j] <= 10^5
  • 矩阵中的所有元素都是不同的
题解

考虑每一行,找出最小的,然后再看是否在一列中最大,模拟即可。

时间复杂度:\(O(nm)\)

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

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

请你设计一个支持下述操作的栈。

实现自定义栈类 CustomStack

  • CustomStack(int maxSize):用 maxSize 初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize 之后则不支持 push 操作。
  • void push(int x):如果栈还未增长到 maxSize ,就将 x 添加到栈顶。
  • int pop():返回栈顶的值,或栈为空时返回 -1
  • void inc(int k, int val):栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val

示例:

输入:
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
输出:
[null,null,null,2,null,null,null,null,null,103,202,201,-1] 
解释: 
CustomStack customStack = new CustomStack(3); // 栈是空的 [] 
customStack.push(1);                          // 栈变为 [1] 
customStack.push(2);                          // 栈变为 [1, 2] 
customStack.pop();                            // 返回 2 --> 返回栈顶值 2,栈变为 [1] 
customStack.push(2);                          // 栈变为 [1, 2] 
customStack.push(3);                          // 栈变为 [1, 2, 3]
customStack.push(4);                          // 栈仍然是 [1, 2, 3],不能添加其他元素使栈大小变为 4 
customStack.increment(5, 100);                // 栈变为 [101, 102, 103] 
customStack.increment(2, 100);                // 栈变为 [201, 202, 103] 
customStack.pop();                            // 返回 103 --> 返回栈顶值 103,栈变为 [201, 202] 
customStack.pop();                            // 返回 202 --> 返回栈顶值 202,栈变为 [201] 
customStack.pop();                            // 返回 201 --> 返回栈顶值 201,栈变为 [] 
customStack.pop();                            // 返回 -1 --> 栈为空,返回 -1 

提示:

  • 1 <= maxSize <= 1000
  • 1 <= x <= 1000
  • 1 <= k <= 1000
  • 0 <= val <= 100
  • 每种方法 incrementpush 以及 pop 分别最多调用 1000
题解

直接模拟即可。

时间复杂度:

  • push:\(O(1)\)
  • pop:\(O(1)\)
  • increment:\(O(k)\)
class CustomStack {
public:
    vector<int> value;
    int maxSize;
    CustomStack(int maxSize) {
        this->maxSize = maxSize;
    }
    
    void push(int x) {
        if(value.size() == maxSize) return;
        value.push_back(x);
    }
    
    int pop() {
        if(value.size() == 0) return -1;
        int val = value.back();
        value.erase(value.end() - 1);
        return val;
    }
    
    void increment(int k, int val) {
        int n = min(k, (int)value.size());
        for(int i = 0; i < n; i++) {
            value[i] += val;
        }
    }
};

/**
 * Your CustomStack object will be instantiated and called as such:
 * CustomStack* obj = new CustomStack(maxSize);
 * obj->push(x);
 * int param_2 = obj->pop();
 * obj->increment(k,val);
 */

将二叉搜索树变平衡

给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。

如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的

如果有多种构造方法,请你返回任意一种。

示例:

输入:root = [1,null,2,null,3,null,4,null,null]
输出:[2,1,3,null,null,null,4]
解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。

提示:

  • 树节点的数目在 1 到 10^4 之间。
  • 树节点的值互不相同,且在 1 到 10^5 之间。
题解

获取所有节点值后升序排序,然后每次从区间中点分开处理。

时间复杂度:\(O(n)\)

/**
 * 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 {
public:
    vector<int> number;
    void getValue(TreeNode* root) {
        if(root == NULL) return;
        number.push_back(root->val);
        getValue(root->left);
        getValue(root->right);
    }
    TreeNode* greate(int lef, int rig) {
        if(rig < lef) return NULL;
        int mid = lef + rig >> 1;
        TreeNode* root = new TreeNode(number[mid]);
        root->left = greate(lef, mid - 1);
        root->right = greate(mid + 1, rig);
        return root;
    }
    TreeNode* balanceBST(TreeNode* root) {
        getValue(root);
        sort(number.begin(), number.end());
        int n = number.size();
        return greate(0, n - 1);
    }
};

最大的团队表现值

公司有编号为 1 到 n 的 n 个工程师,给你两个数组 speed 和 efficiency ,其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 ​​​​​​最大团队表现值 ,由于答案可能很大,请你返回结果对 10^9 + 7 取余后的结果。

团队表现值 的定义为:一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。

示例 1:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
输出:60
解释:
我们选择工程师 2(speed=10 且 efficiency=4)和工程师 5(speed=5 且 efficiency=7)。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。

示例 2:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
输出:68
解释:
此示例与第一个示例相同,除了 k = 3 。我们可以选择工程师 1 ,工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。

示例 3:

输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
输出:72

提示:

  • 1 <= n <= 10^5
  • speed.length == n
  • efficiency.length == n
  • 1 <= speed[i] <= 10^5
  • 1 <= efficiency[i] <= 10^8
  • 1 <= k <= n
题解

efficiency 降序考虑,遍历每一个员工。

保证至多考虑 k 个员工的情况下,每次选择 efficiency 都是最小的分母,我们要让分子尽量大。

我们把考虑过的分子加入小根堆中,要加入新的分子时,我们把之前的最小分子拿出,新的分子加入,这样能保证考虑 k 个员工的情况下,分子和最大。

时间复杂度:\(O(n\log k)\)

const int MOD = 1E9 + 7;
class Solution {
public:
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<pair<int, int>> inform;
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        long long sum = 0, result = -1;
        for(int i = 0; i < n; i++) {
            inform.push_back(make_pair(efficiency[i], speed[i]));
        }
        sort(inform.begin(), inform.end());
        for(int i = n - 1; 0 <= i; i--) {
            sum = (sum + inform[i].second);
            pq.push(inform[i].second);
            if(--k < 0) {
                sum = sum - pq.top();
                pq.pop();
            }
            result = max(result, sum * inform[i].first);
        }
        return result % MOD;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注