leetcode weekly contes 360

T4 是比较难的题目了，其余的都还算是简单题目。

2833. 距离原点最远的点

给你一个长度为 n 的字符串 moves ，该字符串仅由字符 'L'、'R' 和 '_' 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。

你的初始位置就在原点（0），第 i 次移动过程中，你可以根据对应字符选择移动方向：

如果 moves[i] = 'L' 或 moves[i] = '_' ，可以选择向左移动一个单位距离
如果 moves[i] = 'R' 或 moves[i] = '_' ，可以选择向右移动一个单位距离

移动 n 次之后，请你找出可以到达的距离原点最远的点，并返回 从原点到这一点的距离 。

示例 1：

输入：moves = "L_RL__R"
输出：3
解释：可以到达的距离原点 0 最远的点是 -3 ，移动的序列为 "LLRLLLR" 。

示例 2：

输入：moves = "_R__LL_"
输出：5
解释：可以到达的距离原点 0 最远的点是 -5 ，移动的序列为 "LRLLLLL" 。

示例 3：

输入：moves = "_______"
输出：7
解释：可以到达的距离原点 0 最远的点是 7 ，移动的序列为 "RRRRRRR" 。

提示：

1 <= moves.length == n <= 50
moves 仅由字符 'L'、'R' 和 '_' 组成

地址

https://leetcode.cn/contest/weekly-contest-360/problems/furthest-point-from-origin/

题意

直接模拟

思路

实际除了 ‘L’ 向左右，’R’ 向右走以外，根据贪心算法 __ 要么全部向右要么全部向左
复杂度分析：

时间复杂度：$O(n)$, 其中 $n$ 表示字符串的长度。
空间复杂度：$O(1)$。

代码

[sol1-C++]

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int cnt1 = 0, cnt2 = 0;
        for (auto c : moves) {
            if (c == 'L') cnt1--;
            if (c == 'R') cnt1++;
            if (c == '_') cnt2++;
        }
        return abs(cnt1) + cnt2;
    }
};

2834. 找出美丽数组的最小和

给你两个正整数：n 和 target 。

如果数组 nums 满足下述条件，则称其为 美丽数组 。

nums.length == n.
nums 由两两互不相同的正整数组成。
在范围 [0, n-1] 内，不存在 两个不同下标 i 和 j ，使得 nums[i] + nums[j] == target 。

返回符合条件的美丽数组所可能具备的最小和。

示例 1：

输入：n = 2, target = 3
输出：4
解释：nums = [1,3] 是美丽数组。
- nums 的长度为 n = 2 。
- nums 由两两互不相同的正整数组成。
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 4 是符合条件的美丽数组所可能具备的最小和。

示例 2：

输入：n = 3, target = 3
输出：8
解释：
nums = [1,3,4] 是美丽数组。 
- nums 的长度为 n = 3 。 
- nums 由两两互不相同的正整数组成。 
- 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。
可以证明 8 是符合条件的美丽数组所可能具备的最小和。

示例 3：

输入：n = 1, target = 1
输出：1
解释：nums = [1] 是美丽数组。

提示：

1 <= n <= 105
1 <= target <= 105

地址

https://leetcode.cn/contest/weekly-contest-360/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

题意

贪心算法

思路

与上周周赛的题目一模一样，直接贪心取即可，保证是最小的，因为取了 $x$，则 $target - x$ 就不能取，我们直接从最小的 $1$ 取到最大数即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为给定的元素。
空间复杂度：$O(n)$，其中 $n$ 为给定的元素。

代码

class Solution {
public:
    long long minimumPossibleSum(int n, int target) {
        int m = target / 2;
        if (n <= m) {
            return n * (n + 1) / 2;
        } else {
            return (long long)m * (m + 1) / 2 + (long long)(n - m) * (target * 2 + n - m - 1) / 2;   
        }
    }
};

2835. 使子序列的和等于目标的最少操作次数

给你一个下标从 0 开始的数组 nums ，它包含非负整数，且全部为 2 的幂，同时给你一个整数 target 。

一次操作中，你必须对数组做以下修改：

选择数组中一个元素 nums[i] ，满足 nums[i] > 1 。
将 nums[i] 从数组中删除。
在 nums 的末尾添加两个数，值都为 nums[i] / 2 。

你的目标是让 nums 的一个 子序列 的元素和等于 target ，请你返回达成这一目标的 最少操作次数 。如果无法得到这样的子序列，请你返回 -1 。

数组中一个 子序列 是通过删除原数组中一些元素，并且不改变剩余元素顺序得到的剩余数组。

示例 1：

输入：nums = [1,2,8], target = 7
输出：1
解释：第一次操作中，我们选择元素 nums[2] 。数组变为 nums = [1,2,4,4] 。
这时候，nums 包含子序列 [1,2,4] ，和为 7 。
无法通过更少的操作得到和为 7 的子序列。

示例 2：

输入：nums = [1,32,1,2], target = 12
输出：2
解释：第一次操作中，我们选择元素 nums[1] 。数组变为 nums = [1,1,2,16,16] 。
第二次操作中，我们选择元素 nums[3] 。数组变为 nums = [1,1,2,16,8,8] 。
这时候，nums 包含子序列 [1,1,2,8] ，和为 12 。
无法通过更少的操作得到和为 12 的子序列。

示例 3：

输入：nums = [1,32,1], target = 35
输出：-1
解释：无法得到和为 35 的子序列。

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 230
nums 只包含非负整数，且均为 2 的幂。
1 <= target < 231

地址

https://leetcode.cn/contest/weekly-contest-360/problems/minimum-operations-to-form-subsequence-with-target-sum/

题意

进位运算

思路

