周赛 – 174

1. 方阵中战斗力最弱的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
  • matrixi 不是 0 就是 1

代码

viv丑陋版

核心就是写一个cmp函数,然后输出前k个。
将原id放在vector最后一维,以便输出。

bool cmp(vector<int>& a, vector<int>& b) {
    int len = a.size();
    int cnta = 0, cntb = 0;
    for(int i=0; i<len-1; i++) {
        if(a[i] == 1) cnta++;
    }
    for(int i=0; i<len-1; i++) {
        if(b[i] == 1) cntb++;
    }
    if(cnta != cntb) return cnta < cntb;
    return a[len-1] < b[len-1];
}

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int len = mat.size();
        for(int i=0; i<len; i++) mat[i].push_back(i);
        sort(mat.begin(), mat.end(), cmp);
        vector<int> ans;
        for(int i=0; i<k; i++) {
            int lenn = mat[i].size();
            ans.push_back(mat[i][lenn-1]);
        }
        return ans;
    }
};

zz美丽版

差不多啦,不过比我优雅一点而已,哼!

const int MAXN = 150;
int battle[MAXN], idx[MAXN];

bool cmp(int a, int b) {
    if(battle[a] != battle[b]) return battle[a] < battle[b];
    return a < b;
}

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        int n = mat.size();
        memset(idx, 0, sizeof(idx));
        
        for(int i=0; i<n; i++) {
            battle[i] = 0; idx[i] = i;
            for(auto v: mat[i]) battle[i] += v;
        }
        
        sort(idx, idx + n, cmp);
        
        vector<int> ans;
        for(int i=0; i<k; i++) ans.push_back(idx[i]);
        return ans;
    }
};

2. 数组大小减半

给你一个整数数组 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

代码

viv丑陋版

很明显,删掉出现次数最多的数字。
所以就想到了统计每个数字出现的次数,放入数组cnt。
然后将cnt数组按照从大到小排序,删到符合要求为止。

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        sort(arr.begin(), arr.end());
        
        int len = arr.size(); 
        int cnt[len], now = 0;
        memset(cnt, 0, sizeof(cnt));
        
        cnt[0] = 1;
        for(int i=1; i<=len; i++) {
            if(i == len || arr[i] != arr[i-1]) now++;
            if(i != len) cnt[now]++;
        }
        sort(cnt, cnt+now);
        
        int ans = 0, sum = 0;
        for(int i=now-1; i>=0; i--) {
            sum += cnt[i]; ans++;
            if(sum >= len / 2) break;
        }
        return ans;
    }
};

zz美丽版

思路也一样。
对于vector的reverse虽然没啥必要,但可以记一下这个用法,和sort一样用。

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        int n = arr.size();
        vector<int> cnt;
        
        sort(arr.begin(), arr.end());
        for(int i=0, app=0; i<n; i++) {
            ++app;
            if(i==n-1 || arr[i] != arr[i+1]) cnt.push_back(app), app = 0;
        }
        
        sort(cnt.begin(), cnt.end());
        reverse(cnt.begin(), cnt.end());
        
        int ans = 0, tot = 0;
        for(auto v: cnt) {
            tot += v; ans++;
            if(tot * 2 >= n) return ans;
        }
        return n;
    }
};

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

给你一棵二叉树,它的根为 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] 之间。

代码

viv丑陋版

绕了半天,最终想法和zz想的一样但是我却TLE了,我晕倒,可能是没吃早饭脑子傻了。
理由很显然,我算子树的和重复计算了N遍,我是猪,我的dfs还是太不熟练了。
树上砍一刀,两部分中其中一部分是一棵完整的子树,另一部分用总体sum减去子树。
枚举所有子树,取一个乘积max就好。
这道题要取模,但是不能乱取模,因为乱取模在TLE之前我WA了好几次。太慌乱了,没时间了……
所有节点的和的范围应该在5e4乘1e4,即5e8之内,所以最终结果应该小于5e8乘5e8,即1e17之内,这个值是不会爆long long的,所以最后返回的时候取模就可以了,中间过程不需要也不能取模,不然比大小结果就错了。
[scode type=”red”]放上我TLE的代码,请勿模仿。[/scode]

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef long long LL;
const LL MOD = 1e9 + 7;

