Leetcode 第 414 场周赛题解

Leetcode 第 414 场周赛题解

题目1：3280. 将日期转换为二进制表示

思路

切分字符串，分成 year、month、day，转成二进制字符串，再拼接起来。

代码

/** @lc app=leetcode.cn id=3280 lang=cpp** [3280] 将日期转换为二进制表示*/// @lc code=start
class Solution
{
public:string convertDateToBinary(string date){string year = date.substr(0, 4);string month = date.substr(5, 2);string day = date.substr(8);return trans(year) + "-" + trans(month) + "-" + trans(day);}// 辅函数 - 转成二进制字符串string trans(string &s){int x = stoi(s);string res;while (x){res.insert(res.begin(), x % 2 + '0');x /= 2;}return res;}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是字符串 date 的长度。

空间复杂度：O(n)，其中 n 是字符串 date 的长度。

题目2：3281. 范围内整数的最大得分

思路

假设得分为 score。

把区间按照左端点排序。这样我们只需考虑相邻区间所选数字之差。

设从第一个区间选了数字 x，那么第二个区间所选的数字至少为 x+score，否则不满足得分的定义。

由于得分越大，所选数字越可能不在区间内，有单调性，可以二分答案。

代码

/** @lc app=leetcode.cn id=3281 lang=cpp** [3281] 范围内整数的最大得分*/// @lc code=start
class Solution
{
public:int maxPossibleScore(vector<int> &start, int d){int n = start.size();sort(start.begin(), start.end());auto check = [&](int score) -> bool{long long x = LLONG_MIN;for (int &s : start){x = max(x + score, (long long)s);if (x > s + d)return false;}return true;};int left = 0, right = floor(1.0 * (start[n - 1] + d - start[0]) / (n - 1)) + 1;while (left + 1 < right){int mid = left + (right - left) / 2;if (check(mid))left = mid;elseright = mid;}return left;}
};
// @lc code=end

复杂度分析

时间复杂度：O(nlogn+nlogA)，其中 n 是数组 nums 的长度，A = (max(start)+d−min(start)) / (n−1)。排序的时间复杂度为 O(nlogn)，二分 O(logA) 次，每次耗时 O(n)。

空间复杂度：O(1)。忽略排序的栈开销。

题目3：3282. 到达数组末尾的最大得分

思路

动态规划 + 贪心。

只用动态规划会超时：

class Solution {
public:long long findMaximumScore(vector<int>& nums) {if (nums.size() <= 1) return 0LL;int n = nums.size();vector<long long> dp(n + 1);dp[0] = 0;for (int j = 1; j <= n; j++) {for (int i = 1; i < j; i++) {dp[j] = max(dp[j], dp[i] + 1LL * (j - i) * nums[i - 1]);}}return dp[n];}
};

维护一个 maxIndex 表示之前 nums 元素最大值的下标，从贪心的角度思考，从maxIndex 跳到当前下标 i，增加的值最大。

代码

/** @lc app=leetcode.cn id=3282 lang=cpp** [3282] 到达数组末尾的最大得分*/// @lc code=start
class Solution
{
public:long long findMaximumScore(vector<int> &nums){if (nums.size() <= 1)return 0LL;int n = nums.size();vector<long long> dp(n);dp[0] = 0;int maxIndex = 0;for (int i = 1; i < n; i++){dp[i] = dp[maxIndex] + 1LL * (i - maxIndex) * nums[maxIndex];if (nums[i] > nums[maxIndex])maxIndex = i;}return dp[n - 1];}
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)，其中 n 是数组 nums 的长度。

题目4：3283. 吃掉所有兵需要的最多移动次数

思路

定义状态为 dfs(i,mask)，表示当前马在第 i 个兵的位置，且剩余没有被吃掉的兵的集合为 mask 的情况下，继续游戏，两名玩家的总移动次数的最大值。

设从 (x,y) 移动到第 i 个兵的最小步数为 dis[i][x][y]，这可以用网格图 BFS 算出来：反向思考，计算从第 i 个兵的位置出发，通过「马走日」移动到 (x,y) 的最小步数。

设当前位置为 (x,y)=positions[i]，考虑枚举吃掉第 j 个兵：

如果第 j 个兵在集合 mask 中，把马移动 dis[j][x][y] 步，吃掉第 j 个兵。现在问题变成当前马在第 j 个兵的位置，且剩余没有被吃掉的兵的集合为 mask∖{j} 的情况下，继续游戏，两名玩家的总移动次数的最大值。

如果当前是 Alice 操作，则取最大值；如果当前是 Bob 操作，则取最小值。

递归边界：dfs(i,∅)=0。所有兵都被吃掉，游戏结束。

递归入口：dfs(n,U)。即答案。

代码

#
# @lc app=leetcode.cn id=3283 lang=python3
#
# [3283] 吃掉所有兵需要的最多移动次数
## @lc code=start
DIRS = ((2, 1), (1, 2), (-1, 2), (-2, 1), (-2, -1), (-1, -2), (1, -2), (2, -1))class Solution:def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:n = len(positions)# 计算马到兵的步数，等价于计算兵到其余格子的步数dis = [[[-1] * 50 for _ in range(50)] for _ in range(n)]for d, (px, py) in zip(dis, positions):d[px][py] = 0q = [(px, py)]step = 1while q:tmp = qq = []for p in tmp:for dx, dy in DIRS:x, y = p[0] + dx, p[1] + dyif 0 <= x < 50 and 0 <= y < 50 and d[x][y] < 0:d[x][y] = stepq.append((x, y))step += 1positions.append((kx, ky))u = (1 << n) - 1@cachedef dfs(i: int, mask: int) -> int:if mask == 0:return 0odd = (u ^ mask).bit_count() % 2res = inf if odd else 0x, y = positions[i]for j, d in enumerate(dis):if mask >> j & 1:if odd:# Bobres = min(res, dfs(j, mask ^ (1 << j)) + d[x][y])else:# Aliceres = max(res, dfs(j, mask ^ (1 << j)) + d[x][y])return resreturn dfs(n, u)
# @lc code=end

复杂度分析

时间复杂度：O(nL²+n²2ⁿ)，其中 n 是数组 positions 的长度，L=50。

空间复杂度：O(nL²+n2ⁿ)，其中 n 是数组 positions 的长度，L=50。