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

统计链表奇数节点

【一次遍历】遍历即可，小技巧是ans直接加0/1结果，省去if判断这一步。

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)，然后开始模拟。

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大且栈顶 元素也够则可以出栈。

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背包（整个数组和当作一个物品的价值，数组长度当作物品体积）。为了优化时间复杂度，需要用分治来优化。

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