int dfsSum(TreeNode* root) {
    if(root == NULL) return 0;
    int sum = root->val;
    if(root->left) sum += dfsSum(root->left);
    if(root->right) sum += dfsSum(root->right);
    return sum;
}

LL ans = 0;
void dfs(TreeNode* root, int sum) {
    if(root == NULL) return;
    int le = 0, ri = 0;
    if(root->left) {
        le = dfsSum(root->left);
        dfs(root->left, sum);
    }
    if(root->right) {
        ri = dfsSum(root->right);
        dfs(root->right, sum);
    }
    int cur = sum - le - ri;
    LL ans1 = (1LL * (cur + le)) * (1LL * ri);
    LL ans2 = (1LL * (cur + ri)) * (1LL * le);
    ans = max(ans, max(ans1, ans2));
}

class Solution {
public:
    int maxProduct(TreeNode* root) {
        ans = 0;
        int sum = dfsSum(root);
        dfs(root, sum);
        return ans % MOD;
    }
};

zz美丽版

我发现我和zz好像dfs的时候还是有一些小小的差别的。
在dfs的每一层,我考虑的是当前节点+左子树+右子树,也就是说我所谓的“枚举子树”就是在枚举当前层的左子树或右子树,导致我脑子一片浆糊。而zz的“枚举子树”每次枚举的是dfs的当前层,也就是以当前节点为根的子树,所以他写起来soeasy,也不用每次都调用求sum的函数。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
typedef long long LL;
const LL MOD = 1e9 + 7;
class Solution {
public:
    LL sum = 0, ans = 0;
    void dfs_sum(TreeNode* root) {
        if(root == NULL) return;
        sum += root->val;
        dfs_sum(root->left);
        dfs_sum(root->right);
    }
    
    long long dfs_tree(TreeNode* root) {
        if(root == NULL) return 0;
        long long ret = root->val;
        ret += dfs_tree(root->left);
        ret += dfs_tree(root->right);
        if(ans < ret * (sum - ret)) ans = ret * (sum - ret);
        return ret;
    }
    int maxProduct(TreeNode* root) {
        sum = ans = 0;
        dfs_sum(root);
        dfs_tree(root);
        return ans % MOD;
    }
};

4. 跳跃游戏 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:

meta-chart.jpeg

输入: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

代码

viv丑陋版

比赛的时候题目都没来得及看,哭哭。

zz美丽版

又是一道dp。其实还蛮简单的,感觉如果有时间也许能写出来?
dp[i]表示从第i个下标起跳最多能访问的下标个数。
由于跳跃的限制条件,很显然要从高度最低的下标开始转移。
对于每一个坐标,更新其左右两边可以成功跳过去的坐标。
用ans记录所有dp[i]的最大值,毕竟无法确定答案情形下无法再跳跃的坐标位置。

const int MAXN = 1e3 + 5;
int dp[MAXN], idx[MAXN];
vector<int> val;

bool cmp(int a, int b) {
    return val[a] < val[b];
}

class Solution {
public:
    int maxJumps(vector<int>& arr, int d) {
        int n = arr.size(); 
        val = arr;
        for(int i=0; i<n; i++) idx[i] = i;
        sort(idx, idx+n, cmp);
        
        int ans = 0;
        for(int j=0; j<n; j++) {
            int i = idx[j];
            dp[i] = 1;
            for(int j=i-1; j>=0 && j>=i-d; j--) {
                if(arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], dp[j] + 1);
            }
            for(int j=i+1; j<n && j<=i+d; j++) {
                if(arr[j] >= arr[i]) break;
                dp[i] = max(dp[i], dp[j] + 1);
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