首先我们需要数组中所有的数按照 $2$ 的幂次方进行分类统计。$cnt[i]$ 则表示 $2^i$ 的个数，因此对于 $x$ 来说最少的次数肯定是我们将 $x$ 拆分成不同的 $2$ 的幂次之和，我们从低位向高位依次遍历 $x$ 的第 $i$ 位：

假设当前第 $i$ 位为 $0$ 则跳过；
- 假设当前第 $i$ 位为 $1$ 则如果当前 $cnt[i] > 0$，则直接取出一个 $2^i$ 即可，则此时 $cnt[i] - 1$, 否则则按照如下：
- 首先在 $[2^0,2^{i-1}]$ 中找到是否可以组合等于 $2^i$ 的数，这个其实很简单我们可以利用进位运算对 $[0,i-1]$ 进行进位运算即可；
  - 如果没有在 $[2^0,2^{i-1}]$ 中找到，则此时需要从高位进行裂变，此时依次从 $2^{i+1},2^{i+2}, \cdots$ 中找到满足 $cnt[i+ j] > 0$ 的最小元素，此时需要进行操作 $j$ 次，依次将分割后的数进行裂变即可；
- 如果上述两个条件都无法达到，则直接返回 $-1$；

复杂度分析：

时间复杂度：$O(C^3)$，其中 $C = 32$；
空间复杂度：$O(c)$，其中 $C = 32$；

代码

class Solution {
public:
    int minOperations(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<int> cnt(33);
        for (auto v : nums) {
            for (int i = 0; i < 32; i++) {
                if (v & (1 << i)) {
                    cnt[i]++;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < 32; i++) {
            if (target & (1 << i)) {
                /* 向前借位*/
                if (cnt[i] <= 0) {
                    for (int j = 0; j < i; j++) {
                        cnt[j + 1] += cnt[j] / 2;
                        cnt[j] = cnt[j] & 1;
                    }
                }
                    
                /* 向后借位需要裂变 */
                if (cnt[i] <= 0) {
                    for (int j = i + 1; j < 32; j++) {
                        if (cnt[j] > 0) {
                            cnt[j]--;
                            for (int k = j - 1; k > i; k--) {
                                cnt[k]++;
                            }
                            cnt[i] += 2;
                            res += (j - i);
                            break;
                        }
                    }
                }
                if (cnt[i] <= 0) {
                    return -1;
                }
                cnt[i]--;
            }
        }
        return res;
    }
};

2836. 在传球游戏中最大化函数值

给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。

总共有 n 名玩家，玩家编号互不相同，且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。

你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传恰好 k 次。

如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之和，如果有玩家多次触球，则 累加多次 。换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver(k)[x] 。

你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。

请你返回函数的 最大值 。

注意：receiver 可能含有重复元素。

示例 1：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			2
1	2	1	3
2	1	0	3
3	0	2	5
4	2	1	6

输入：receiver = [2,0,1], k = 4
输出：6
解释：上表展示了从编号为 x = 2 开始的游戏过程。
从表中可知，f(2) 等于 6 。
6 是能得到最大的函数值。
所以输出为 6 。

示例 2：

传递次数	传球者编号	接球者编号	x + 所有接球者编号
			4
1	4	3	7
2	3	2	9
3	2	1	10

输入：receiver = [1,1,1,2,3], k = 3
输出：10
解释：上表展示了从编号为 x = 4 开始的游戏过程。
从表中可知，f(4) 等于 10 。
10 是能得到最大的函数值。
所以输出为 10 。

提示：

1 <= receiver.length == n <= 105
0 <= receiver[i] <= n - 1
1 <= k <= 1010

地址

https://leetcode.cn/contest/weekly-contest-360/problems/maximize-value-of-function-in-a-ball-passing-game/

题意

倍增

思路

典型的 binary lifting，树上倍增的思想，不过比较超纲的题目，如果利用倍增的思想，则这个题目就比较简单了，只是需要记录从每个起点跳跃 $2^i$ 次方可以得到的最大累加次数，此时我们可以依次找到从任意起点跳跃 $k$ 次的得分题目就变得很简单了，实际比赛的时候一直在想如何找到 $O(n)$ 的解法，需要仔细处理树上的环的问题，这个代码本身还是挺难写的，因为树中存在各种环。
基环树处理，将整个传递过程转换为基环树，利用前缀和，做法还挺复杂，实际代码非常不好写。
复杂度分析：

时间复杂度：$O(n \log k)$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素。
空间复杂度：$O(n \log k)$，其中 $n$ 表示数组的长度，$k$ 表示给定的元素。

代码

class Solution {
public:
    long long getMaxFunctionValue(vector<int>& receiver, long long k) {
        int n = receiver.size();
        vector<vector<long long>> dp(n, vector<long long>(40));
        vector<vector<long long>> next(n, vector<long long>(40));
        for (int i = 0; i < n; i++) {
            dp[i][0] = receiver[i];
            next[i][0] = receiver[i];
        }
        for (int j = 1; j <= 36; j++) {
            for (int i = 0; i < n; i++) {
                int x = next[i][j - 1];
                int y = next[x][j - 1];
                dp[i][j] = dp[i][j - 1] + dp[x][j - 1];
                next[i][j] = y;
            }
        }
        long long res = 0;
        for (int i = 0; i < n; i++) {
            long long sum = i;
            int curr = i;
            for (int j = 0; j <= 36; j++) {
                if (k & (1LL << j)) {
                    sum += dp[curr][j];
                    curr = next[curr][j];
                }
            }
            res = max(res, sum);
        }
        return res;
    }
};

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

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 359 leetcodeweekly contes 361 →

扫描二维码，分享此文章