LeetCode 第185场周赛

反复被虐。。哭🐦。。

第一题:重新格式化字符串

难度简单

题目描述

给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母。

请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同。也就是说,字母后面应该跟着数字,而数字后面应该跟着字母。

请你返回 重新格式化后 的字符串;如果无法按要求重新格式化,则返回一个 空字符串

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= s.length <= 500
  • s 仅由小写英文字母和/或数字组成。

题目链接

https://leetcode-cn.com/problems/reformat-the-string/

思路:

  如果字母数数字数的绝对值大于1,则无法按要求重新格式化。

代码:

第二题:点菜展示表

难度中等

题目描述

给你一个数组 orders,表示客户在餐厅中完成的订单,确切地说, orders[i]=[customerNamei,tableNumberi,foodItemi] ,其中 customerNamei 是客户的姓名,tableNumberi 是客户所在餐桌的桌号,而 foodItemi 是客户点的餐品名称。

请你返回该餐厅的 点菜展示表 在这张表中,表中第一行为标题,其第一列为餐桌桌号 “Table” ,后面每一列都是按字母顺序排列的餐品名称。接下来每一行中的项则表示每张餐桌订购的相应餐品数量,第一列应当填对应的桌号,后面依次填写下单的餐品数量。

注意:客户姓名不是点菜展示表的一部分。此外,表中的数据行应该按餐桌桌号升序排列。

示例 1:

示例 2:

示例 3:

提示:

  • 1 <= orders.length <= 5 * 10^4
  • orders[i].length == 3
  • 1 <= customerNamei.length, foodItemi.length <= 20
  • customerNameifoodItemi 由大小写英文字母及空格字符 ' ' 组成。
  • tableNumberi1500 范围内的整数。

题目链接

https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant/

思路:

  用字典存放每一桌点的菜,每一桌点的菜数量也用字典存放。

代码:

第三题:数青蛙

难度中等

题目描述

给你一个字符串 croakOfFrogs,它表示不同青蛙发出的蛙鸣声(字符串 “croak” )的组合。由于同一时间可以有多只青蛙呱呱作响,所以 croakOfFrogs 中会混合多个 “croak” 请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。

注意:要想发出蛙鸣 “croak”,青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母,那么它就不会发出声音。

如果字符串 croakOfFrogs 不是由若干有效的 “croak” 字符混合而成,请返回 -1

示例 1:

示例 2:

示例 3:

示例 4:

提示:

  • 1 <= croakOfFrogs.length <= 10^5
  • 字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'

题目链接

https://leetcode-cn.com/problems/minimum-number-of-frogs-croaking/

思路:

  ① 当前"c", "r", "o", "a", "k"的数量必须是降序的。因为一只青蛙🐸必须"croak"地叫,而不能是"roak"或者"coak"

  ② 统计"c", "r", "o", "a", "k""c"的数量和"k"的数量之差,就是最少需要的青蛙数,因为"k"表示已经完成的叫声,已经完成的叫声就不需要再计算青蛙数量了。

  ③ 叫声结束后,"c", "r", "o", "a", "k"的数量必须相等。

代码:

第四题:生成数组

难度困难

题目描述

给你三个整数 nmk 。下图描述的算法用于找出正整数数组中最大的元素。

请你生成一个具有下述属性的数组 arr

  • arr 中有 n 个整数。
  • 1 <= arr[i] <= m 其中 (0 <= i < n)
  • 将上面提到的算法应用于 arrsearch_cost 的值等于 k

返回上述条件下生成数组 arr方法数 ,由于答案可能会很大,所以 必须10^9 + 7 取余。

示例 1:

示例 2:

示例 3:

示例 4:

示例 5:

提示:

  • 1 <= n <= 50
  • 1 <= m <= 100
  • 0 <= k <= n

题目链接

https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons/

思路:

  令dp[i][j][kk]表示arr[i:]最大元素为jsearch_cost = kk能表示的种数。

  假设当前数组最大的元素为j,如果增加一个元素,而保持k保持不变的话,增加的新的元素不能超过j,也就是取值范围[1, j],共有j种可能。这一部分表示为dp[i - 1][j][kk] * j

  如果增加一个元素,会使得kk+1,那么增加的元素一定是最大的j,这一部分共有sum(dp[i - 1][1: j][kk-1])种可能性。

  因此递推公式dp[i][j][kk] = dp[i - 1][j][kk] * j +sum(dp[i - 1][1: j][kk-1])

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注