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

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

image.png

3 分 - 重新格式化字符串
4 分 - 点菜展示表
5 分 - 数青蛙
6 分 - 生成数组

展开讨论
力扣 (LeetCode)发起于 2020-04-19

A: 重新格式化字符串

将字符分类,字母一组,数字一组,轮流使用。当两组的个数相差超过 1 时无解。

B: 点菜展示表

header 中,要包含所有菜名,并且按字典序排序,用 set 保存所有菜名。

对于每张桌子,我们保存它有哪些菜,每个菜有几份。

最后按数字顺序遍历桌子,输出每种菜有多少份。

C: 数青蛙

  1. 若已知每个青蛙目前喊到了哪个字符,且 croak 中每个字符都不同,则可以知道每个青蛙下一次喊什么字符;由于可以循环喊,所以 k 之后是 c
  2. 用一个 map 记录下一次喊 ch 字符的青蛙有哪些;当读到某个字符 ch 时,在其中取出一个青蛙让他喊,并更新它的下一个叫喊字符
  3. 当遇到字符 ch 却没有青蛙会喊该字符时,问题无解;另外当喊完所有字符后,某些青蛙只喊到一半也是非法的,无解。

D: 生成数组

我们从左到右放置元素,一个新放置的元素如果会引起 search cost 变化,说明该元素比前面的最大值还要大,因此我们可以以此为思路构造 DP 方程

  1. 状态表示:f[i][j][k] 表示前 i 个元素最大值是 j 且 search cost 为 k 的数量
  2. 从第 i 位能推导到第 i+1 位,第 i+1 位元素范围 [1,m],分两种情况:
    1. 若 1 <= x <= j,显然 f[i+1][j][k] += f[i][j][k]
    2. 若 j < x <= m,显然 f[i+1][x][k+1] += f[i][j][k]
  3. 状态空间为 O(n * m * k),时间复杂度为 O(n * m * k * m)
10
展开全部 25 讨论