P1 圆形赛道上经过次数最多的扇区
给你一个整数 n 和一个整数数组 rounds 。有一条圆形赛道由 n 个扇区组成，扇区编号从 1 到 n 。现将在这条赛道上举办一场马拉松比赛，该马拉松全程由 m 个阶段组成。其中，第 i 个阶段将会从扇区 rounds[i - 1] 开始，到扇区 rounds[i] 结束。举例来说，第 1 阶段从 rounds[0] 开始，到 rounds[1] 结束。
请你以数组形式返回经过次数最多的那几个扇区，按扇区编号 升序 排列。
注意，赛道按扇区编号升序逆时针形成一个圆（请参见第一个示例）。
解：只需考虑起点和终点。 中间过程相当于没跑。
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] R e t u r n Return Return
维护的区间时递增的， 每次可以用二分。 对 n = 1 0 5 n =10^5 n=105的复杂度为 1 0 5 ∗ log ( 1 0 5 ) = 1660964 10^5*\log(10^5) = 1660964 105∗log(105)=1660964。
PS: 比赛时，觉得一定是这样的。 因为第三题一般都是 n log ( 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 ( n 3 ) O(n^3) O(n3)的复杂度， 对 n = 500 n=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
