且听疯吟

leetcode biweekly contes 104

2023-05-18

leetcode biweekly contes 104

手速场的题目，可惜的是每次手速场排名都不咋读，也许是年纪大了，思维不够快。非手速场，成绩还好一些。

6366. 老人的数目

给你一个下标从 0 开始的字符串 details 。details 中每个元素都是一位乘客的信息，信息用长度为 15 的字符串表示，表示方式如下：

  • 前十个字符是乘客的手机号码。
  • 接下来的一个字符是乘客的性别。
  • 接下来两个字符是乘客的年龄。
  • 最后两个字符是乘客的座位号。

请你返回乘客中年龄 严格大于 60 岁 的人数。

示例 1：

输入：details = ["7868190130M7522","5303914400F9211","9273338290F4010"]
输出：2
解释：下标为 0 ，1 和 2 的乘客年龄分别为 75 ，92 和 40 。所以有 2 人年龄大于 60 岁。

示例 2：

输入：details = ["1313579440F2036","2921522980M5644"]
输出：0
解释：没有乘客的年龄大于 60 岁。

提示：

  • 1 <= details.length <= 100
  • details[i].length == 15
  • details[i] 中的数字只包含 '0' 到 '9' 。
  • details[i][10] 是 'M' ，'F' 或者 'O' 之一。
  • 所有乘客的手机号码和座位号互不相同。

地址

https://leetcode.cn/contest/weekly-contest-343/problems/determine-the-winner-of-a-bowling-game/

题意

直接模拟

思路

  1. 直接统统计年龄即可，返回大于 $60$ 的人数即可。
  2. 复杂度分析：
  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

代码

class Solution {
public:
    int countSeniors(vector<string>& details) {
        int res = 0;
        for (auto s : details) {
            int val = stoi(s.substr(11, 2));
            if (val > 60) {
                res++;
            }
        }
        return res;
    }
};

6367. 矩阵中的和

给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：

  1. 矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
  2. 在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数 中。

请你返回最后的 分数 。

示例 1：

输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
输出：15
解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。

示例 2：

输入：nums = [[1]]
输出：1
解释：我们删除 1 并将分数增加 1 ，所以返回 1 。

提示：

  • 1 <= nums.length <= 300
  • 1 <= nums[i].length <= 500
  • 0 <= nums[i][j] <= 103

地址

https://leetcode.cn/contest/biweekly-contest-104/problems/sum-in-a-matrix/

题意

排序

思路

  1. 根据题意要求，由于每一行按照从大到小的顺序进行删除，首先我们将矩阵的每一行按照从大到小进行排序；
  2. 根据题意要求，每次删除的得分为所有行中的最大值，因此我们依次求出每列中的最大值并求和即可；
  3. 复杂度分析：
  • 时间复杂度：$O(mn)$，其中 $m,n$ 为矩阵的行数与列数。
  • 空间复杂度：$O(mn)$，其中 $m,n$ 为矩阵的行数与列数。

代码

class Solution {
public:
    int matrixSum(vector<vector<int>>& nums) {
        int res = 0;
        int m = nums.size();
        int n = nums[0].size();
        for (int i = 0; i < m; i++) {
            sort(nums[i].begin(), nums[i].end());
        }
        for (int i = 0; i < n; i++) {
            int curr = 0;
            for (int j = 0; j < m; j++) {
                curr = max(curr, nums[j][i]);
            }
            res += curr;
        }
        return res;
    }
};

6369. 最大或值

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 k 。每一次操作中，你可以选择一个数并将它乘 2 。

你最多可以进行 k 次操作，请你返回 nums[0] | nums[1] | ... | nums[n - 1] 的最大值。

a | b 表示两个整数 a 和 b 的 按位或 运算。

示例 1：

输入：nums = [12,9], k = 1
输出：30
解释：如果我们对下标为 1 的元素进行操作，新的数组为 [12,18] 。此时得到最优答案为 12 和 18 的按位或运算的结果，也就是 30 。

示例 2：

输入：nums = [8,1,2], k = 2
输出：35
解释：如果我们对下标 0 处的元素进行操作，得到新数组 [32,1,2] 。此时得到最优答案为 32|1|2 = 35 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 15

地址

https://leetcode.cn/contest/biweekly-contest-104/problems/maximum-or/

题意

贪心

思路

  1. 动态规划的思路就非常简单了，设 $dp[i][j]$ 表示前 $i$ 个元素进行 $j$ 次移位操作时的最大值，此时可以知道：

    $$dp[i][j] = \max(dp[i-1][s] \lor nums[i]\times 2^{j-s})$$，上述的动态规划思路是错误的，最优子集可能不在这个里面。比如给定数组 $[10,8,4]$, 前两个数进行 $1$ 次移位的最大值为 $(10 << 1) \lor 8 = 11100$ ，但是最终的最大值不是在这个区间里面，前两个数组的最大值可能为 $10 \lor (8 << 1) \lor 4 = 11110$,所以动态规划的思路完全错误。题目确实是个不错的构造题，比较有意思。

  2. 由于题目给定的 $k$ 的取值范围为 $[1,15]$, 因此根据贪心算法我们应该尽可能的将数组中的其中一个数往左移动 $k$ 位，为什么要选择一个数，有以下几方面原因:

    • $32$ 整数在给定的 $k$ 的范围下，最少可以向左移动 $32$ 位，因此 $k$ 位完全可以给定一个数进行移位操作；
    • 我们可以知道实际过程肯定在最高位往左移的位数越多，最终或运算的结果越大，假设当前数中某个数移动 $x$ 位后那么它的最高第 $i$ 位为 $1$，此时我们最优选择应该也是将剩余的 $k - i$ 位全部用来移动该数，此时数组中所有数的可能的最高位为 $i + k - x$，这样即可使得或运算的值最大；
    • 我们存储数组或的前缀与后缀，分别尝试对每个数进行移位，然后与前缀与后缀进行或运算。

  3. 复杂度分析：

  • 时间复杂度：$O(n)$，其中 $n$ 为给定的数组的长度。
  • 空间复杂度：$O(n)$，其中 $n$ 为给定的数组的长度。

