leetcode 第360场周赛

总结

好久没参加leetcode周赛了，比赛时间都从两小时变成了一个半小时。这次周赛由两道签到题和两道中等难度题组成，严格来说最后一道的难度也可以视为hard，但是只要想到正确的思路，编码还是比较容易的。

比赛链接:leetcode 第 360 场周赛

题目列表

1.距离原点最远的点

题目描述

给你一个长度为 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' 和 '_' 组成

分析

本题主要是理解题意，moves是’_'的时候可以选择左移也可以选择右移，要求最终到达的位置离原点最远。

移动的顺序无所谓，因此经过若干次’L’和’R’的移动后，位置P是唯一的，此时只剩下若干个’_‘的操作符，如果P是在原点左边，’_'就继续左移，否则右移。具体实现时候只需要统计下各个操作字符的个数，然后返回$abs(L-R)+cnt(\_)$即可。

代码

class Solution {
public:
    int furthestDistanceFromOrigin(string moves) {
        int l = 0, r = 0, t = 0;
        for(int i = 0;i < moves.size();i++) {
            if (moves[i] == 'L') l++;
            else if(moves[i] == 'R') r++;
            else t++;
        }
        return max(l, r)  - min(l, r) + t;
    }
};

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

题目描述

给你两个正整数：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 <= 10^5
• 1 <= target <= 10^5

分析

简单的模拟题，从1开始枚举数组里的正整数，添加i前确认下数组里不存在target - i的数字，添加后就使用哈希表记录下已添加的数字，直至枚举到n个数，求和即可。

代码

class Solution {
public:
    unordered_map<int,int> m;
    long long minimumPossibleSum(int n, int target) {
        long long res = 0;
        int cnt = 0;
        int num = 1;
        while(cnt < n) {
            if (!m.count(target - num)) {
                cnt++;
                m[num] = 1;
                res += num;
            }
            num++;
        }
        return res;
    }
};

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

题目描述

给你一个下标从 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] <= 2^30
• nums 只包含非负整数，且均为 2 的幂。
• 1 <= target < 2^31

分析

首先，数组里面的元素都是2的整数次幂，只要数组的和不小于target，那么经过若干次拆分一定可以使得子序列的和等于target。

不难想到将target使用二进制表示，拆分成若干个2的整数次幂数字的和，然后在数组里面找到这些数字，如果不存在，要么拆分，要么使用更小的数累加。

nums = [1,32,1,2], target = 12

第二个示例比较适合用来分析，target为12=4 + 8，数组里找不到4，所以使用两个1和一个2拼到一起了；然后32拆分两次得到8。什么时候使用拼接，什么时候使用拆分？想清楚这个问题本题就可以求解了。

求解思路如下：

• 将target的二进制表示存入vector s，将数组里面的元素二进制表示也存入一个vector v。
• 自低位到高位遍历target的二进制vector，如果该位置是1，就在v中查找有没有对应的元素，有就将该元素数量减一，将多余的元素除以2累加到更高位的元素数量，没有就继续往高位查找，找到高位元素后一步步分解，分解到需要的元素重复前面的步骤；如果s的该位置是0，也需要将v中对应元素除以2累加到高位。

以上面例子为例，12=(1100)₂，最低位是0，而nums里面有2个1，将这两个1累加起来增加2的个数，得到[32,2,2]；第二位还是0，将两个2累加起来得到[32,4]，第三位是1，并且数组里面出现了累加的4;第四位是1，数组里面没有找到8，向高位找到了32，拆分两次得到了8，最终拆分的次数是2。

因此，本题的关键就是想到对于没用完的元素，累加到高位继续用，想到了这点直接模拟就可以解决了。

代码

class Solution {
public:
    int index(int n) {
        if (n == 1) return 0;
        return index(n / 2) + 1;
    }
    int minOperations(vector<int>& nums, int target) {
        vector<int> v(32, 0);
        vector<int> s;
        int t = target;
        while(t) {
            s.push_back(t & 1);
            t >>= 1;
        }
        int n = s.size();
        long long sum = 0;
        for(auto x : nums) {
            v[index(x)]++;
            sum += x;
        }
        if (sum < target) return -1;
        int res = 0;
        for (int i = 0; i < n;i++) {
            if (s[i]) {
                if (v[i]) {
                    v[i]--;
                    v[i+1] += v[i] / 2;
                    continue;
                }
                int j = i + 1;
                while(!v[j]) j++;
                while(j != i) {
                    v[j]--;
                    v[--j] += 2;
                    res++;
                }
            } else {
                v[i+1] += v[i] / 2;
            }
        }
        return res;
    }
};

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

题目描述

给你一个长度为 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 <= 10^5
• 0 <= receiver[i] <= n - 1
• 1 <= k <= 10^10

分析

本题常规解法，找环的起点比较繁琐，而且即使找到了环，如果环的长度是10w级别的，遍历下n个起点，时间也会超限。比较好的解法是使用DP+倍增。一共要传k轮，可以对k进行二进制拆分，比如k = 13，可以拆除1 + 4 + 8，也就是先传1轮，再传4轮，最后传8轮。

状态表示：$f[i][j]$表示从$i$开始，传$2^j$轮经过的编号之和，注意这里的编号不包括$i$本身，因为一旦包含了$i$，第一次传到了$t$，已经统计了$t$的编号，第二次从$t$开始传，就重复统计了，统计编号时不包含起点，最后统计结果时再加上起点的编号即可。

另外，除了需要记录传$2^j$后的编号之和，还需要记录位置，这样才能确定下一轮传输的起点，即$pos[i][j]$表示从$i$开始，传$2^j$轮到达的编号。

状态转移方程：
$$f[i][j]=f[i][j-1]+f[pos[i][j-1]][j-1]$$

$$pos[i][j]=pos[pos[i][j-1]][j-1]$$

也就是从$i$出发走$2^j$步，只需要从$i$出发先走$2^{j-1}$步到达$pos[i][j-1]$的位置，再从该位置出发再走$2^{j-1}$步。

状态边界：$f[i][0]=receiver[i]$和$pos[i][0]=receiver[i]$。

另外，还需要记录下走$k$轮，每次走到的中转的位置，这样才能在此基础上找到下次的起点。

由于状态转移每次只使用了上一层的状态，所以可以使用滚动数组实现，节省内存空间。

具体实现见代码：文章来源地址https://www.toymoban.com/news/detail-680222.html

代码

class Solution {
public:
    static const int N = 100005;
    long long f[N][2];
    int pos[N][2], pre[N];
    long long ans[N];
    long long getMaxFunctionValue(vector<int>& r, long long k) {
        int n = r.size();
        for (int i = 0; i < n;i++) {
            f[i][0] = r[i];
            pos[i][0] = r[i];
            pre[i] = i;
        }
        if (k & 1) {
            for(int i = 0; i < n;i++) {
                ans[i] = f[i][0];
                pre[i] = pos[i][0];
            }
        }
        for (int i = 1; i < 35;i++) {
            int t1 = i & 1, t2 = 1 - t1;
            for (int j = 0; j < n;j++) {
                f[j][t1] = f[j][t2] + f[pos[j][t2]][t2];
                pos[j][t1] = pos[pos[j][t2]][t2];
            }
            if(k >> i & 1) {
                for(int j = 0; j < n;j++) {
                    ans[j] += f[pre[j]][t1];
                    pre[j] = pos[pre[j]][t1];
                }
            }
        }
        long long res = 0;
        for(int i = 0; i < n;i++) res = max(res, i + ans[i]);
        return res;
    }
};

到了这里，关于leetcode 第360场周赛的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！