周赛笔记185


(1)重新格式化字符串

给你一个混合了数字和字母的字符串 s,其中的字母均为小写英文字母。
请你将该字符串重新格式化,使得任意两个相邻字符的类型都不同。也就是说,字母后面应该跟着数字,而数字后面应该跟着字母。
请你返回 重新格式化后 的字符串;如果无法按要求重新格式化,则返回一个 空字符串 。

class Solution:
    def reformat(self, s: str) -> str:
        if not s: return ""
        ln,ls=[],[]
        for i in s:
            if i.isdigit():ln.append(i)
            else:ls.append(i)
        a,b,ans=len(ln),len(ls),""
        if a==b+1:
            while ls:
                ans+=(ln.pop()+ls.pop())
            return ans+ln.pop()
        elif b==a+1:
            while ln:
                ans+=(ls.pop()+ln.pop())
            return ans+ls.pop()
        elif b==a:
            while ln:
                ans+=(ls.pop()+ln.pop())
            return ans
        else:
            return ""

(2)点菜展示表

给你一个数组 orders,表示客户在餐厅中完成的订单,确切地说, orders[i]=[customerNamei,tableNumberi,foodItemi] ,其中 customerNamei 是客户的姓名,tableNumberi 是客户所在餐桌的桌号,而 foodItemi 是客户点的餐品名称。
请你返回该餐厅的 点菜展示表 。在这张表中,表中第一行为标题,其第一列为餐桌桌号 “Table” ,后面每一列都是按字母顺序排列的餐品名称。接下来每一行中的项则表示每张餐桌订购的相应餐品数量,第一列应当填对应的桌号,后面依次填写下单的餐品数量。
注意:客户姓名不是点菜展示表的一部分。此外,表中的数据行应该按餐桌桌号升序排列。

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

小结

好难。。。

(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)生成数组

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

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)
  • 将上面提到的算法应用于 arrsearch_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

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录