LeetCode 第185场周赛

反复被虐。。哭🐦。。

Contents

1 第一题：重新格式化字符串
2 第二题：点菜展示表
3 第三题：数青蛙
4 第四题：生成数组

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

难度简单

题目描述

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

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

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

示例 1：

输入：s = "a0b1c2"
输出："0a1b2c"
解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

输入：s = "a0b1c2"

输出："0a1b2c"

解释："0a1b2c" 中任意两个相邻字符的类型都不同。 "a0b1c2", "0a1b2c", "0c2a1b" 也是满足题目要求的答案。

示例 2：

输入：s = "leetcode"
输出：""
解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。

输入：s = "leetcode"

输出：""

解释："leetcode" 中只有字母，所以无法满足重新格式化的条件。

示例 3：

输入：s = "1229857369"
输出：""
解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。

输入：s = "1229857369"

输出：""

解释："1229857369" 中只有数字，所以无法满足重新格式化的条件。

示例 4：

输入：s = "covid2019"
输出："c2o0v1i9d"

输入：s = "covid2019"

输出："c2o0v1i9d"

示例 5：

输入：s = "ab123"
输出："1a2b3"

输入：s = "ab123"

输出："1a2b3"

提示：

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

题目链接

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

思路:

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

代码:

class Solution:
    def reformat(self, s: str) -> str:
        ans = ''
        n = len(s)
        nums = ''
        alphas = ''
        for i in range(n):
            if s[i].isdigit():
                nums += s[i]
            else:
                alphas += s[i]

        if abs(len(nums) - len(alphas)) > 1:
            return ''

        nums = list(nums)
        alphas = list(alphas)

        flag = len(nums) > len(alphas)
        while nums or alphas:
            if flag:
                ans += nums.pop(0)
            else:
                ans += alphas.pop(0)
            flag = not flag

        return ans

class Solution:

def reformat(self, s: str) -> str:

ans = ''

n = len(s)

nums = ''

alphas = ''

for i in range(n):

if s[i].isdigit():

nums += s[i]

else:

alphas += s[i]

if abs(len(nums) - len(alphas)) > 1:

return ''

nums = list(nums)

alphas = list(alphas)

flag = len(nums) > len(alphas)

while nums or alphas:

if flag:

ans += nums.pop(0)

else:

ans += alphas.pop(0)

flag = not flag

return ans

第二题：点菜展示表

难度中等

题目描述

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

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

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

示例 1：

