LeetcodeWk185

写在前面

太久没有做过周赛题了,偶尔来做一做,感觉真是越来越菜了

第185 场周赛

题目

A. 重新格式化字符串

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

1
2
输入:s = "covid2019"
输出:"c2o0v1i9d"

示例 5:

1
2
输入:s = "ab123"
输出:"1a2b3"

提示:

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

我们不难发现只有数字和字符出现的次数之差小于等于1时,才有答案,然后直接构造即可

B. 点菜展示表

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: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:

1
2
3
4
5
输入: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:

1
2
输入: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
  • customerNameifoodItemi 由大小写英文字母及空格字符 ' ' 组成。
  • tableNumberi1500 范围内的整数。

C. 数青蛙

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

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

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

示例 1:

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

示例 2:

1
2
3
4
5
输入:croakOfFrogs = "crcoakroak"
输出:2
解释:最少需要两只青蛙,“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"

示例 3:

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

示例 4:

1
2
输入:croakOfFrogs = "croakcroa"
输出:-1

提示:

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

我们直接考虑 一个青蛙会有几个状态

  • 蛙鸣完毕,可以重新蛙鸣
  • 蛙鸣’c’
  • 蛙鸣’r’
  • 蛙鸣’o’
  • 蛙鸣’a’
  • 蛙鸣’k’,进入空闲区域

每次都从上一个状态找一个,如果没有的话说明是非法的

蛙鸣完k之后,进入蛙鸣完毕状态,我们可以定义一个变量来保存空闲的青蛙,每次开始蛙鸣’c’时,我们就先看是否有空闲,否则再创建新的青蛙

最后再判断一下即可

D. 生成数组

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

1
2
3
4
5
6
7
8
9
10
11
12
maximum_value = -1;
maximum_index = -1;
search_cost = 0;
n = arr.length;
for(int i = 0; i < n; i++){
if (maximum_value < arr[i]){
maximum_value < arr[i];
maximum_index = i;
search_cost = search_csot+1
}
}
return maximum_index;

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

1
2
输入:n = 37, m = 17, k = 7
输出:418930126

提示:

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

代码的意思非常简单,就是再找最大值的过程中,会得到几次当前的最大值。

我们可以考虑通过枚举最大值是多少来计算答案

然后我们发现这个可以通过dp来做

我们可以定义这样一个表dp[n][m][k], 表示考虑到第n个位置时,最大值为m的时候,已经得到k次最大值的数组个数

不难发现答案为:

对于所有的初始状态,也就是dp[1][m][1]=1

然后我们进行转移,第一种是最大值变化,第二种是不变化的

  • $dp[n][m][k]=\sum\nolimits_{i=1}^{m-1}dp[n-1][i][k-1]+\sum\nolimits_{i=1}^{m}dp[i][m][k]$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define LL long long
class Solution {
public:
LL dp[51][101][501];
LL MOD=1e9+7;
int numOfArrays(int n, int m, int k) {
for(int i=1;i<=m;i++) dp[1][i][1]=1;
for(int i=2;i<=n;i++){
for(int mx=1;mx<=m;mx++){
for(int t=1;t<=k;t++){
for(int v=1;v<=mx;v++){
// mx 不变
dp[i][mx][t]=(dp[i][mx][t]+ dp[i-1][mx][t])%MOD;
// mx 变
if(v!=mx)dp[i][mx][t]=(dp[i][mx][t]+ dp[i-1][v][t-1])%MOD;
}
}
}
}
LL ans=0;
for(int i=1;i<=m;i++) ans = (ans + dp[n][i][k])%MOD;
return (int)(ans);
}
};

总结

太久没做了,还是有些生疏了,总是写错代码