从今天起决定不写zz美丽版了,事情有点多,zz的视频有点慢。

1. 矩阵中的幸运数

给你一个 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 <= matrixi <= 10^5
  • 矩阵中的所有元素都是不同的

代码

看到数据范围就直接暴力嘛,先记录每一行中最小元素的位置,然后对于每一个最小元素判断它是否在它所在的列中是最大。

class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        
        vector<pair<int, int>> mn;
        for(int i=0; i<n; i++) {
            int now = 1e5 + 5;
            int x = -1, y = -1;
            for(int j=0; j<m; j++) {
                if(matrix[i][j] < now) {
                    now = matrix[i][j];
                    x = i; y = j;
                }
            }
            mn.push_back(make_pair(x, y));
        }
        
        vector<int> ans;
        for(auto v: mn) {
            int x = v.first, y = v.second;
            bool flag = false;
            for(int i=0; i<n; i++) {
                if(i == x) continue;
                if(matrix[i][y] > matrix[x][y]) {
                    flag = true;
                    break;
                }
            }
            if(!flag) ans.push_back(matrix[x][y]);
        }
        return ans;
    }
};

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

请你设计一个支持下述操作的栈。
实现自定义栈类 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 。

样例

示例 1:
输入:
["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
  • 每种方法 increment,push 以及 pop 分别最多调用 1000 次

代码

一开始还在想着给栈底所有元素加$val$要开个标记数组,然后看到数据范围决定无脑暴力了……
内部用$vector$和一个当前指针模拟栈。

class CustomStack {
public:
    vector<int> s;
    int now, maxSize;
    
    CustomStack(int maxSize) {
        now = 0;
        this->maxSize = maxSize;
        s.clear();
        for(int i=0; i<maxSize; i++) s.push_back(-1);
    }
    
    void push(int x) {
        if(now >= maxSize) return;
        s[now++] = x;
    }
    
    int pop() {
        if(now <= 0) return -1;
        return s[--now];
    }
    
    void increment(int k, int val) {
        for(int i=0; i<min(k, now); i++) s[i] += val;
    }
};

3. 将二叉搜索树变平衡

给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的
如果有多种构造方法,请你返回任意一种。

样例

示例 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 之间。

代码

一开始看到这道题给我吓坏了,大一数据结构课的阴影之一AVL树,并且到现在我也没搞清楚那什么左旋右旋。我甚至打开了数据结构PPT想复习一下,然后刷新看了一下过题人数并且不断心理暗示这是Leetcode,终于发现这题好像没这么复杂……
也许我的方法有些蠢,但确实是过了。
首先dfs一遍,将每个元素都压入vector并排序。
然后在这个排完序的vector上直接建树。dfs,每次的根节点都是当前vector的中位数。很显然,这样一定可以保证每一棵子树的左右高度差为0或1。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

vector<int> vec;
void dfs(TreeNode* root) {
    if(root == NULL) return;
    vec.push_back(root->val);
    dfs(root->left);
    dfs(root->right);
}

TreeNode* build(int l, int r) {
    if(l > r) return NULL;
    int m = (l + r) >> 1;
    TreeNode* x = new TreeNode(vec[m]);
    x->left = build(l, m-1);
    x->right = build(m+1, r);
    return x;
}

class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vec.clear();
        dfs(root);
        int n = vec.size();
        sort(vec.begin(), vec.end());
        return build(0, n-1);
    }
};

4. 最大的团队表现值

公司有编号为 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

代码

第一反应DP,然后感觉DP时间和空间复杂度都是$O(n^2)$,我觉得布星。
然后就想不明白怎么贪心。最后在zz的提示下完成了……
首先按照效率从大到小排序,然后用优先队列维护前$x$个人的$top\ k$速度和,并记录第$x$个人的效率与速度和的积,与答案比较找最大值。
在此隆重感谢zz的思路,以免他说我嫌弃他(翻白眼中)。
本质还是枚举。答案=最低效率×速度和,先排序再枚举,确保当前枚举到的效率是当前选择的最低效率,每一种最低效率可能对应很多的速度和,这时贪心让速度和最大就一定是最低效率的最优解,用优先队列来维护。

const int MAXN = 1e5 + 5;
const long long MOD = 1e9 + 7;
struct Employee {
    int v, e;
} employee[MAXN];

bool cmp(Employee& e1, Employee& e2) {
    return e1.e > e2.e;
}

class Solution {
public:    
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        for(int i=0; i<n; i++) employee[i].v = speed[i], employee[i].e = efficiency[i];
        sort(employee, employee+n, cmp);
        
        priority_queue<int, vector<int>, greater<int> > que;
        int cnt = 0;
        long long sum = 0, ans = 0;
        
        for(int i=0; i<n; i++) {
            if(cnt < k) {
                que.push(employee[i].v);
                sum += 1LL * employee[i].v;
                cnt++;
            }
            else {
                if(employee[i].v > que.top()) {
                    sum = sum - (que.top() - employee[i].v) * 1LL;
                    que.pop(); que.push(employee[i].v);
                }
            }
            ans = max(ans, 1LL * employee[i].e * sum);
        }
        return ans % MOD;
    }
};
最后修改:2020 年 03 月 18 日 11 : 13 AM
如果觉得我的文章对你有用,请随意赞赏