周赛笔记185

1. 重新格式化字符串

class Solution:
    def reformat(self, s: str) -> str:
        a, b = [], []
        for c in s:
            if c.isdigit():
                a.append(c)
            else:
                b.append(c)

        if abs(len(a)-len(b)) > 1:
            return ""
        elif len(a) >= len(b):
            return "".join(list(i for row in zip_longest(a,b,fillvalue="") for i in row))
        else:
            return "".join(list(i for row in zip_longest(b,a,fillvalue="") for i in row))

2. 点菜展示表

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        fs=set()
        ts=collections.defaultdict(lambda:collections.defaultdict(int))
        for _ ,t,f in orders:
            fs.add(f)
            ts[int(t)][f]+=1
        ans=[["Table"]]
        for f in sorted(list(fs)):  #菜名
            ans[0].append(f)
        for t in sorted(list(ts.keys())):  #桌号
            ans.append([str(t)])   
            for i in range(1,len(ans[0])):   #份数
                ans[-1].append(str(ts[t][ans[0][i]]))
        return ans

class Solution:
    def displayTable(self, orders: List[List[str]]) -> List[List[str]]:
        d = defaultdict(list)
        vis_n = set()
        vis_food = set()

        for name, n, food in orders:
            d[n].append(food)
            vis_n.add(n)
            vis_food.add(food)

        vis_n = list(vis_n)
        vis_n.sort(key = lambda x:int(x))
        vis_food = list(vis_food)
        vis_food.sort()

        res = [["Table"]+[food for food in vis_food]]
        for i,n in enumerate(vis_n):
            c = Counter(d[n])
            res.append([n]+[str(c.get(food, 0)) for food in vis_food])

        return res

3. 数青蛙

给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 “croak” ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
注意：要想发出蛙鸣 “croak”，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。
如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。

class Solution:
    def minNumberOfFrogs(self, cr: str) -> int:
        pre = [0] * 5
        res = 0
        for c in cr:
            if c == 'c':
                pre[0] += 1
            if c == 'r':
                pre[0] -= 1
                pre[1] += 1
            if c == 'o':
                pre[1] -= 1
                pre[2] += 1
            if c == 'a':
                pre[2] -= 1
                pre[3] += 1
            if c == 'k':
                pre[3] -= 1
            if any(c < 0 for c in pre):
                return -1
            res = max(res, sum(pre))
        
        if any(c != 0 for c in pre):
            return -1
        return res

4. 生成数组

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

maximum_value = -1
maximum_index = -1
search_cost = 0
for (i=0;i<n;i++) {
    if (maximum_value < arr[i]){
        maximum_value = arr[i]
        maximum_index = i
        search_cost+=1
    }
}
return maximum_index

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

• arr 中有 n 个整数。
• 1 <= arr[i] <= m 其中 (0 <= i < n) 。
• 将上面提到的算法应用于 arr ，search_cost 的值等于 k 。
  返回上述条件下生成数组 arr 的 方法数 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        mod = 10 ** 9 + 7

        dp = [[[0] * (k + 1) for _ in range(m + 1)] for _ in range(n)]
        
        for i in range(1, m + 1):
            dp[0][i][1] = 1
        
        for i in range(1, n):
            for j in range(1, m + 1):
                for pre in range(1, m + 1):
                    if pre >= j:
                        for kk in range(k + 1):
                            dp[i][pre][kk] += dp[i - 1][pre][kk]
                    else:
                        for kk in range(1, k + 1):
                            dp[i][j][kk] += dp[i - 1][pre][kk - 1]
        res = 0
        for i in range(m + 1):
            res += dp[-1][i][k]
        return res % mod