因为 30 日当天返校，要处理很多事情，所以当天搁置了，此为后来补上的文章。
第一题：重复至少 K 次且长度为 M 的模式
给你一个正整数数组 arr，请你找出一个长度为 m 且在数组中至少重复 k 次的模式。
模式 是由一个或多个值组成的子数组（连续的子序列），连续重复多次但不重叠。 模式由其长度和重复次数定义。
如果数组中存在至少重复 k 次且长度为 m 的模式，则返回 true，否则返回 false。
示例：
输入：arr = [1,2,4,4,4,4], m = 1, k = 3
输出：true
解释：模式 (4) 的长度为 1 ，且连续重复 4 次。注意，模式可以重复 k 次或更多次，但不能少于 k 次。
分析
这道题用 Python 的话就是一道秒解题，直接匹配即可。
代码
Python
class Solution:
def containsPattern(self, arr: List[int], m: int, k: int) -> bool:
i = 0
while i < len(arr):
p = arr[i:i+m]
if p * k == arr[i:i+m*k]:
return True
i += 1
return False
第二题：乘积为正数的最长子数组长度
给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例：
输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。
分析
这道题有点贪心算法的影子在里面，为了自己拿数量最大化，所以最好的情况是 Alice 拿最多的，同时 Bob 必须拿最少的，所以就依照这个条件来进行遍历求和即可。
代码
Python
class Solution:
def maxCoins(self, piles: List[int]) -> int:
piles.sort() # 从小到大排序，方便后续处理
left = 0
right = len(piles) - 1
count = 0
while left < right:
if right - 1 >= left: # 如果自己还能够拿一份的话，等于是因为自己比 Bob 先拿
count += piles[right - 1] # 求和
right -= 2 # 我和 Alice 拿完
left += 1 # Bob 拿完
return count
C++
class Solution {
public:
int maxCoins(vector<int>& piles) {
sort(piles.begin(), piles.end(), [](int l, int r) -> bool {
return l > r;
});
int anw = 0;
for(int i = 0; i < piles.size()/3; i++) {
anw += piles[i*2+1];
}
return anw;
}
};
第三题：查找大小为 M 的最新分组
给你一个数组 arr，该数组表示一个从 1 到 n 的数字排列。有一个长度为 n 的二进制字符串，该字符串上的所有位最初都设置为 0 。
在从 1 到 n 的每个步骤 i 中（假设二进制字符串和 arr 都是从 1 开始索引的情况下），二进制字符串上位于位置 arr[i] 的位将会设为 1 。
给你一个整数 m ，请你找出二进制字符串上存在长度为 m 的一组 1 的最后步骤。一组 1 是一个连续的、由 1 组成的子串，且左右两边不再有可以延伸的 1 。
返回存在长度恰好为 m 的一组 1 的最后步骤。如果不存在这样的步骤，请返回 -1 。
示例：
输入：arr = [3,5,1,2,4], m = 1
输出：4
解释：
步骤 1："00100"，由 1 构成的组：["1"]
步骤 2："00101"，由 1 构成的组：["1", "1"]
步骤 3："10101"，由 1 构成的组：["1", "1", "1"]
步骤 4："11101"，由 1 构成的组：["111", "1"]
步骤 5："11111"，由 1 构成的组：["11111"]
存在长度为 1 的一组 1 的最后步骤是步骤 4 。
分析
一开始我直接按着描述，又写了一个典型的超时例子：
class Solution:
def findLatestStep(self, arr: List[int], m: int) -> int:
count = 0
numstr = '0' * len(arr)
for n in range(len(arr)):
numstr = numstr[:arr[n] - 1] + '1' + numstr[arr[n]:]
temp = numstr.split('0')
if '1' * m in temp:
count = n + 1
if count == 0:
return -1
else:
return count
后来找到了另一种解决方法，就是把原来的列表反过来匹配，这样速度会更快；相当于每一次从列表中把一个 1 变为 0，然后每次变换都检查一遍即可。
代码
Python
class Solution:
def findLatestStep(self, arr: List[int], m: int) -> int:
if m == len(arr):
return m
l = [0, len(arr) + 1]
for i, t in enumerate(arr[::-1]):
idx = bisect.bisect(l, t) # 利用 bisect 找到插入位置
l.insert(idx, t)
if l[idx + 1] - l[idx] - 1 == m or l[idx] - l[idx-1] - 1 == m:
# 满足条件即最后一个，可直接返回
return len(arr) - i - 1
return -1
C++
C++ 因为时间问题，就没有写了。
第四题：石子游戏 V
几块石子排成一行，每块石子都有一个关联值，关联值为整数，由数组 stoneValue 给出。
游戏中的每一轮：Alice 会将这行石子分成两个非空行（即，左侧行和右侧行）；Bob 负责计算每一行的值，即此行中所有石子的值的总和。Bob 会丢弃值最大的行，Alice 的得分为剩下那行的值（每轮累加）。如果两行的值相等，Bob 让 Alice 决定丢弃哪一行。下一轮从剩下的那一行开始。
只剩下一块石子时，游戏结束。Alice 的分数最初为 0 。
返回Alice 能够获得的最大分数。
示例：
输入：stoneValue = [6,2,3,4,5,5]
输出：18
解释：在第一轮中，Alice 将行划分为 [6，2，3]，[4，5，5] 。左行的值是 11 ，右行的值是 14 。Bob 丢弃了右行，Alice 的分数现在是 11 。
在第二轮中，Alice 将行分成 [6]，[2，3] 。这一次 Bob 扔掉了左行，Alice 的分数变成了 16（11 + 5）。
最后一轮 Alice 只能将行分成 [2]，[3] 。Bob 扔掉右行，Alice 的分数现在是 18（16 + 2）。游戏结束，因为这行只剩下一块石头了。
分析
这一道题没有做出来，自己一开始的想法就想错了（还是太菜了），我用 DFS 发现做不出结果，最后看了大家的代码发现应该使用 DP 去求解（逃）。
代码
Python
import sys
sys.setrecursionlimit(999999999)
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
n = len(stoneValue)
S = [val for val in stoneValue]
for i in range(1, n):
S[i] += S[i - 1]
@lru_cache(typed=False, maxsize=128000000)
def dp(i, j):
if i == j:
return 0
start_val = 0 if i == 0 else S[i - 1]
total = S[j] - start_val
ans = 0
for mid in range(i, j):
part1 = S[mid] - start_val
part2 = total - part1
tmp = None
if part1 < part2:
tmp = part1 + dp(i, mid)
elif part1 > part2:
tmp = part2 + dp(mid + 1, j)
else:
tmp = max( part1 + dp(i, mid), part2 + dp(mid + 1, j) )
ans = max(ans, tmp)
return ans
return dp(0, n - 1)
C++
C++ 因为时间问题，就没有写了。