On the shoulders of giants.

weekly-contest-185

重新格式化字符串

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

示例 5:

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

提示:

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

先统计个数,作为大前提。

如果两类字符同样多,那么任意字符开始然后交替出现。

否则让多的那类字符开始然后交替出现。

时间复杂度:\(O(n)\)

class Solution {
public:
    string reformat(string s) {
        string num = "";
        string cha = "";
        for(auto c : s) {
            if('0' <= c && c <= '9') num += c;
            else cha += c;
        }
        int dx = num.length() - cha.length();
        if(1 < abs(dx)) return "";
        string result = "";
        for(int i = 0; i < s.length(); i++) {
            if(dx < 0) {
                result += (i & 1 ? num[i >> 1] : cha[i >> 1]);
            } else {
                result += (i & 1 ? cha[i >> 1] : num[i >> 1]);
            }
            
        }
        return result;
    }
};

点菜展示表

给你一个数组 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" 

示例 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"

示例 3:

输入: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 范围内的整数。
题解

orders 做关于 tableNumber 从小到大排序。

然后对每个菜从小到大标号,最后直接模拟。

时间复杂度:\(O(n\log n)\)

class Solution {
public:
    static bool cmp(const vector<string>& a, const vector<string>& b) {
        return stoi(a[1]) < stoi(b[1]);
    }
    vector<vector<string>> displayTable(vector<vector<string>>& orders) {
        set<string> s;
        map<string, int> h;
        int total = 0;
        vector<string> tital;
        for(auto order : orders) s.insert(order[2]);
        tital.push_back("Table");
        for(auto name : s) tital.push_back(name), h[name] = ++total;
        sort(orders.begin(), orders.end(), cmp);
        vector<vector<string>> result;
        result.push_back(tital);
        for(int i = 0, k = 0; i < orders.size(); i++) {
            if(!k || result[k][0] != orders[i][1]) {
                result.push_back(vector<string> (total + 1, "0"));
                result[++k][0] = orders[i][1];
            }
            string& c = result[k][h[orders[i][2]]];
            c = to_string(stoi(c) + 1);
        }
        return result;
    }
};

数青蛙

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

提示:

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

我们分别用 c,r,o,a,k 来记录从 开始叫 到 叫到该字符 的青蛙个数。

然后直接模拟过程。

时间复杂度:\(O(n)\)

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        int c = 0, r = 0, o = 0, a = 0, k = 0, total = 0;
        for(auto ch : croakOfFrogs) {
            if(ch == 'c') {
                (0 < k) ? k-- : total++;
                c++;
            } else if(ch == 'r') {
                c--, r++;
            } else if(ch == 'o') {
                r--, o++;
            } else if(ch == 'a') {
                o--, a++;
            } else if(ch == 'k') {
                a--, k++;
            }
            if(c < 0 || r < 0 || o < 0 || a < 0 || k < 0)
                return -1;
        }
        if(c || r || o || a) return -1;
        else return total;
    }
};

生成数组

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

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

  • arr 中有 n 个整数。
  • 1 <= arr[i] <= m 其中 (0 <= i < n)
  • 将上面提到的算法应用于 arrsearch_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]

示例 2:

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

示例 3:

输入: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 取余

示例 5:

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

提示:

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

动态规划,设 \(dp_{x,y,k}\) 表示长度为 n 的数组,元素最大值为 m,交换了 k 次的数组方案数。

如果最后新来的数是全局最大值,那么有:\(\sum_{i=1}^{y-1} dp_{x-1,i,t-1}\)

如果最后新来的数不是全局最大值,那么有:\(y\cdot dp_{x-1,y,k}\) ,表示最后一个数有 1~y 共 y 种可能。

两者的和即为 \(dp_{x,y,k}\) 的解。

时间复杂度:\(O(nm^2k)\)

const int MOD = 1E9 + 7;
class Solution {
public:
    int numOfArrays(int n, int m, int k) {
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (m + 1, vector<int> (k + 1)));
        for(int i = 1; i <= m; i++) dp[1][i][1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                for(int t = 1; t <= min(k, i); t++) {
                    for(int x = 1; x < j; x++)
                        dp[i][j][t] = (dp[i][j][t] + dp[i - 1][x][t - 1]) % MOD;
                    dp[i][j][t] = (dp[i][j][t] + 1ll * j * dp[i - 1][j][t]) % MOD;
                }
            }
        }
        int result = 0;
        for(int i = 1; i <= m; i++) result = (result + dp[n][i][k]) % MOD;
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注