LeetCode 第414场周赛个人题解

本文主要是介绍LeetCode 第414场周赛个人题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Q1. 将日期转换为二进制表示

原题链接

思路分析

AC代码

Q2. 范围内整数的最大得分

原题链接

思路分析

AC代码

Q3. 到达数组末尾的最大得分

原题链接

思路分析

AC代码

Q4. 吃掉所有兵需要的最多移动次数

原题链接

思路分析

AC代码

Q1. 将日期转换为二进制表示

原题链接

Q1. 将日期转换为二进制表示

思路分析

签到题

AC代码

class Solution:def convertDateToBinary(self, date: str) -> str:date = date.split('-')date = [bin(int(x))[2::] for x in date]return '-'.join(date)

Q2. 范围内整数的最大得分

原题链接

Q2. 范围内整数的最大得分

思路分析

二分

最大化最小，可以二分

二分答案x，那么如何check？

贪心的往左边放，第一个放0，那么下一个至少要放到0 + x，下一个的位置为max(0 + x, start[1])

以此类推

时间复杂度：O(nlogU)

AC代码

class Solution:def maxPossibleScore(self, start: List[int], d: int) -> int:start.sort()def check(x: int) -> bool:pre = start[0]for i in range(1, len(start)):pre = max(pre + x, start[i])if pre > start[i] + d:return Falsereturn Truelo, hi = 0, start[-1] + dres = -1while lo <= hi:x = (lo + hi) // 2if check(x):res = xlo = x + 1else:hi = x - 1return res

Q3. 到达数组末尾的最大得分

原题链接

Q3. 到达数组末尾的最大得分

思路分析

李超线段树秒杀斜率优化dp

写一个暴力的dp方程

定义状态 f(i) 为跳到 i 的最大收益

那么 f(i) = min{ f(j) + (i - j) * nums[j] }

f(i) = f(j) + i * nums[j] - j * nums[j]

令 y = f(i), k = nums[j], b = - j * nums[j]

每次插入一条线段，每次状态转移看作 x = i 处所有线段最高点

时间复杂度：O(nlogn)

AC代码

using i64 = long long;const int N = 2e5 + 10;
constexpr i64 inf64 = 1E18 + 7;struct line {i64 k, b;
} lines[N];inline i64 gety(int id, int x) {return lines[id].k * x + lines[id].b;
}int tr[N << 2];#define lc p << 1
#define rc p << 1 | 1
void update(int p, int l, int r, int id) {int mid = l + r >> 1;if (gety(id, mid) > gety(tr[p], mid)) std::swap(tr[p], id);if (gety(id, l) > gety(tr[p], l)) update(lc, l, mid, id);if (gety(id, r) > gety(tr[p], r)) update(rc, mid + 1, r, id);
}i64 query(int p, int l, int r , int x) {if (l == r) return gety(tr[p], x);int mid = l + r >> 1;i64 res = gety(tr[p], x);if (x <= mid) return std::max(res, query(lc, l, mid, x));return std::max(res, query(rc, mid + 1, r, x));
}
class Solution {
public:long long findMaximumScore(vector<int>& a) {memset(tr, 0, sizeof tr);int n = a.size();std::vector<i64> f(n);lines[0] = { a[0], 0 };for (int i = 1; i < n; ++ i) {f[i] = query(1, 0, N - 1, i);lines[i] = { a[i], f[i] - 1LL * i * a[i] };update(1, 0, N - 1, i);}return f[n - 1];}
};

Q4. 吃掉所有兵需要的最多移动次数

原题链接

Q4. 吃掉所有兵需要的最多移动次数

思路分析

博弈dp & 状压dp

网格很小，国际象棋不会下，那么就bfs暴力处理每个点开始，到其它点的距离

定义状态 f(cx, cy, st, turn) 代表玩家从 (cx, cy) 出发，已经遍历过的马的集合为st，turn代表

0：Alice，1：Bob

那么我们枚举当前玩家要到的马的位置(x, y)

对于Alice：

res = max(res, w + dfs(x, y, nst, turn ^ 1))

对于Bob：

res = min(res, w + dfs(x, y, nst, turn ^ 1))

时间复杂度：O(2500 * 2500 + n^2 * (1 << n))

AC代码

B = 50dir = [(-2, -1), (-2, 1), (2, -1), (2, 1),(-1, -2), (-1, 2), (1, -2), (1, 2)
]def get(kx, ky):d = [[inf] * B for _ in range(B)]q = deque([(kx, ky)])d[kx][ky] = 0while q:x, y = q.popleft()for dx, dy in dir:nx, ny = x + dx, y + dyif 0 <= nx < B and 0 <= ny < B and d[nx][ny] == inf:d[nx][ny] = d[x][y] + 1q.append((nx, ny))return dd = [get(i, j) for i in range(B) for j in range(B)]class Solution:def maxMoves(self, kx: int, ky: int, positions: List[List[int]]) -> int:n = len(positions)@cachedef dfs(cx, cy, st: int, turn: int) -> int:if st == (1 << n) - 1:return 0id = cx * B + cyres = inf if turn else -inffor i, (x, y) in enumerate(positions):if ((st >> i) & 1) == 0:w = d[id][x][y]nst = st | (1 << i)if turn:res = min(res, w + dfs(x, y, nst, turn ^ 1))else:res = max(res, w + dfs(x, y, nst, turn ^ 1))return resdfs.cache_clear()return dfs(kx, ky, 0, 0)

这篇关于LeetCode 第414场周赛个人题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！