LeetCode 第188场周赛

第一题:用栈操作构建数组

难度简单

题目描述

给你一个目标数组 target 和一个整数 n。每次迭代,需要从 list = {1,2,3..., n} 中依序读取一个数字。

请使用下述操作来构建目标数组 target

  • Push:从 list 中读取一个新元素, 并将其推入数组中。
  • Pop:删除数组中的最后一个元素。
  • 如果目标数组构建完成,就停止读取更多元素。

题目数据保证目标数组严格递增,并且只包含 1n 之间的数字。

请返回构建目标数组所用的操作序列。

题目数据保证答案是唯一的。

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • 1 <= target.length <= 100
  • 1 <= target[i] <= 100
  • 1 <= n <= 100
  • target 是严格递增的

题目链接

https://leetcode-cn.com/problems/build-an-array-with-stack-operations/

思路:

  从1target[-1],每个元素都push一次,如果这个元素不在target中,再pop出来。

代码:

第二题:形成两个异或相等数组的三元组数目

难度中等

题目描述

给你一个整数数组 arr

现需要从数组中取三个下标 ijk ,其中 (0 <= i < j <= k < arr.length)

ab 定义如下:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

注意:^ 表示 按位异或 操作。

请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

题目链接

https://leetcode-cn.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/

思路:

  前缀和。

代码:

第三题:收集树上所有苹果的最少时间

难度中等

题目描述

给你一棵有 n 个节点的无向树,节点编号为 0n-1 ,它们中有一些节点有苹果。通过树上的一条边,需要花费 1 秒钟。你从 节点 0 出发,请你返回最少需要多少秒,可以收集到所有苹果,并回到节点 0 。

无向树的边由 edges 给出,其中 edges[i] = [fromi, toi] ,表示有一条边连接 fromtoi 。除此以外,还有一个布尔数组 hasApple ,其中 hasApple[i] = true 代表节点 i 有一个苹果,否则,节点 i 没有苹果。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= n <= 10^5
  • edges.length == n-1
  • edges[i].length == 2
  • 0 <= fromi, toi <= n-1
  • fromi < toi
  • hasApple.length == n

题目链接

https://leetcode-cn.com/problems/minimum-time-to-collect-all-apples-in-a-tree/

思路:

  dfs。记录到每个苹果的路径。然后统计路径和。

代码:

第四题:切披萨的方案数

难度困难

题目描述

给你一个 rows x cols 大小的矩形披萨和一个整数 k ,矩形包含两种字符: 'A' (表示苹果)和 '.' (表示空白格子)。你需要切披萨 k-1 次,得到 k 块披萨并送给别人。

切披萨的每一刀,先要选择是向垂直还是水平方向切,再在矩形的边界上选一个切的位置,将披萨一分为二。如果垂直地切披萨,那么需要把左边的部分送给一个人,如果水平地切,那么需要把上面的部分送给一个人。在切完最后一刀后,需要把剩下来的一块送给最后一个人。

请你返回确保每一块披萨包含 至少 一个苹果的切披萨方案数。由于答案可能是个很大的数字,请你返回它对 10^9 + 7 取余的结果。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= rows, cols <= 50
  • rows == pizza.length
  • cols == pizza[i].length
  • 1 <= k <= 10
  • pizza 只包含字符 '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次的方案数,然后用动态规划求解。注意每次切割要保证切出来的两块矩形区域都有苹果🍎。  

代码: