复盘｜「天池 X LeetCode」在线编程专场选拔赛

统计链表奇数节点

【一次遍历】遍历即可，小技巧是ans直接加0/1结果，省去if判断这一步。
1 2 3 4 5 6 7 class Solution: def numberEvenListNode(self, head: Optional[ListNode]) -> int: ans = 0 while head: ans += head.val & 1 head = head.next return ans

光线反射

【模拟】用DIRS数组存↑↓←→（对应0123四种状态）。由题意，碰到向左倾斜的镜面，←↑是一对，↓→是一对，可以通过异或操作来转换两种状态（状态 xor 2 即可，总共0123四种方向，0 xor 2=2，2 xor 2 = 0，1 xor 2 = 3，3 xor 2 = 1）；碰到向右倾斜的镜面，↓←是一对，↑→是一对，同理，状态 xor 3。初始x,y = (0,0)，d = 1即DIR = (1,0)，然后开始模拟。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution: def getLength(self, grid: List[str], DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))) -> int: n, m = len(grid), len(grid[0]) ans = x = y = 0 d = 1 while 0 <= x < n and 0 <= y < m: ans += 1 if grid[x][y] == 'L': d ^= 2 elif grid[x][y] == 'R': d ^= 3 x += DIRS[d][0] y += DIRS[d][1] return ans

整理书架

【单调栈】要求次数尽可能少，所以要把所有出现次数大于limit的元素，删除知道出现次数=limit。要求字典序最小，所以从左往右遍历如果找到更小数字就把前面更大的数去掉。用单调栈模拟，遍历的同时，要保证栈里的元素出现次数不超过limit，如果后面没有足够的元素，也不能让元素出现次数低于limit，如果遇到比栈顶小的元素，可以出栈。代码中，入栈时候要看后面有没有足够元素。如果没足够元素（cnt[x] = limit）就continue，如果栈顶比x大且栈顶 元素也够则可以出栈。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution: def arrangeBookshelf(self, order: List[int], limit: int) -> List[int]: left, st, cnt_st = Counter(order), [0], Counter() for x in order: if cnt_st[x] == limit: left[x] -= 1 continue while st[-1] > x and left[st[-1]] > limit: left[st[-1]] -= 1 cnt_st[st[-1]] -= 1 st.pop() st.append(x) cnt_st[x] += 1 return st[1:]

意外惊喜

【贪心 + 分治 + 01背包】由于题中说每个礼物包里的礼物价值非严格递增，所以可证不存在选了两个数组但都没有选完的情况，之多只有一个数组没有选完，其余要么整个数组都选，要么都不选。枚举这个没选完的数组，其余的转为01背包（整个数组和当作一个物品的价值，数组长度当作物品体积）。为了优化时间复杂度，需要用分治来优化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution: def brilliantSurprise(self, present: List[List[int]], limit: int) -> int: ans, dp = 0, [0] * (1 + limit) def f(a, tot): nonlocal dp, ans if len(a) == 1: sm = 0 for i, x in enumerate(a[0]): if i >= limit: break sm += x ans = max(ans, dp[limit - (i + 1)] + sm) return tmp, m = dp.copy(), len(a) // 2 left, right = a[:m], a[m:] for i, row in enumerate(left): for j in range(limit, len(row) - 1, -1): dp[j] = max(dp[j], dp[j - len(row)] + tot[i]) f(right, tot[m:]) dp = tmp for i, row in enumerate(right, m): for j in range(limit, len(row) - 1, -1): dp[j] = max(dp[j], dp[j - len(row)] + tot[i]) f(left, tot[:m]) tot = [sum(a) for a in present] f(present, tot) return ans