Leetcode 第 369 场周赛题解
- Leetcode 第 369 场周赛题解
- 题目1：2917. 找出数组中的 K-or 值
- 思路
- 代码
- 复杂度分析
- 题目2：2918. 数组的最小相等和
- 思路
- 代码
- 复杂度分析
- 题目3：2919. 使数组变美的最小增量运算数
- 思路
- 代码
- 复杂度分析
- 题目4：2920. 收集所有金币可获得的最大积分
- 思路
- 代码
- 复杂度分析
Leetcode 第 369 场周赛题解
题目1：2917. 找出数组中的 K-or 值
思路
模拟。
枚举每个比特位，遍历数组，如果第 i 个比特位上的 1 的个数 ≥ k，则把 2i 加到答案中。
代码
/*
* @lc app=leetcode.cn id=2917 lang=cpp
*
* [2917] 找出数组中的 K-or 值
*/
// @lc code=start
class Solution
{
public:
int findKOr(vector<int> &nums, int k)
{
int k_or = 0;
for (int i = 0; i < 32; i++)
{
int count = 0;
for (const int &num : nums)
if (num & (1 << i))
count++;
if (count >= k)
k_or += (1 << i);
}
return k_or;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogU)，其中 n 为数组 nums 的长度，U=max(nums)。
空间复杂度：O(1)。
题目2：2918. 数组的最小相等和
思路
贪心。
设数组 nums1 的元素总和为 sum1，其中 0 的个数为 countZero1；数组 nums2 的元素总和为 sum2，其中 0 的个数为 countZero2。
题目要求我们必须将两个数组中的 所有 0 替换为严格正整数，并且满足两个数组中所有元素的和相等 。
最后返回最小相等和 ，如果无法使两数组相等，则返回 -1 。
基于贪心的思想，把所有的 0 改成 1，所有元素的和为最小。于是，数组 nums1 的最小和为 sum1 + countZero1，数组 nums2 的最小和为 sum2 + countZero2。
分类讨论：
- 如果 sum1 < sum2 + countZero2 && countZero1 == 0，说明无法将数组 nums1 修改到和修改后的数组 nums2 的和相等，返回 -1。
- 如果 sum2 < sum1 + countZero1 && countZero2 == 0，说明无法将数组 nums2 修改到和修改后的数组 nums1 的和相等，返回 -1。
- 其他情况，都能得到最小相等和。最小相等和为两个最小和的较大值，即 max(sum1 + countZero1, sum2 + countZero2)。
代码
/*
* @lc app=leetcode.cn id=2918 lang=cpp
*
* [2918] 数组的最小相等和
*/
// @lc code=start
class Solution
{
public:
long long minSum(vector<int> &nums1, vector<int> &nums2)
{
long long sum1 = 0, sum2 = 0;
int countZero1 = 0, countZero2 = 0;
for (const int num : nums1)
{
if (num)
sum1 += num;
else
countZero1++;
}
for (const int num : nums2)
{
if (num)
sum2 += num;
else
countZero2++;
}
if (sum1 < sum2 + countZero2 && countZero1 == 0)
return -1;
if (sum2 < sum1 + countZero1 && countZero2 == 0)
return -1;
return max(sum1 + countZero1, sum2 + countZero2);
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n+m)，其中 n 为数组 nums1 的长度，m 为数组 nums2 的长度。
空间复杂度：O(1)。
题目3：2919. 使数组变美的最小增量运算数
思路
动态规划。
把大于 k 的元素视作 k。
由于大于 3 的子数组必然包含等于 3 的子数组，问题转换成：每个长为 3 的子数组都需要包含至少一个 k。
设 dp[i] 表示表示修改第 i 项并使前 i 项变为美丽数组的最小修改次数。
初始化时，dp[0] = max(0, k - nums[0])，dp[1] = max(0, k - nums[1])，dp[2] = max(0, k - nums[2])。
状态转移方程：
dp[i] = min{dp[i−3], dp[i−2], dp[i−1]} + max{0, k−nums[i]}
使原数组变为美丽数组的最小修改次数 ans = min{dp[n−3], dp[n−2], dp[n−1]}。
代码
/*
* @lc app=leetcode.cn id=2919 lang=cpp
*
* [2919] 使数组变美的最小增量运算数
*/
// @lc code=start
class Solution
{
public:
long long minIncrementOperations(vector<int> &nums, int k)
{
int n = nums.size();
// dp[i] 表示表示修改第 i 项并使前 i 项变为美丽数组的最小修改次数
vector<long long> dp(n, 0);
// 初始化
for (int i = 0; i < 3; i++)
dp[i] = max(0, k - nums[i]);
// 状态转移
for (int i = 3; i < n; i++)
{
// 状态转移方程
dp[i] = min(dp[i - 3], min(dp[i - 2], dp[i - 1])) + max(0, k - nums[i]);
}
return min(dp[n - 3], min(dp[n - 2], dp[n - 1]));
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。
题目4：2920. 收集所有金币可获得的最大积分
思路
树型 DP。
题解：树 DP
代码
/*
* @lc app=leetcode.cn id=2920 lang=cpp
*
* [2920] 收集所有金币可获得的最大积分
*/
// @lc code=start
class Solution
{
public:
int maximumPoints(vector<vector<int>> &edges, vector<int> &coins, int K)
{
int n = coins.size();
const int MAXP = 20;
// 建图
vector<int> e[n];
for (auto &edge : edges)
{
e[edge[0]].push_back(edge[1]);
e[edge[1]].push_back(edge[0]);
}
const long long INF = 1e18;
long long f[n][MAXP][2];
for (int i = 0; i < n; i++)
for (int j = 0; j < MAXP; j++)
f[i][j][0] = f[i][j][1] = -INF;
// 树 dp
function<void(int, int)> dp = [&](int sn, int fa)
{
long long now = coins[sn];
for (int j = 0; j < MAXP; j++)
{
f[sn][j][0] = now - K;
if (j > 0)
f[sn][j][1] = now;
now >>= 1;
}
// 枚举子节点的操作
for (int fn : e[sn])
if (fn != fa)
{
dp(fn, sn);
for (int j = 0; j < MAXP; j++)
{
// 这里的 min 是因为我们只考虑 log 次操作
long long best = max(f[fn][j][0], f[fn][min(MAXP - 1, j + 1)][1]);
f[sn][j][0] += best;
f[sn][j][1] += best;
}
}
};
dp(0, -1);
long long ans = 0;
for (int j = 0; j < MAXP; j++)
ans = max({ans, f[0][j][0], f[0][j][1]});
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(nlogU)，其中 n 为 coins 的长度，U=max(coins)。
空间复杂度：O(nlogU)。
