北京协会网站建设,比分网站怎么做,邢台企业做网站哪家好,北京住房和城乡建设网官网Leetcode 第 369 场周赛题解 Leetcode 第 369 场周赛题解题目1#xff1a;2917. 找出数组中的 K-or 值思路代码复杂度分析 题目2#xff1a;2918. 数组的最小相等和思路代码复杂度分析 题目3#xff1a;2919. 使数组变美的最小增量运算数思路代码复杂度分析 题目4#xff1… Leetcode 第 369 场周赛题解 Leetcode 第 369 场周赛题解题目12917. 找出数组中的 K-or 值思路代码复杂度分析 题目22918. 数组的最小相等和思路代码复杂度分析 题目32919. 使数组变美的最小增量运算数思路代码复杂度分析 题目42920. 收集所有金币可获得的最大积分思路代码复杂度分析 Leetcode 第 369 场周赛题解 题目12917. 找出数组中的 K-or 值
思路
模拟。
枚举每个比特位遍历数组如果第 i 个比特位上的 1 的个数 ≥ k则把 2i 加到答案中。
代码
/** lc appleetcode.cn id2917 langcpp** [2917] 找出数组中的 K-or 值*/// lc codestart
class Solution
{
public:int findKOr(vectorint 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 codeend复杂度分析
时间复杂度O(nlogU)其中 n 为数组 nums 的长度Umax(nums)。
空间复杂度O(1)。
题目22918. 数组的最小相等和
思路
贪心。
设数组 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 appleetcode.cn id2918 langcpp** [2918] 数组的最小相等和*/// lc codestart
class Solution
{
public:long long minSum(vectorint nums1, vectorint nums2){long long sum1 0, sum2 0;int countZero1 0, countZero2 0;for (const int num : nums1){if (num)sum1 num;elsecountZero1;}for (const int num : nums2){if (num)sum2 num;elsecountZero2;}if (sum1 sum2 countZero2 countZero1 0)return -1;if (sum2 sum1 countZero1 countZero2 0)return -1;return max(sum1 countZero1, sum2 countZero2);}
};
// lc codeend复杂度分析
时间复杂度O(nm)其中 n 为数组 nums1 的长度m 为数组 nums2 的长度。
空间复杂度O(1)。
题目32919. 使数组变美的最小增量运算数
思路
动态规划。
把大于 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 appleetcode.cn id2919 langcpp** [2919] 使数组变美的最小增量运算数*/// lc codestart
class Solution
{
public:long long minIncrementOperations(vectorint nums, int k){int n nums.size();// dp[i] 表示表示修改第 i 项并使前 i 项变为美丽数组的最小修改次数vectorlong 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 codeend复杂度分析
时间复杂度O(n)其中 n 是数组 nums 的长度。
空间复杂度O(n)其中 n 是数组 nums 的长度。
题目42920. 收集所有金币可获得的最大积分
思路
树型 DP。
题解树 DP
代码
/** lc appleetcode.cn id2920 langcpp** [2920] 收集所有金币可获得的最大积分*/// lc codestart
class Solution
{
public:int maximumPoints(vectorvectorint edges, vectorint coins, int K){int n coins.size();const int MAXP 20;// 建图vectorint 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;// 树 dpfunctionvoid(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 codeend复杂度分析
时间复杂度O(nlogU)其中 n 为 coins 的长度Umax(coins)。
空间复杂度O(nlogU)。
