[Leetcode/python3]第203场周赛题解


P1 圆形赛道上经过次数最多的扇区

给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成,扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛,该马拉松全程由 m 个阶段组成。其中,第 i 个阶段将会从扇区 rounds[i – 1] 开始,到扇区 rounds[i] 结束。举例来说,第 1 阶段从 rounds[0] 开始,到 rounds[1] 结束。

请你以数组形式返回经过次数最多的那几个扇区,按扇区编号 升序 排列。

注意,赛道按扇区编号升序逆时针形成一个圆(请参见第一个示例)。

[Leetcode/python3]第203场周赛题解
解:只需考虑起点和终点。 中间过程相当于没跑。

class Solution:
def mostVisited(self, n: int, rounds: List[int]) -> List[int]:
a, b = rounds[0], rounds[-1]
if a == b: return [a]
if a < b: return [x for x in range(a, b+1)]
return [x for x in range(1, b + 1)] + [x for x in range(a, n+1)]

P2 你可以获得的最大硬币数目

有 3n 堆数目不一的硬币,你和你的朋友们打算按以下方式分硬币:

每一轮中,你将会选出 任意 3 堆硬币(不一定连续)。
Alice 将会取走硬币数量最多的那一堆。
你将会取走硬币数量第二多的那一堆。
Bob 将会取走最后一堆。
重复这个过程,直到没有更多硬币。
给你一个整数数组 piles ,其中 piles[i] 是第 i 堆中硬币的数目。

返回你可以获得的最大硬币数目。

解:贪心。
Code 1:

