package main// https://space.bilibili.com/206214
var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func getLength(g []string) (ans int) {n, m := len(g), len(g[0])x, y, di := 0, 0, 1for 0 <= x && x < n && 0 <= y && y < m {ans++c := g[x][y]if c == 'L' {di ^= 2} else if c == 'R' {di ^= 3}x += dir4[di].xy += dir4[di].y}return
}

四、[Medium] 221021天池-03. 整理书架

链接: 221021天池-03. 整理书架

1. 题目描述

2. 思路分析

• 从左向右遍历尝试把这个数入栈。答案就是最后的栈。
• 用一个单调栈，如果这个数字要进栈，显然要栈中已有的本数数量
• 因此需要一个used的计数器，储存栈里每个数有几个。
• 入栈前，检查栈顶元素，如果栈顶元素大于当前数尝试出栈。
• 出栈的前提当然是后边还存在这个栈顶的数量够用。
• 因此需要一个cnt计数器计算没遍历到的后边元素里每个数字还有多少个。

3. 代码实现

class Solution:def arrangeBookshelf(self, order: List[int], limit: int) -> List[int]:cnt = Counter(order)st = []used = Counter()for i,v in enumerate(order):if used[v] < limit:while st and st[-1] > v and cnt[st[-1]]+used[st[-1]]>limit:used[st.pop()] -= 1used[v] += 1st.append(v)cnt[v] -= 1return st        

五、[Hard] 221021天池-04. 意外惊喜

链接: 221021天池-04. 意外惊喜

1. 题目描述

2. 思路分析

• 这题是我记录这场比赛的主要原因。
• 学习了一个新的分治DP。
• 可以用来优化复杂度，因为用到了大量的重复计算。
• 处理左半部分时，右半部分的结果永远不用动。

3. 代码实现

class Solution:def brilliantSurprise(self, present: List[List[int]], limit: int) -> int:        """1. 由于每个礼包内价值是递增的，我们发现最终的拿取方案中绝对不可能存在两个或以上的礼包都只拿一部分。证明如下：假设存在两个都没拿完的礼包，这两个礼包拿取得最后一个价值分别是ai和bj，那么只存在两种情况:ai==bj 或 ai>bj(如果aib[j],我们知道价值递增，那么a[i+1]>=a[i]>b[j]>=b[j-1]，即a[i+1]必>b[j]，那么我们可以放弃b[j],换取a[i+1],会使答案更优;当a[i]==b[j],我们知道价值内部递增，那么a[i+1]>=a[i]==b[j]>=b[j-1],因此我们可以放弃b[j],换取a[i+1]不会使答案更差。2. 因此最终的选取方案一定是只存在0个或1个礼包拿一部分，其它的要么拿全部要么不拿3. 也就是说其它的可以当01背包计算。体积是本行的len,价值是本行sum4. 01背包复杂度O(n*limit) 再枚举n个数组，那就O(n*n*limit)过不了，因此要想办法重复利用背包的计算结果。5. 这里是分治来优化的。注意在同一层时，需要分别对left求01背包，计算right；对right求01背包，计算left；这两部分的dp前提是一样的，因此要还原DP状态。6. 总体时间复杂度O(limit*n*lgn)"""
# 3928 msdp = [0]*(limit+1)  # 01背包空间压缩写法,dp[j]代表开了j个箱子的最大价值ans = 0total = [sum(row) for row in present]def f(l,r):  # 递归的区间左右端点，避免切片nonlocal ans, dp if l == r:  # 最后一个单独的礼包作为没用完那个s = 0for i,v in enumerate(present[l][:limit],start = 1):s += vans = max(ans, s + dp[limit-i])returnmid = (l+r) // 2  # 分治tmp = dp[:]  # 保留案发现场# 01背包左边，递归右边for i in range(l,mid+1):for j in range(limit, len(present[i]) - 1, -1):dp[j] = max(dp[j], dp[j-len(present[i])]+total[i])f(mid+1, r)dp = tmp  # 还原案发现场# 01背包右边，递归左边for i in range(mid+1, r+1):for j in range(limit, len(present[i]) - 1, -1):dp[j] = max(dp[j], dp[j-len(present[i])]+total[i])f(l, mid)f(0, len(present)-1)return ans# 4080ms
#         dp = [0]*(limit+1)  # 空间压缩的01背包，dp[i]开了i次礼物的最大价值
#         ans = 0
#         def f(pr,total):  # 当前处理的礼包区间,total对应的区间
#             nonlocal ans,dp
#             if len(pr) == 1:  # 区间只剩一个礼包的话，这个就作为最后开的那个没开完的礼包                
#                 s = 0
#                 for i,v in enumerate(pr[0],start=1):
#                     if i > limit:break
#                     s += v
#                     ans = max(ans,dp[limit-i]+s)
#                 return #             tmp = dp.copy()  # 保留案发现场
#             mid = len(pr) // 2
#             left, right = pr[:mid], pr[mid:]#             # 背包左边，处理右边;两种写法都可以 枚举的同样的东西
#             # # 4020 ms
#             # for i,v in enumerate(total[:mid]):
#             #     for j in range(limit,len(pr[i])-1,-1):
#             #         dp[j] = max(dp[j],dp[j-len(pr[i])] + v)  
#             # # 4080 ms
#             for i,row in enumerate(left):
#                 for j in range(limit,len(row)-1,-1):
#                     dp[j] = max(dp[j],dp[j-len(row)]+total[i])
#             f(right,total[mid:])#             dp = tmp  # 还原案发现场
#             # 背包右边，处理左边            
#             # for i,v in enumerate(total[mid:], mid):
#             #     for j in range(limit,len(pr[i])-1,-1):
#             #         dp[j] = max(dp[j],dp[j-len(pr[i])] + v)  
#             for i,row in enumerate(right,mid):
#                 for j in range(limit,len(row)-1,-1):
#                     dp[j] = max(dp[j],dp[j-len(row)]+total[i])
#             f(left,total[:mid])#         total = [sum(row) for row in present]
#         f(present,total)
#         return ans