leetcode解题思路分析（一百六十四）1418 - 1424 题

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

读懂题意后按需要设计结构体即可。

class Solution {
public:vector<vector<string>> displayTable(vector<vector<string>> &orders) {// 从订单中获取餐品名称和桌号，统计每桌点餐数量unordered_set<string> nameSet;unordered_map<int, unordered_map<string, int>> foodsCnt;for (auto &order : orders) {nameSet.insert(order[2]);int id = stoi(order[1]);++foodsCnt[id][order[2]];}// 提取餐品名称，并按字母顺序排列int n = nameSet.size();vector<string> names;for (auto &name : nameSet) {names.push_back(name);}sort(names.begin(), names.end());// 提取桌号，并按餐桌桌号升序排列int m = foodsCnt.size();vector<int> ids;for (auto &[id, _] : foodsCnt) {ids.push_back(id);}sort(ids.begin(), ids.end());// 填写点菜展示表vector<vector<string>> table(m + 1, vector<string>(n + 1));table[0][0] = "Table";copy(names.begin(), names.end(), table[0].begin() + 1);for (int i = 0; i < m; ++i) {int id = ids[i];auto &cnt = foodsCnt[id];table[i + 1][0] = to_string(id);for (int j = 0; j < n; ++j) {table[i + 1][j + 1] = to_string(cnt[names[j]]);}}return table;}
};

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

遍历一遍

class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {if (croakOfFrogs.size() % 5 != 0) {return -1;}int res = 0, frogNum = 0;vector<int> cnt(4);unordered_map<char, int> mp = {{'c', 0}, {'r', 1}, {'o', 2}, {'a', 3}, {'k', 4}};for (char c : croakOfFrogs) {int t = mp[c];if (t == 0) {cnt[t]++;frogNum++;if (frogNum > res) {res = frogNum;}} else {if (cnt[t - 1] == 0) {return -1;}cnt[t - 1]--;if (t == 4) {frogNum--;} else {cnt[t]++;}}}if (frogNum > 0) {return -1;}return res;}
};

1420. 生成数组
      请你构建一个具有以下属性的数组 arr ：
      arr 中包含确切的 n 个整数。
      1 <= arr[i] <= m 其中 (0 <= i < n) 。
      将上面提到的算法应用于 arr 之后，search_cost 的值等于 k 。
      返回在满足上述条件的情况下构建数组 arr 的 方法数量 ，由于答案可能会很大，所以 必须 对 10^9 + 7 取余。

用动态规划解

class Solution {
private:int f[51][51][101];static constexpr int mod = 1000000007;public:int numOfArrays(int n, int m, int k) {// 不存在搜索代价为 0 的数组if (!k) {return 0;}memset(f, 0, sizeof(f));// 边界条件，所有长度为 1 的数组的搜索代价都为 1for (int j = 1; j <= m; ++j) {f[1][1][j] = 1;}for (int i = 2; i <= n; ++i) {// 搜索代价不会超过数组长度for (int s = 1; s <= k && s <= i; ++s) {for (int j = 1; j <= m; ++j) {f[i][s][j] = (long long)f[i - 1][s][j] * j % mod;for (int j0 = 1; j0 < j; ++j0) {f[i][s][j] += f[i - 1][s - 1][j0];f[i][s][j] %= mod;}}}}// 最终的答案是所有 f[n][k][..] 的和// 即数组长度为 n，搜索代价为 k，最大值任意int ans = 0;for (int j = 1; j <= m; ++j) {ans += f[n][k][j];ans %= mod;}return ans;}
};

1422. 分割字符串的最大得分
      给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

遍历到尾部再回来就行

class Solution {
public:int maxScore(string s) {int max_ret = 0, cnt_now = 0;for (auto c : s) {if (c =='0') {cnt_now++;}}for (int i = s.size() - 1; i >= 1; i --) {if (s[i] == '1')cnt_now++;elsecnt_now--;max_ret = max(cnt_now, max_ret);}return max_ret;}
};

1423. 可获得的最大点数
      几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。你的点数就是你拿到手中的所有卡牌的点数之和。给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

逆向思维：两边拿，剩下的一定是个连续的数组。那滑动窗口解题即可。

class Solution {
public:int maxScore(vector<int>& cardPoints, int k) {auto size = cardPoints.size();auto wnd_len = size - k;int left = 0, right = 0;auto now_val = 0;int  min_val = INT_MAX;int  total_cnt = 0;for ( ; right < wnd_len; right++) {now_val += cardPoints[right];}min_val = now_val;total_cnt = now_val;while (right <= size - 1) {now_val -= cardPoints[left];now_val += cardPoints[right];total_cnt += cardPoints[right];min_val = min(min_val, now_val);left++;right++;}return total_cnt - min_val;}
};

1424. 对角线遍历 II
      给你一个列表 nums ，里面每一个元素都是一个整数列表。请你依照下面各图的规则，按顺序返回 nums 中对角线上的整数。

斜线的特点是x+y相等

class Solution {
public:vector<int> findDiagonalOrder(vector<vector<int>>& nums) {map<int, vector<int>> mp;/* 从最后一行开始存储数据, 利用map有序的特点 */for (int i = nums.size() - 1; i >= 0; i--) {for (int j = 0; j < nums[i].size(); j++) {mp[i + j].push_back(nums[i][j]);}}vector<int> ans;/* 顺序输出即为题目要求的 */for (auto &[k, v] : mp) {for (auto val : v) {ans.push_back(val);}}return ans;}
};