目录

重新格式化字符串

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reformat-the-string

示例

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

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

我的思路

统计字符串 s 中的字母和数字个数。如果两者绝对差值超过1，则必然会有两个数字或字母相邻，直接返回空串即可。
数量多的一方必然会包办生成字符串的两个边界。

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution:
    def reformat(self, s: str) -> str:
        digits = []
        chs = []
        for ch in s:
            if ch.isalpha():
                chs.append(ch)
            if ch.isdigit():
                digits.append(ch)
        n = len(chs)
        m = len(digits)
        if abs(n - m) > 1:
            return ""
        res = ""
        if n > m:
            while chs:
                res += chs.pop()
                try:
                    res += digits.pop()
                except:
                    continue
        else:
            while digits:
                res += digits.pop()
                try:
                    res += chs.pop()
                except:
                    continue
        return res

点菜展示表

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant

示例

输入：
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，用列表保存菜单并用字典保存每桌点的菜。
对菜单列表用 sorted() 排成字典序。 遍历点单字典的，统计每桌对菜单列表的点单数。用匿名函数对桌号进行排序。

我的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def displayTable(self, orders):
        n = len(orders)
        menus = list()
        table = dict()
        for order in orders:
            if order[2] not in menus:
                menus.append(order[2])
            try:
                table[int(order[1])] += [order[2]]
            except:
                table[int(order[1])] = [order[2]]
        menus = sorted(menus)
        res = list()
        res.append(["Table"] + menus)
        tmp = list()
        for k, v in table.items():
            cur = list()
            cur.append(k)
            for menu in menus:
                cur.append(v.count(menu))
            tmp.append(cur)
        tmp = sorted(tmp, key=lambda x:x[0])
        for cur in tmp:
            res.append([str(x) for x in cur])
        return res

数青蛙

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-number-of-frogs-croaking

示例

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

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

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

别人的思路

在遍历croakOfFrogs的过程中维护croak五个字母的个数。

  • 如果遇到当前字母，则必有其前面的字母转移过来，前面的字母数减1。如遇到r，则必由c转移过来，因此c的个数减1。
  • 如遇到c，先去消耗k，如果k没了，则需要新的青蛙。
  • 遍历过程中若c,r,o,a的数量不够，则存在无效的croak，退出遍历

遍历结束后，检查c,r,o,a的数量是否被消耗完，如果没有则说明有无效croak，返回-1

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution:
    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
        c, r, o, a, k = 0, 0, 0, 0, 0
        res = 0
        for ch in croakOfFrogs:
            if ch == 'c':
                if k > 0:
                    k -= 1
                else:
                    res += 1
                c += 1
            elif ch == 'r':
                c -= 1
                r += 1
            elif ch == 'o':
                r -= 1
                o += 1
            elif ch == 'a':
                o -= 1
                a += 1
            elif ch == 'k':
                a -= 1
                k += 1
            
            if c < 0 or r < 0 or o < 0 or a < 0:
                break
        
        if c != 0 or r != 0 or o != 0 or a != 0:
            return -1
        return res

生成数组

给你三个整数 n、m 和 k 。下图描述的算法用于找出正整数数组中最大的元素。
算法
请你生成一个具有下述属性的数组 arr ：

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/build-array-where-you-can-find-the-maximum-exactly-k-comparisons

示例

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

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

别人的思路

三维DP。
dp[n][k][i] 代表长度为 n，搜索代价为k，最大值为 i的数组的数目。sum(dp[n][k][i]), 1 <= i <= m 即为所求。

边界条件：

  • dp[0][k][i] = 0, 1 <= i <= m # 因为 1 <= n <= 50, 故长度为0的数组个数为0
  • dp[n][0][i] = 0, 1 <= i <= m # 搜索代价为0，即搜索不到最大值的数组个数为0
  • dp[n][k][0] = 0 # 因为数组中最小值为1，不存在0，故最大值为0的数组个数为0
  • dp[1][1][i] = 1, 1 <= i <= m # 长度为1且搜索代价为1，对每个最大值为i的数组个数都只有1个

设一个数组的长度为 l, 最大值的搜索代价为 c，最大值为 p，那么其数目为 dp[l][c][p]。那么将一个新数 num 加入该数组有两种情况:

  • num比原数组的所有数都大，加入num后num成为了新数组的最大值，新数组搜索代价加1，长度也加1。故有 dp[l+1][c+1][num] = sum(dp[l][c][j]), 1 <= j <= num - 1
  • num小于等于原数组的最大值，因此新数组的最大值保持不变，因此搜索代价也保持不变，长度加1。因为 1 <= num <= p 共有 p 种, 例如原数组为[[1],[2]]这2种, 那么新数组有[[1,1],[1,2],[2,1],[2,2]]这4种。故有 dp[l+1][c][p] = dp[l][c][p] * p。

从上面可推出转移方程为：

  • dp[l][c][p] = sum(dp[l-1][c-1][j]) + dp[l-1][c][p] * p, 1 <= j <= p - 1

别人的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

        def dfs(l, c, p):
            if self.dp[l][c][p] != -1:
                return self.dp[l][c][p]
            if l == 0 or c == 0 or p == 0:
                self.dp[l][c][p] = 0
                return 0
            if l == 1 and c == 1:
                self.dp[l][c][p] = 1
                return 1
            res = 0
            for j in range(1, p):
                res += dfs(l - 1, c - 1, j)
                res %= 10 ** 9 + 7
            res += dfs(l - 1, c, p) * p
            res %= 10 ** 9 + 7
            self.dp[l][c][p] = res
            return res

        res = 0
        for i in range(1, m + 1):
            res += dfs(n, k, i)
            res %= 10 ** 9 + 7
        return res

总结

依旧只AC了前两道，排位1153/5002。 这回有字节的周边奖品，以及前200名有字节内推机会，所以参赛的人数比较多。
最后一题三维DP还有很多弄不清的地方。