代码

class Solution {
public:
    long long maximumOr(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefix(n + 1);
        vector<int> suffix(n + 1);
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] | nums[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            suffix[i] = suffix[i + 1] | nums[i];
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            res = max(res, (long long)nums[i] << k | prefix[i] | suffix[i + 1]);
        }
        return res;
    }
};

2681. 英雄的力量

给你一个下标从 0 开始的整数数组 nums ，它表示英雄的能力值。如果我们选出一部分英雄，这组英雄的 力量 定义为：

  • i0 ，i1 ，… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik]) 。

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大，请你将结果对 109 + 7 取余。

示例 1：

输入：nums = [2,1,4]
输出：141
解释：
第 1 组：[2] 的力量为 22 * 2 = 8 。
第 2 组：[1] 的力量为 12 * 1 = 1 。
第 3 组：[4] 的力量为 42 * 4 = 64 。
第 4 组：[2,1] 的力量为 22 * 1 = 4 。
第 5 组：[2,4] 的力量为 42 * 2 = 32 。
第 6 组：[1,4] 的力量为 42 * 1 = 16 。
第 7 组：[2,1,4] 的力量为 42 * 1 = 16 。
所有英雄组的力量之和为 8 + 1 + 64 + 4 + 32 + 16 + 16 = 141 。

示例 2：

输入：nums = [1,1,1]
输出：7
解释：总共有 7 个英雄组，每一组的力量都是 1 。所以所有英雄组的力量之和为 7 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109

地址

https://leetcode.cn/contest/biweekly-contest-104/problems/power-of-heroes/

题意

组合数学

思路

  1. 题目本质看起来就是一个组合数学的问题，其实分析起来也不难，只要能够推导出公式来题目就非常简单了，首先我们肯定是需要根据题意对数组进行排序，这样才能进行枚举最大值与最小值；

  2. 接下来先思考一个简单问题，假设当前子序列以 $nums[i]$ 为最小值，以 $nums[j]$ 为最大值时，此时可以得到的力量值之和为多少？

    • 我们可以知道此时一定满足 $i \le j$, 此时该序列中的剩余元素一定只能在 $[i+1,j-1]$ 中取，此时有多少种取法，就可以组成多少个以 $nums[i]$ 为最小值，以 $nums[j]$ 为最大值的子序列，根据排列组合数可以知道此时一共有 $2^{j - 1 - i}$ 种不同的取法；
    • 则此时以 $nums[i]$ 为最小值，以 $nums[j]$ 为最大值组成的英雄的力量值之和一定为 $2^{j - i - 1} \times nums[i] \times nums[j]^{2}$;

  3. 根据上述的分析可以知此时假设我们以 $nums[j]$ 为最大值，此时最小值可以为 $nums[0], nums[1],nums[2],\cdots nums[j - 1]$，则此时可以知道以 $nums[j]$ 为最大值构成的合法的英雄组的总力量值如下:

    $$power_{j} = nums[j]^3 + nums[j]^2 \times \sum_{i=0}^{j-1}2^{j-i-1}\times nums[i]$$

  4. 根据上述推导出来的公式就非常方便了，我们令 $f[k] = \sum_{i=0}^{k}2^{k-i}\times nums[i]$, 令 $f[-1] = 0,f[0] = nums[i]$此时可以根据递推关系可以知道 $f[k+1] = 2f[k] + nums[k+1]$, 综上可以知道如下递推公式:

    ​ $$power_{j} = nums[j]^3 + nums[j]^2 \times f[j-1]$$

  5. 复杂度分析：

  • 时间复杂度：$O(n \log n)$，其中 $n$ 为数组的长度；
  • 空间复杂度：$O(\log n)$，其中 $n$ 为数组的长度；

代码

class Solution {
public:
    int sumOfPower(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        long long mod = 1e9 + 7;
        long long res = 0;
        long long curr = 0;
        for (int i = 0; i < n; i++) {
            res = (res + (((long long)nums[i] * nums[i]) % mod) * curr % mod) % mod;
            res = (res + (((long long)nums[i] * nums[i] % mod) * nums[i]) % mod) % mod;
            curr = (curr * 2 + nums[i]) % mod;
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

Tags: 题解 力扣季度赛
← leetcode weekly contes 344 leetcode weekly contes 345 →

扫描二维码，分享此文章