本次周赛，两个简单题，一个中等题，一个难题。我花了四十多分钟做了两个简单题，就不会做了。
比赛链接：143周赛
1104.分糖果II
排排坐，分糖果。
我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。
给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。
然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。
重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。
返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。
示例 1：
输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。
示例 2：
输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。
提示：
* 1 <= candies <= 10^9
* 1 <= num_people <= 1000
idea:
创建一个列表，表示每个人分到的糖果。糖果递增分配，直到糖果分配完。
class Solution:
def distributeCandies(self, candies: int, num_people: int) -> List[int]:
ans = [0]*num_people
i = 1
while(i<=candies):
ans[i%num_people - 1] += i
candies-=i
i += 1
else:
ans[i%num_people - 1] += candies
return ans
1103. 二叉树寻路
在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
示例 1：
输入：label = 14
输出：[1,3,4,14]
示例 2：
输入：label = 26
输出：[1,2,6,10,26]
提示：
1 <= label <= 10^6
idea:
根据label，可以知道label的层数，通过奇偶判断label在从左到右第几个，从而知道父节点是从左到右第几个，一直类推，到根节点。
class Solution:
def pathInZigZagTree(self, label: int) -> List[int]:
i = 0
while(2**i-1<label):
i += 1
ans = []
# temp变量存储label从左到右的位置
if i%2==0:
temp = 2**i - label
else:
temp = label - 2**(i-1) + 1
temp = (temp+1)//2
ans.append(label)
for j in range(i-1):
#由于是从下到上，j需要变一下。
j = i - j -1
if j%2==0:
ans.append(2**j - temp)
else:
ans.append(2**(j-1) + temp - 1)
temp = (temp+1)//2
# 最后将ans反转得到结果
return ans[::-1]
1105.填充书架
附近的家居城促销，你买回了一直心仪的可调节书架，打算把自己的书都整理到新的书架上。
你把要摆放的书 books 都整理好，叠成一摞：从上往下，第 i 本书的厚度为 books[i][0]，高度为 books[i][1]。
按顺序 将这些书摆放到总宽度为 shelf_width 的书架上。
先选几本书放在书架上（它们的厚度之和小于等于书架的宽度 shelf_width），然后再建一层书架。重复这个过程，直到把所有的书都放在书架上。
需要注意的是，在上述过程的每个步骤中，摆放书的顺序与你整理好的顺序相同。 例如，如果这里有 5 本书，那么可能的一种摆放情况是：第一和第二本书放在第一层书架上，第三本书放在第二层书架上，第四和第五本书放在最后一层书架上。
每一层所摆放的书的最大高度就是这一层书架的层高，书架整体的高度为各层高之和。
以这种方式布置书架，返回书架整体可能的最小高度。
示例：
输入：books = [[1,1],[2,3],[2,3],[1,1],[1,1],[1,1],[1,2]], shelf_width = 4
输出：6
解释：
3 层书架的高度和为 1 + 3 + 2 = 6 。
第 2 本书不必放在第一层书架上。
提示：
* 1 <= books.length <= 1000
* 1 <= books[i][0] <= shelf_width <= 1000
* 1 <= books[i][1] <= 1000
idea:
这是一个动态规划问题，最优解由最优子解构成。我们从顶层开始思考，只有有一本书是，最优解就是这本书的高度，两本书时，若两者宽度和满足宽度条件，则是两者的最大值，若不满足，则是两者之和，以此类推，假设有n本书，已经得到最优解，对于n+1本书，第n+1本书单独一行，第n+1本书与第n本书一行，与第n-1本书一行···直到不满足宽度条件。最优解是其中的一个。
class Solution:
def minHeightShelves(self, books: List[List[int]], shelf_width: int) -> int:
dp=[books[0][1]];n=len(books)
for i in range(1,n):
now=1000000000;j=i;tot=0;mx=books[j][1]
while j>=0:
tot+=books[j][0]
mx=max(mx,books[j][1])
if tot>shelf_width:
break
if j>0:
now=min(now,mx+dp[j-1])
else:
now=min(now,mx)
j-=1
dp.append(now)
return dp[n-1]
感谢kayroger的代码。
1106.解析布尔表达式
给你一个以字符串形式表述的 布尔表达式（boolean） expression，返回该式的运算结果。
有效的表达式需遵循以下约定：
* "t"，运算结果为 True
* "f"，运算结果为 False
* "!(expr)"，运算过程为对内部表达式 expr 进行逻辑 非的运算（NOT）
* "&(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 与的运算（AND）
* "|(expr1,expr2,...)"，运算过程为对 2 个或以上内部表达式 expr1, expr2, ... 进行逻辑 或的运算（OR）
示例 1：
输入：expression = "!(f)"
输出：true
示例 2：
输入：expression = "|(f,t)"
输出：true
示例 3：
输入：expression = "&(t,f)"
输出：false
示例 4：
输入：expression = "|(&(t,f,t),!(t))"
输出：false
提示：
* 1 <= expression.length <= 20000
* expression[i] 由 {'(', ')', '&', '|', '!', 't', 'f', ','} 中的字符组成。
* expression 是以上述形式给出的有效表达式，表示一个布尔值。
idea:
这个问题，用栈数据结构就很好的解决了，因为括号是最高优先级，我们先计算括号里面的内容。具体做法是，遍历表达式，若字符不是”)”，就入栈，否则，对栈进行弹出操作，直到遇到一个逻辑运算符，对出栈的字符进行逻辑运算，将结果压入栈。
class Solution:
def parseBoolExpr(self, expression: str) -> bool:
ans = []
for c in expression:
if c!=')':
ans.append(c)
else:
temp = []
while(True):
_c = ans.pop()
if _c=='(':
break
else:
temp.append(_c)
logic = ans.pop()
if logic=='!':
if temp[0]=='t':
ans.append('f')
else:
ans.append('t')
elif logic=='|':
if 't' in temp:
ans.append('t')
else:
ans.append('f')
elif logic=='&':
if 'f' in temp:
ans.append('f')
else:
ans.append('t')
if ans[0]=='t':
return True
else:
return False
总结
本次周赛，比上次简单，但我还是只做了两道题，动态规划还是不熟悉，第四题的思路一开始不明朗，琢磨半天，没想明白。后续加强，动态规划的训练。