第 180 场周赛

Posted on | In , | |
Words count in article: 566 | Reading time ≈ 3

5356. 矩阵中的幸运数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    vector<int> luckyNumbers (vector<vector<int>>& matrix) {
        if(matrix.empty()) return {};
        vector<int> ret;
        unordered_map<int, int> rol;
        unordered_map<int, int> com;
        int m = matrix.size(), n = matrix[0].size(); 
        for(int i=0; i<m; i++) {
            int curmin = INT_MAX;
            for(int j=0; j<n; j++) {
                curmin = min(curmin, matrix[i][j]);
            }
            rol[i] = curmin;
        }
        for(int i=0; i<n; i++) {
            int curmax = INT_MIN;
            for(int j=0; j<m; j++) {
                curmax = max(curmax, matrix[j][i]);
            }
            com[i] = curmax;
        }
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(matrix[i][j] == rol[i] && matrix[i][j] == com[j]) {
                    ret.push_back(matrix[i][j]);
                }
            }
        }
        return ret;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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:
        void PreOrder(vector<TreeNode*>& tmp, TreeNode* root){
        stack<TreeNode*> stack;
        TreeNode* p=root;
        while(p!=NULL || !stack.empty()){
            while(p!=NULL){
                stack.push(p);
                p=p->left;
            }
            p=stack.top();
            stack.pop();
            tmp.push_back(p);
            p=p->right;
        }
    }
    
    TreeNode* balanceBSTCore(vector<TreeNode*>& tmp, int m, int n){
        if(m>n)
            return NULL;
        int k=(m+n)/2;
        tmp[k]->left=balanceBSTCore(tmp,m,k-1);
        tmp[k]->right=balanceBSTCore(tmp,k+1,n);
        return tmp[k];
    }
    
    TreeNode* balanceBST(TreeNode* root) {
        vector<TreeNode*> tmp;
        PreOrder(tmp, root);
        int size=tmp.size()-1;
        return balanceBSTCore(tmp,0,size);
    }
};

1383. 最大的团队表现值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
        long mod = 1000000007;
        long res = 0;
        long sum = 0;
        vector<vector<int>> es;
        for(int i=0; i<n; i++) es.push_back({efficiency[i], speed[i]});
        sort(es.rbegin(), es.rend());
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i=0; i<n; i++) {
            sum += es[i][1];
            int eff = es[i][0];
            q.push(es[i][1]);
            bool flag = false;
            while(q.size() > k) {
                if(q.top() == es[i][1]) flag = true;
                sum -= q.top();
                q.pop();
            }
            if(!flag) res = max(res, eff*sum);
        }
        return (int)(res%mod);
    }
};
Donate? comment?