Leetcode 第 414 场周赛题解
- Leetcode 第 414 场周赛题解
- 题目1:3280. 将日期转换为二进制表示
- 思路
- 代码
- 复杂度分析
- 题目2:3281. 范围内整数的最大得分
- 思路
- 代码
- 复杂度分析
- 题目3:3282. 到达数组末尾的最大得分
- 思路
- 代码
- 复杂度分析
- 题目4:3283. 吃掉所有兵需要的最多移动次数
- 思路
- 代码
- 复杂度分析
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(nL2+n22n),其中 n 是数组 positions 的长度,L=50。
空间复杂度:O(nL2+n2n),其中 n 是数组 positions 的长度,L=50。