输入：orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]
输出：[["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]] 
解释：
点菜展示表如下所示：
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
对于餐桌 3：David 点了 "Ceviche" 和 "Fried Chicken"，而 Rous 点了 "Ceviche"
而餐桌 5：Carla 点了 "Water" 和 "Ceviche"
餐桌 10：Corina 点了 "Beef Burrito"

输入：orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken"],["Carla","5","Water"],["Carla","5","Ceviche"],["Rous","3","Ceviche"]]

输出：[["Table","Beef Burrito","Ceviche","Fried Chicken","Water"],["3","0","2","1","0"],["5","0","1","0","1"],["10","1","0","0","0"]]

解释：

点菜展示表如下所示：

Table,Beef Burrito,Ceviche,Fried Chicken,Water

3 ,0 ,2 ,1 ,0

5 ,0 ,1 ,0 ,1

10 ,1 ,0 ,0 ,0

对于餐桌 3：David 点了 "Ceviche" 和 "Fried Chicken"，而 Rous 点了 "Ceviche"

而餐桌 5：Carla 点了 "Water" 和 "Ceviche"

餐桌 10：Corina 点了 "Beef Burrito"

示例 2：

输入：orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]
输出：[["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]] 
解释：
对于餐桌 1：Adam 和 Brianna 都点了 "Canadian Waffles"
而餐桌 12：James, Ratesh 和 Amadeus 都点了 "Fried Chicken"

输入：orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken"],["Adam","1","Canadian Waffles"],["Brianna","1","Canadian Waffles"]]

输出：[["Table","Canadian Waffles","Fried Chicken"],["1","2","0"],["12","0","3"]]

解释：

对于餐桌 1：Adam 和 Brianna 都点了 "Canadian Waffles"

而餐桌 12：James, Ratesh 和 Amadeus 都点了 "Fried Chicken"

示例 3：

输入：orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
输出：[["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

输入：orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]

输出：[["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

提示：

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

题目链接

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

思路:

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

代码:

from collections import defaultdict

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        table = defaultdict(dict)
        dishes = set()
        for _, tid, food in orders:
            dishes.add(food)
            tid = int(tid)
            if food in table[tid]:
                table[tid][food] += 1  
            else:
                table[tid][food] = 1

        dishes = sorted(dishes)
        head = ['Table'] + dishes
        ans = [head]
        for tid, dish in sorted(table.items()):
            line = [str(tid)]
            for d in dishes:
                if d in table[tid]:
                    line.append(str(table[tid][d]))
                else:
                    line.append('0')


            ans.append(line)

        return ans

from collections import defaultdict

class Solution:

def displayTable(self, orders: List[List[str]]) -> List[List[str]]:

table = defaultdict(dict)

dishes = set()

for _, tid, food in orders:

dishes.add(food)

tid = int(tid)

if food in table[tid]:

table[tid][food] += 1

else:

table[tid][food] = 1

dishes = sorted(dishes)

head = ['Table'] + dishes

ans = [head]

for tid, dish in sorted(table.items()):

line = [str(tid)]

for d in dishes:

if d in table[tid]:

line.append(str(table[tid][d]))

else:

line.append('0')

ans.append(line)

return ans

第三题：数青蛙

难度中等

题目描述

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

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

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

示例 1：

输入：croakOfFrogs = "croakcroak"
输出：1 
解释：一只青蛙 “呱呱” 两次

输入：croakOfFrogs = "croakcroak"

输出：1

解释：一只青蛙 “呱呱” 两次

示例 2：

输入：croakOfFrogs = "crcoakroak"
输出：2 
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

输入：croakOfFrogs = "crcoakroak"

输出：2

解释：最少需要两只青蛙，“呱呱” 声用黑体标注

第一只青蛙 "crcoakroak"

第二只青蛙 "crcoakroak"

示例 3：

输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。

输入：croakOfFrogs = "croakcrook"

输出：-1

解释：给出的字符串不是 "croak" 的有效组合。

示例 4：

输入：croakOfFrogs = "croakcroa"
输出：-1

输入：croakOfFrogs = "croakcroa"

输出：-1

提示：

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"的数量必须相等。

代码:

from collections import defaultdict

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        ans = 1
        dt = {}
        for i, c in enumerate('croak'):
            dt[c] =  i

        cnt = [0] * 5

        for c in croakOfFrogs:
            cnt[dt[c]] += 1
            for i in range(4):
                if cnt[i] < cnt[i + 1]:
                    return -1
                ans = max(ans, cnt[0] - cnt[4])

        if cnt[0] != cnt[4]:
            return -1

        return ans

from collections import defaultdict

class Solution:

def minNumberOfFrogs(self, croakOfFrogs: str) -> int:

ans = 1

dt = {}

for i, c in enumerate('croak'):

dt[c] = i

cnt = [0] * 5

for c in croakOfFrogs:

cnt[dt[c]] += 1

for i in range(4):

if cnt[i] < cnt[i + 1]:

return -1

ans = max(ans, cnt[0] - cnt[4])

if cnt[0] != cnt[4]:

return -1

return ans

第四题：生成数组

难度困难

题目描述

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

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

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

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

示例 1：

输入：n = 2, m = 3, k = 1
输出：6
解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

输入：n = 2, m = 3, k = 1

输出：6

解释：可能的数组分别为 [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

示例 2：

输入：n = 5, m = 2, k = 3
输出：0
解释：没有数组可以满足上述条件

输入：n = 5, m = 2, k = 3

输出：0

解释：没有数组可以满足上述条件

示例 3：

输入：n = 9, m = 1, k = 1
输出：1
解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]

输入：n = 9, m = 1, k = 1

输出：1

解释：可能的数组只有 [1, 1, 1, 1, 1, 1, 1, 1, 1]

示例 4：

输入：n = 50, m = 100, k = 25
输出：34549172
解释：不要忘了对 1000000007 取余

输入：n = 50, m = 100, k = 25

输出：34549172

解释：不要忘了对 1000000007 取余

示例 5：

输入：n = 37, m = 17, k = 7
输出：418930126

输入：n = 37, m = 17, k = 7

输出：418930126

提示：

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:]最大元素为j且search_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])。

代码:

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        dp = [[[0 for _ in range(k + 1)] for _ in range(m + 1)] for _ in range(n)]
        for j in range(1, m + 1):
            dp[0][j][1] = 1

        for i in range(1, n):
            for kk in range(1, k + 1):           
                acc = 0
                for j in range(1, m + 1):
                    dp[i][j][kk] = dp[i - 1][j][kk] * j + acc
                    acc += dp[i - 1][j][kk - 1]

        ans = 0
        for line in dp[n - 1]:
            ans += line[k]
        return ans % 1000000007

class Solution:

def numOfArrays(self, n: int, m: int, k: int) -> int:

dp = [[[0 for _ in range(k + 1)] for _ in range(m + 1)] for _ in range(n)]

for j in range(1, m + 1):

dp[0][j][1] = 1

for i in range(1, n):

for kk in range(1, k + 1):

acc = 0

for j in range(1, m + 1):

dp[i][j][kk] = dp[i - 1][j][kk] * j + acc

acc += dp[i - 1][j][kk - 1]

ans = 0

for line in dp[n - 1]:

ans += line[k]

return ans % 1000000007