讨论/题目交流/🏆 第 188 场力扣周赛/
🏆 第 188 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛】

image.png

3 分 - 用栈操作构建数组
4 分 - 形成两个异或相等数组的三元组数目
5 分 - 收集树上所有苹果的最少时间
7 分 - 切披萨的方案数

展开讨论
力扣 (LeetCode)发起于 2020-05-10
最近编辑于 2020-05-10

用栈操作构建数组

用两个指针来维护一些信息:

  1. a 指针指向目标数组的元素
  2. b 指针指向 {1,2,3 ... n} 列表的当前元素

显然可以得到以下操作:

  1. 当 b 所指元素小于 a 所指元素,需要丢弃,对应一个 Push + Pop;并且 b 移向下一位
  2. 当 b 所指元素等于 a 所指元素,需要保留,对应一个 Push;b 和 a 都移向下一位
  3. 按题意给出的保证可推导出,b 所指元素不会大于 a 所指的元素

形成两个异或相等数组的三元组数目

关于异或有两个常用的性质:

  1. 任何数和自己异或都得到 0
  2. 任何数和 0 异或都得到自身

由以上两条性质不难解决一个问题 —— 对于一个数组,想求下标范围 [i, j] 之间的所有元素的异或值,可以转化为两个前缀的异或:

  1. pre[j]: 表示 [0, j] 的异或值
  2. pre[i-1]: 表示 [0, i-1] 的异或值
  3. pre[j] ^ pre[i-1] 等价于把 pre[i-1] 抵消掉了,只剩下 [i, j] 的异或值

回到本题:

  1. 先预处理出前缀元素的异或值,记 pre[i] 表示 [0, i] 元素的异或值,O(n)
  2. 对于查询 [i, k] 可以 O(1) 回答:pre[k] ^ pre[i-1]
  3. 对于 [i, k] 的异或值为 0,必定存在下标 j,使得 [i, j-1] 的异或值等于 [j, k] 的异或值(性质1); 枚举下标 j 进行判断

收集树上所有苹果的最少时间

基于一个基本的贪心策略:一个子树有苹果才需要深入下去。因此我们要记录每个节点及其子树下是否有苹果

  1. 记 cnt[i] 表示节点 i 及其子树的苹果数,cnt[i] > 0 表示有苹果
  2. 对于节点 u,它的儿子节点 v,满足 cnt[v] > 0 才需要走进去
  3. 记得返回时,步数也要加 1;特别的,从节点 0 不需要返回,不要加步数

切披萨的方案数

问题的突破在于切饼的方式:每次横切完会把上部分给顾客,竖切完会把左部分给顾客,这意味着上或左部分是不会再参与切割的。

问题进一步转化为,其实总是在考虑某个 (r,c,n,m) 矩阵应该怎么切,其中 r,c 表示矩阵左上角坐标,n,m 表示原始矩阵右下角。

用 DP 来解决这类计数问题:

  1. dp[r][c][k] 表示 (r,c,n,m) 矩阵切成 k 份的方案数;总的状态个数为 505010 = 25000
  2. 枚举横切,假设在 r1 行切,那么转向 dp[r1][y][k-1]
  3. 枚举竖切,假设在 c1 列切,那么转向 dp[r][c1][k-1]
  4. 枚举的代价为 50 + 50 = 100
  5. 总的时间复杂度 O(n * n * k * (n+n))

还需要解决一个问题,判断切割是否合法,也就是判断一个矩阵内是否有苹果:

  1. 把整个矩阵看成 0 1 矩阵,有苹果是 1;一个矩阵有苹果说明矩阵元素和大于 0
  2. 求一个矩阵 (r,c,r1,c1) 的和,等价于 (0,0,r1,c1) - (0,0,r1,c-1) - (0,0,r1-1,c1) + (0,0,r1-1,c1-1);因此先预处理出所有 (0,0,r,c) 矩阵的和
7
展开全部 12 讨论