class Solution:
def maxCoins(self, piles: List[int]) -> int:
piles = sorted(piles)[::-1]
return sum(piles[2*i + 1] for i in range(len(piles) // 3))

Code 2:

class Solution:
def maxCoins(self, A):
return sum(sorted(A)[len(A)//3::2])

P3 查找大小为 M 的最新分组

给你一个数组 arr ,该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串,该字符串上的所有位最初都设置为 0 。

在从 1 到 n 的每个步骤 i 中(假设二进制字符串和 arr 都是从 1 开始索引的情况下),二进制字符串上位于位置 arr[i] 的位将会设为 1 。

给你一个整数 m ,请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串,且左右两边不再有可以延伸的 1 。

返回存在长度 恰好 为 m 的 一组 1 的最后步骤。如果不存在这样的步骤,请返回 -1 。

解一: 倒序 + 二分

    最终状态为 n 个 1 , 用区间 [ 1, n ] 表示 。

    [6,3,5,1,2,4],m=1[6, 3,5,1,2,4], m=1

    [6,3,5,1,2,4],m=1 为例,

    4=>[1,3],[5,6]4 => [ 1, 3], [ 5, 6]

    4=>[1,3],[5,6]

    2=>[1,1],[3,3],[5,6]2 => [1, 1], [3,3], [5,6]

    2=>[1,1],[3,3],[5,6]

    ReturnReturn

    Return
    维护的区间时递增的, 每次可以用二分。 对

    n=105n =10^5

    n=105的复杂度为

    105log(105)=166096410^5*\log(10^5) = 1660964

    105∗log(105)=1660964。
    PS: 比赛时,觉得一定是这样的。 因为第三题一般都是

    nlog(n)n\log(n)

    nlog(n), 没想到这次模拟一下就可以了。

class Solution:
def findLatestStep(self, arr: List[int], m: int) -> int:
n = len(arr)
if n == m: return n
A = [[1, n]]
def bs(A, x):
if x < A[0][0]:
return -1
if x >= A[-1][0]:
return len(A) -1
L, R = 0, len(A) -1
while L < R:
mid = (L + R) >> 1
if A[mid][0] <= x:
if A[mid + 1][0] <= x:
L = mid + 1
else:
return mid
else:
R = mid - 1
return L
cnt = n
for x in arr[::-1]:
cnt -= 1
idx = bs(A, x)
if idx == -1:
return -1
a, b = A[idx]
if x - a == m or b - x == m:
return cnt
del A[idx]
if x+1 <= b:
A.insert(idx, [x + 1, b])
if a <= x-1:
A.insert(idx, [a, x - 1])
return -1

解二: 模拟

O(n)O(n)

O(n)

class Solution:
def findLatestStep(self, A, m):
Counter = collections.defaultdict(int)
n = len(A)
cnt = [0] * n
res = -1
for i, a in enumerate(A):
a -= 1
L = cnt[a-1] if a else 0
R = cnt[a+1] if a + 1 < n else 0
cnt[a - L] = cnt[a + R] = cnt[a] = L + R + 1
Counter[L] -= 1
Counter[R] -= 1
Counter[cnt[a]] += 1
if Counter[m]:
res = i + 1
return res

P4 石子游戏 V

几块石子 排成一行 ,每块石子都有一个关联值,关联值为整数,由数组 stoneValue 给出。

游戏中的每一轮:Alice 会将这行石子分成两个 非空行(即,左侧行和右侧行);Bob 负责计算每一行的值,即此行中所有石子的值的总和。Bob 会丢弃值最大的行,Alice 的得分为剩下那行的值(每轮累加)。如果两行的值相等,Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。

只 剩下一块石子 时,游戏结束。Alice 的分数最初为 0 。

返回 Alice 能够获得的最大分数 。

解一:记忆化搜索。
PS: 用记忆化搜索能过。 但是,直接求是TLE。

O(n3)O(n^3)

O(n3)的复杂度, 对

n=500n=500

n=500, 应该是过不了的。

class Solution:
def stoneGameV(self, A: List[int]) -> int:
C = []
for x in A:
if not C:
C.append(x)
else:
C.append(x + C[-1])

def get(i):
return 0 if i < 0 else C[i]

n = len(A)
from functools import lru_cache
@lru_cache(None)
def dp(i,j):
if j ==i: return 0
ret = 0
for k in range(i, j):
left, right = get(k) - get(i-1), get(j) - get(k)
if right < left:
ret = max(ret, right + dp(k + 1, j))
elif left < right:
ret = max(ret, left + dp(i, k))
else:
ret = max(ret, right + dp(k+1, j), left + dp(i, k))
return ret

return dp(0, n-1)

解二:DP + 优化

class Solution:
def stoneGameV(self, A: List[int]) -> int:
n = len(A)
C = self.getRangeCum(A)
M = self.getmid(A)
dp = [[[0] * 3 for _ in range(n)] for _ in range(n)]

for k in range(1, n+1):
for i in range(n):
j = i + k - 1
if j >= n: continue
mid_L = M[i][j][0]
mid_R = M[i][j][1]
if mid_L != -1: dp[i][j][2] = max(dp[i][j][2], dp[i][mid_L][0])
if mid_R != -1: dp[i][j][2] = max(dp[i][j][2], dp[mid_R][j][1])

tmp = dp[i][j][2] + C[i][j]
if i == j:
dp[i][j][0] = dp[i][j][1] = tmp
else:
dp[i][j][0] = max(tmp, dp[i][j-1][0])
dp[i][j][1] = max(tmp, dp[i+1][j][1])

return dp[0][-1][-1]

def getRangeCum(self, A):
n = len(A)
C = [[0]*n for _ in range(n)]
for L in range(n):
for R in range(L, n):
C[L][R] = A[L] if L == R else C[L][R-1] + A[R]
return C

def getmid(self, A):
n = len(A)
C = self.getRangeCum(A)
M = [[[-1] * 2 for _ in range(n)] for _ in range(n)]
for i in range(n):
L = i
p, R = L, L + 1
while R < n:
while C[L][p] <= C[L][R] / 2:
p += 1
if p - 1 >= L:
M[L][R][0] = p -1
if C[L][p-1] == C[L][R] / 2:
M[L][R][1] = p

if M[L][R][1] == -1 and p+1 <= R:
M[L][R][1] = p + 1
R += 1
return M

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

[Leetcode/python3]第203场周赛题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » [Leetcode/python3]第203场周赛题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