On the shoulders of giants.

weekly-contest-174

方阵中战斗力最弱的 K 行

给你一个大小为 m * n 的方阵 mat,方阵由若干军人和平民组成,分别用 0 和 1 表示。

请你返回方阵中战斗力最弱的 k 行的索引,按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。

示例 1:

输入:mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
输出:[2,0,3]
解释:
每行中的军人数目:
行 0 -> 2 
行 1 -> 4 
行 2 -> 1 
行 3 -> 2 
行 4 -> 5 
从最弱到最强对这些行排序后得到 [2,0,3,1,4]

示例 2:

输入:mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
输出:[0,2]
解释: 
每行中的军人数目:
行 0 -> 1 
行 1 -> 4 
行 2 -> 1 
行 3 -> 1 
从最弱到最强对这些行排序后得到 [0,2,3,1]

提示:

  • m == mat.length
  • n == mat[i].length
  • 2 <= n, m <= 100
  • 1 <= k <= m
  • matrix[i][j] 不是 0 就是 1
题解

模拟:以第 i 行总和为第一关键字,以序号 i 为第二关键字排序,然后模拟。

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

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size();
        vector<pair<int, int>> tot(n);
        vector<int> ans;
        for(int i = 0; i < n; i++) {
            tot[i].second = i;
            for(int j = 0; j < m; j++) {
                tot[i].first += mat[i][j];
            }
        }
        sort(tot.begin(), tot.end());
        for(int i = 0; i < k; i++) {
            ans.push_back(tot[i].second);
        }
        return ans;
    }
};

数组大小减半

给你一个整数数组 arr。你可以从中选出一个整数集合,并删除这些整数在数组中的每次出现。

返回 至少 能删除数组中的一半整数的整数集合的最小大小。

示例 1:

输入:arr = [3,3,3,3,5,5,5,2,2,7]
输出:2
解释:选择 {3,7} 使得结果数组为 [5,5,5,2,2]、长度为 5(原数组长度的一半)。
大小为 2 的可行集合有 {3,5},{3,2},{5,2}。
选择 {2,7} 是不可行的,它的结果数组为 [3,3,3,3,5,5,5],新数组长度大于原数组的二分之一。

示例 2:

输入:arr = [7,7,7,7,7,7]
输出:1
解释:我们只能选择集合 {7},结果数组为空。

示例 3:

输入:arr = [1,9]
输出:1

示例 4:

输入:arr = [1000,1000,3,7]
输出:1

示例 5:

输入:arr = [1,2,3,4,5,6,7,8,9,10]
输出:5

提示:

  • 1 <= arr.length <= 10^5
  • arr.length 为偶数
  • 1 <= arr[i] <= 10^5
题解

模拟:每个数字出现的次数排序,然后模拟判断。

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

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        map<int, int> total;
        for(auto x : arr) total[x]++;
        vector<int> result;
        for(auto x : total) {
            result.push_back(x.second);
        }
        sort(result.begin(), result.end());
        int cnt = 0, sum = 0, n = result.size();
        for(int i = n - 1; 0 <= i; i--) {
            sum += result[i];
            cnt++;
            if(arr.size() / 2 <= sum) break;
        }
        return cnt;
    }
};

分裂二叉树的最大乘积

给你一棵二叉树,它的根为 root 。请你删除 1 条边,使二叉树分裂成两棵子树,且它们子树和的乘积尽可能大。

由于答案可能会很大,请你将结果对 10^9 + 7 取模后再返回。

示例 1:

输入:root = [1,2,3,4,5,6]
输出:110
解释:删除红色的边,得到 2 棵子树,和分别为 11 和 10 。它们的乘积是 110 (11*10)

示例 2:

输入:root = [1,null,2,3,4,null,null,5,6]
输出:90
解释:移除红色的边,得到 2 棵子树,和分别是 15 和 6 。它们的乘积为 90 (15*6)

示例 3:

输入:root = [2,3,9,10,7,8,6,5,4,11,1]
输出:1025

示例 4:

输入:root = [1,1]
输出:1

提示:

  • 每棵树最多有 50000 个节点,且至少有 2 个节点。
  • 每个节点的值在 [1, 10000] 之间。
题解

先计算出整棵数的权值,然后枚举分离出哪棵子树(剩下的也一定是一棵树),更新答案即可。

因为过程使用求最大值,所以过程不能进行模运算,得最后结果再模。

时间复杂度:\(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) {}
 * };
 */
const int MOD = 1E9 + 7;
class Solution {
public:
    long long sum, result;
    long long getSum(TreeNode* root) {
        if(root == NULL) return 0;
        return getSum(root->left) + getSum(root->right) + root->val;
    }
    long long splitTree(TreeNode* root) {
        if(root == NULL) return 0;
        long long num = splitTree(root->left) + splitTree(root->right) + root->val;
        result = max(result, num * (sum - num));
        return num;
    }
    int maxProduct(TreeNode* root) {
        sum = getSum(root);
        splitTree(root);
        return result % MOD;
    }
};

跳跃游戏 V

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到:

  • i + x ,其中 i + x < arr.length 且 0 < x <= d 。
  • i - x ,其中 i - x >= 0 且 0 < x <= d 。

除此以外,你从下标 i 跳到下标 j 需要满足:arr[i] > arr[j] 且 arr[i] > arr[k] ,其中下标 k 是所有 i 到 j 之间的数字(更正式的,min(i, j) < k < max(i, j))。

你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。

请注意,任何时刻你都不能跳到数组的外面。

示例 1:

输入:arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出:4
解释:你可以从下标 10 出发,然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意,如果你从下标 6 开始,你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处,因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的,你不能从下标 3 处跳到下标 2 或者下标 1 处。

示例 2:

输入:arr = [3,3,3,3,3], d = 3
输出:1
解释:你可以从任意下标处开始且你永远无法跳到任何其他坐标。

示例 3:

输入:arr = [7,6,5,4,3,2,1], d = 1
输出:7
解释:从下标 0 处开始,你可以按照数值从大到小,访问所有的下标。

示例 4:

输入:arr = [7,1,7,1,7,1], d = 2
输出:2

示例 5:

输入:arr = [66], d = 1
输出:1

提示:

  • 1 <= arr.length <= 1000
  • 1 <= arr[i] <= 10^5
  • 1 <= d <= arr.length
题解

动态规划:设 \(dp_x\) 为第 x 位置开始跳,能访问最多是多少个位置。

在合法的情况下,动态转移方程为:

\(dp_x=\max (dp_i+1) ~ , ~ i\in [x-d,x+d]\)

可以看出,我们应该从深度小的开始解决,最后结果为 \(\max dp_i \) ,具体细节请看代码。

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

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size(), result = 0;
        vector<int> dp(n, 1);
        vector<pair<int, int>> pos;
        for(int i = 0; i < n; i++) {
            pos.push_back(make_pair(arr[i], i));
        }
        sort(pos.begin(), pos.end());
        for(int i = 0; i < n; i++) {
            int x = pos[i].second;
            for(int j = x - 1; x - d <= j; j--) {
                if(j < 0 || arr[j] >= arr[x]) break;
                dp[x] = max(dp[x], dp[j] + 1);
            }
            for(int j = x + 1; j <= x + d; j++) {
                if(n <= j || arr[x] <= arr[j]) break;
                dp[x] = max(dp[x], dp[j] + 1);
            }
            result = max(result, dp[x]);
        }
        return result;
    }
};
Share

You may also like...

发表评论

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