第一题：用栈操作构建数组
难度简单
题目描述
给你一个目标数组 target 和一个整数 n。每次迭代，需要从 list = {1,2,3..., n} 中依序读取一个数字。
请使用下述操作来构建目标数组 target ：
- Push：从
list中读取一个新元素， 并将其推入数组中。 - Pop：删除数组中的最后一个元素。
- 如果目标数组构建完成，就停止读取更多元素。
题目数据保证目标数组严格递增，并且只包含 1 到 n 之间的数字。
请返回构建目标数组所用的操作序列。
题目数据保证答案是唯一的。
示例 1：
|
1 2 3 4 5 6 7 |
输入：target = [1,3], n = 3 输出：["Push","Push","Pop","Push"] 解释： 读取 1 并自动推入数组 -> [1] 读取 2 并自动推入数组，然后删除它 -> [1] 读取 3 并自动推入数组 -> [1,3] |
示例 2：
|
1 2 3 |
输入：target = [1,2,3], n = 3 输出：["Push","Push","Push"] |
示例 3：
|
1 2 3 4 |
输入：target = [1,2], n = 4 输出：["Push","Push"] 解释：只需要读取前 2 个数字就可以停止。 |
示例 4：
|
1 2 3 |
输入：target = [2,3,4], n = 4 输出：["Push","Pop","Push","Push","Push"] |
提示：
1 <= target.length <= 1001 <= target[i] <= 1001 <= n <= 100target是严格递增的
题目链接
https://leetcode-cn.com/problems/build-an-array-with-stack-operations/
思路:
从1到target[-1]，每个元素都push一次，如果这个元素不在target中，再pop出来。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def buildArray(self, target: List[int], n: int) -> List[str]: ans = [] for i in range(1, target[-1]+1): if i > n: break if i in target: ans.append('Push') else: ans = ans + ['Push', 'Pop'] return ans |
第二题：形成两个异或相等数组的三元组数目
难度中等
题目描述
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。
请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
示例 1：
|
1 2 3 4 |
输入：arr = [2,3,1,6,7] 输出：4 解释：满足题意的三元组分别是 (0,1,2), (0,2,2), (2,3,4) 以及 (2,4,4) |
示例 2：
|
1 2 3 |
输入：arr = [1,1,1,1,1] 输出：10 |
示例 3：
|
1 2 3 |
输入：arr = [2,3] 输出：0 |
示例 4：
|
1 2 3 |
输入：arr = [1,3,5,7,9] 输出：3 |
示例 5：
|
1 2 3 |
输入：arr = [7,11,12,9,5,2,7,17,22] 输出：8 |
提示：
1 <= arr.length <= 3001 <= arr[i] <= 10^8
题目链接
https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
思路:
前缀和。
代码:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution: def countTriplets(self, arr: List[int]) -> int: prefix = [0] * len(arr) prefix[0] = arr[0] for i in range(1, len(arr)): prefix[i] = arr[i] ^ prefix[i-1] n = len(arr) ans = 0 for i in range(n): for j in range(i+1,n): for k in range(j,n): if i == 0: a = prefix[j-1] else: a = prefix[j-1] ^ prefix[i-1] b = prefix[k] ^ prefix[j-1] if a == b: ans += 1 # print(i,j,k) return ans |
第三题：收集树上所有苹果的最少时间
难度中等
题目描述
给你一棵有 n 个节点的无向树，节点编号为 0 到 n-1 ，它们中有一些节点有苹果。通过树上的一条边，需要花费 1 秒钟。你从 节点 0 出发，请你返回最少需要多少秒，可以收集到所有苹果，并回到节点 0 。
无向树的边由 edges 给出，其中 edges[i] = [fromi, toi] ，表示有一条边连接 from 和 toi 。除此以外，还有一个布尔数组 hasApple ，其中 hasApple[i] = true 代表节点 i 有一个苹果，否则，节点 i 没有苹果。
示例 1：
|
1 2 3 4 |
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] 输出：8 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。 |
示例 2：
|
1 2 3 4 |
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false] 输出：6 解释：上图展示了给定的树，其中红色节点表示有苹果。一个能收集到所有苹果的最优方案由绿色箭头表示。 |
示例 3：
|
1 2 3 |
输入：n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false] 输出：0 |
提示：
1 <= n <= 10^5edges.length == n-1edges[i].length == 20 <= fromi, toi <= n-1fromi < toihasApple.length == n
题目链接
https://leetcode-cn.com/problems/minimum-time-to-collect-all-apples-in-a-tree/
思路:
dfs。记录到每个苹果的路径。然后统计路径和。
代码:
|
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 31 32 33 34 35 36 37 38 39 40 41 42 |
from collections import defaultdict class Solution: def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: E = defaultdict(list) for x, y in edges: E[x].append(y) E[y].append(x) visited = [False] * n ans = 0 path = [] pre = [0] def to(): nonlocal ans ans += max(len(pre),len(path)) - min(len(pre),len(path)) for j in range(min(len(pre),len(path))): if pre[j] != path[j]: ans += 2 def dfs(i): nonlocal pre if visited[i]: return path.append(i) if hasApple[i]: to() pre = path.copy() visited[i] = True for nxt in E[i]: dfs(nxt) path.pop() dfs(0) path = [0] to() return ans |
第四题：切披萨的方案数
难度困难
题目描述
给你一个 rows x cols 大小的矩形披萨和一个整数 k ，矩形包含两种字符： 'A' （表示苹果）和 '.' （表示空白格子）。你需要切披萨 k-1 次，得到 k 块披萨并送给别人。
切披萨的每一刀，先要选择是向垂直还是水平方向切，再在矩形的边界上选一个切的位置，将披萨一分为二。如果垂直地切披萨，那么需要把左边的部分送给一个人，如果水平地切，那么需要把上面的部分送给一个人。在切完最后一刀后，需要把剩下来的一块送给最后一个人。
请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字，请你返回它对 10^9 + 7 取余的结果。
示例 1：
|
1 2 3 4 |
输入：pizza = ["A..","AAA","..."], k = 3 输出：3 解释：上图展示了三种切披萨的方案。注意每一块披萨都至少包含一个苹果。 |
示例 2：
|
1 2 3 |
输入：pizza = ["A..","AA.","..."], k = 3 输出：1 |
示例 3：
|
1 2 3 |
输入：pizza = ["A..","A..","..."], k = 1 输出：1 |
提示：
1 <= rows, cols <= 50rows == pizza.lengthcols == pizza[i].length1 <= k <= 10pizza只包含字符'A'和'.'。
题目链接
https://leetcode-cn.com/problems/number-of-ways-of-cutting-a-pizza/
思路:
由于要多次查询矩形区域内有没有苹果，因此先用has_apple[x1][x2][y1][y2]表示pizza[x1:x2][y1:y2]的范围内有没有苹果。
dp[i][j][k]表示，矩形[i:n][j:m] 切割了k次的方案数，然后用动态规划求解。注意每次切割要保证切出来的两块矩形区域都有苹果🍎。
代码:
|
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 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from collections import defaultdict class Solution: def ways(self, pizza: List[str], k: int) -> int: m = len(pizza) n = len(pizza[0]) # dp = [[] for _ in range(k+1)] dp = {(0,0):1} has_apple = [[[[False for _ in range(n+1)] for _ in range(n+1)] for _ in range(m+1)] for _ in range(m+1)] # m m n n for x1 in range(m): for x2 in range(x1+1, m+1): for y1 in range(n): for y2 in range(y1+1, n+1): if pizza[x2-1][y2-1] == 'A': has_apple[x1][x2][y1][y2] = True continue has_apple[x1][x2][y1][y2] = has_apple[x1][x2-1][y1][y2] or has_apple[x1][x2][y1][y2-1] # has_apple(x1, x2, y1, y2): # pizza[x1:x2][y1:y2] 有没有苹果 # print(has_apple) for kk in range(1, k): temp = defaultdict(int) for lm, ln in dp: # 之前的情况 count = dp[(lm, ln)] for i in range(lm+1, m): # 按行切 if has_apple[lm][i][ln][n] and has_apple[i][m][ln][n]: temp[(i,ln)] += count for j in range(ln+1, n): # 按列切 if has_apple[lm][m][ln][j] and has_apple[lm][m][j][n]: temp[(lm, j)] += count # print(temp) dp = temp return sum(dp.values()) % (1000000000 + 7) |
