第 174 场周赛

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

1341. 方阵中战斗力最弱的 K 行

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
bool cmp(vector<int>& a, vector<int>& b){
    if(a[1] == b[1])
        return a[0] < b[0];
    return a[1] < b[1];
}
class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        vector<vector<int>> tmp(mat.size(), vector<int>(2, 0));
        for(int i=0; i<mat.size(); i++){
            tmp[i][0] = i;
            int j=0;
            for(; j<mat[i].size(); j++){
                if(mat[i][j] == 0)
                    break;
            }
            tmp[i][1] = j;
        }
        sort(tmp.begin(), tmp.end(), cmp);
        vector<int> ret;
        for(int i=0; i<k; i++)
            ret.push_back(tmp[i][0]);
        return ret;
    }
};

1342. 数组大小减半

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool cmp(int& a, int& b){
    return a > b;
}
class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int size = arr.size();
        vector<int> a(100005, 0);
        for(auto& i: arr){
            a[i]++;
        }
        sort(a.begin(), a.end(), cmp);
        int count = 0;
        int ret = 0;
        for(int i=0; i<a.size(); i++){
            if(a[i] == 0) break;
            if(count >= size/2) break;
            count += a[i];
            ret++;
        }
        return ret;
    }
};

1339. 分裂二叉树的最大乘积

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
/**
 * 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:
    const static int mod = 1e9 + 7;
    long long ans = -1;
    long long sum = 0;
    long long dfs(TreeNode* root){
        if(root == NULL) return 0;
        long long t1 = dfs(root->left), t2 = dfs(root->right);
        ans = max(ans, max(t1*(sum-t1), t2*(sum-t2)));
        return root->val + t1 + t2;
    }
    int maxProduct(TreeNode* root) {
        sum = dfs(root);
        dfs(root);
        return (int)(ans % mod);
    }
};

1344. 跳跃游戏 V

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 maxJumps(vector<int>& arr, int d) {
        int n = arr.size();
        vector<vector<int>> temp;
        vector<int> dp(n, 1);
        int res = 1;
        for(int i=0; i<n; i++)
            temp.push_back({arr[i], i});
        sort(temp.begin(), temp.end());
        for(int i=0; i<n; i++){
            int index = temp[i][1];
            for(int j=index-1; j>=index-d && j>=0; j-- ){
                if(arr[j] >= arr[index]) break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            for(int j=index+1; j<=index+d && j<n; j++ ){
                if(arr[j] >= arr[index]) break;
                dp[index] = max(dp[index], dp[j]+1);
            }
            res = max(res, dp[index]);
        }
        return res;
    }
};
Donate? comment?