题目列表
(AC)6167.检查相同字母间的距离(TR)6168.恰好移动 k 步到达某一位置的方法数目(WA)6169.最长优雅子数组(--)6170.会议室 III
赛后总结
总体上来看自己的基础不够扎实。
6167.检查相同字母间的距离
明明的确是一道简单题，就是能把last[ni] == -1 打成 last[ni] = -1 还嗯是反复查错了半天没查出来，静态查错的能力真的挺重要的，可惜没能养成检查的好习惯。顺便一提，开始时想起来Python是用Unicode码和字符进行转换的，当时想到这还愣了一下。
6168.恰好移动 k 步到达某一位置的方法数目
高数基础考试没有考组合数，结果在这里的第二题考了，考试时看出来了要用数学推导，但是把情况复杂化了，想着去分成SP左边、SP-EP和EP右边分别做推导然后再用类组合数推导求解，果然眼界还是比较小。代码也是乱糟糟的，事后几乎没法还原。
6169.最长优雅子数组
又到了每日跪给位运算的时间了，虽然现学了一个 (A & B) | C == (A & B) | (A & C) 但完全只是为了用而用，完全没有去真正的从位运算的方面去想。因此没有发现“对于每一组解，所有的二进制位上只能出现一个1”（这么基础的东西都没能想到也是真的菜），“对于本题目数据范围，优雅数组的最长长度为30”（对于Python语言来说只是安慰剂）。
6170.会议室 III
完全被那个“困难”标签唬住了。其实这题的数据范围就算直接用暴力排序都能做。Python的自带堆更是看完题解现学的。
正确的代码
6167.检查相同字母间的距离
class Solution:
def checkDistances(self, s: str, distance: List[int]) -> bool:
last = [-1] * (26)
for i in range(len(s)):
ni = ord(s[i]) - ord('a')
if last[ni] == -1:
#print("@",i,ni,last[ni])
last[ni] = i
elif i - last[ni] - 1 != distance[ni]:
#print(i - last[ni] - 1 , distance[ni])
return False
else:
#print(i - last[ni] - 1 , distance[ni])
last[ni] = i
return True6168.恰好移动 k 步到达某一位置的方法数目
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
# 组合数这么明显的方法都没想到，我果然还是个傻子
# 从startPos 到 endPos 明显只有向左走和向右走
# 由于向左走和向右走的步数是固定的，只需要用组合数求出
# 到底是哪几步是向一个方向走的选择就行了
if abs(endPos - startPos) > k:
return 0
if (k - abs(endPos - startPos)) % 2 != 0:
return 0
tokimeki = [0] *(k+5)
for i in range(len(tokimeki)):
tokimeki[i] = [0] * (k+5)
tokimeki[i][0] = 1
HONOKA = 10 ** 9 + 7
for i in range(k + 1):
for j in range(1,min(i,(k - abs(endPos - startPos))//2)+1):
tokimeki[i][j] = (tokimeki[i-1][j-1] + tokimeki[i-1][j]) % HONOKA
#print(tokimeki)
return tokimeki[k][(k - abs(endPos - startPos))//2]6169.最长优雅子数组
class Solution:
def longestNiceSubarray(self, nums: List[int]) -> int:
# 每一对元素按位与的运算结果均为0 ->
# 对于每一组解，所有的二进制位上只能出现一个1，
# 也就是说对于本题目数据范围，优雅数组的最长长度为30。
# 根据位运算的性质，(A & B) | C == (A & B) | (A & C) ->
# 可以用一个OR变量储存之前所有数的或运算，这样无需遍历全部数字，
# 由于性质1，对于一个合法的OR变量，或运算视为无损压缩，
# 故对于合法的OR变量，可以进行异或运算以去除之前的某个数
# 由于性质2以及子数组的连续性，我们可以使用双指针，指定左侧边界
l = 0
ans = 0
cur = 0
for r in range(len(nums)):
while nums[r] & cur :
cur ^= nums[l]
l += 1
cur |= nums[r]
if r - l + 1 > ans:
ans = r - l + 1
return ans6170.会议室 III
class Solution:
def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
# 原来只是加了堆的模拟，（经典早知道）在比赛的时候应该先交个暴力排序先试试的
# 用两个小根堆 idle (i) 和 busy (endTime,i) 储存空闲和繁忙的会议室
# 由于会议的时间是线性的，开始时间严格不同且优先处理开始时间最早的会议
# 故可以先对所有会议按照开始时间进行排序
# 在处理一个会议之前，先把所有已经开完会的会议室腾出来，
# 具体方法就是用堆的heappop弹出结束时间早于当前时间（注意左闭右开）会议
# 之后取出尚未占用且编号最小的会议，
# 注意特判：如果所有的会议室均已被占用，替代为弹出结束时间最早的
# 正在开会的会议室，并在更新结束时间之后将其放回正在开会的会议室
idle = list(range(n))
busy = []
cnt = [0] * (n)
meetings.sort()
for i in meetings:
while busy and busy[0][0] <= i[0]:
heappush(idle,heappop(busy)[1])
if len(idle) == 0:
ti, no = heappop(busy)
ti += (i[1] - i[0])
else:
no = heappop(idle)
ti = i[1]
cnt[no] += 1
heappush(busy,(ti,no))
ans = 0
ansi = 0
for i, c in enumerate(cnt):
if c > ans:
ans = c
ansi = i
return ansi其他的碎碎念
后知后觉的感悟
- 秋招也好，米哈游也罢，其实参加每场周赛的人数都是相对稳定的，之前总是有一种“啊，金九银十了，一定会有不少人临阵抱佛脚”的奇怪想法；
- 排名总是会掉的，毕竟还是小菜只因，之后实打实地练到1700以上，然后再去参加灵神的刷题群吧；
- 今天蹲了一整天的图书馆机房，只打了几道题，难度系数还远没之前OI的高；不过挺快乐的，就当是另一种形式的休息了。
无聊的程序模板
老实说作用有限，不过连带变量直接复制题目里的数据，然后粘贴进去还是做得到的。
###################################
# for Contest : LeetCode Week 309
# Problem No. : D
# Title :
###################################
class Solution:
def main():
pass
if __name__ == "__main__":
sol = Solution()
sol.main()错误程序挂路灯
6168.恰好移动 k 步到达某一位置的方法数目
半成品程序，简单问题复杂化
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
# 变量初始化
HONOKA = 10 ** 9 + 7
dp = [ [0] * (k + 5) ] * (k + 5)
ans = 0
# dp计算函数
def lovelive(rang, step):
nonlocal dp,HONOKA
res = 0
if rang == 0:
return 0
if dp[rang][step] != 0:
return dp[rang][step]
if rang == 1:
if step % 2 == 1:
dp[rang][step] = 1
else:
dp[rang][step] = -1
return dp[rang][step]
for i in range(1,rang):
for j in range(i,step - (rang - i) + 1,2):
l = lovelive(i,j)
r = lovelive(rang - i,step - j)
if l == -1 or r == -1:
continue
res = (res + l * r) % HONOKA
return res
# 主算法
# 特判
if k - abs(startPos - endPos) < 0 :
return 0
if (k - abs(startPos - endPos)) % 2 != 0:
return 0
# 求解
side = (k - abs(startPos - endPos)) // 2
for lside in range(0,side + 1):
# 确定左右需要处理的溢出数量
rside = side - lside
for sstep in range(side * 2,k - abs(startPos - endPos) + 1,2):
for lstep in range(lside * 2,sstep - rside):
rstep = sstep - lstep
lans = lovelive(lside,lstep)
rans = lovelive(rside,rstep)
mans = lovelive()6169.最长优雅子数组
现学的还会WA，WA了还调不出来，真的就是个菜只因。
class Solution:
def main(self):
nums = [744437702,379056602,145555074,392756761,560864007,934981918,113312475,1090,16384,33,217313281,117883195,978927664]
print(self.longestNiceSubarray(nums))
def longestNiceSubarray(self, nums: list[int]) -> int:
def lovelive(leng):
nonlocal nums
for i in range(leng - 1,len(nums)):
print(i,i - leng + 1,end=" ")
curHuo = nums[i - leng + 1]
flag = True
for j in range(i - leng + 2,i + 1):
if nums[j] & curHuo != 0:
flag = False
break
if flag :
print(True)
return True
print("\t| ",end="")
print(False)
return False
l = 1
r = len(nums)
while l < r:
mid = (l + r + 1) // 2
if lovelive(mid):
print("\t",mid,True)
l = mid
else:
print("\t",mid,False)
r = mid - 1
return l
