扣 1418. 点菜展示表
题目描述
给你一个数组 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
- customerNamei 和 foodItemi 由大小写英文字母及空格字符 ' ' 组成。
- tableNumberi 是 1 到 500 范围内的整数。
解决方案
方法一：哈希表
我们首先分析题目需要我们做些什么：
- 我们需要将订单信息进行汇总，存放在一张数据表中作为答案返回；
- 数据表的第一行包含了所有的餐品名称，并且需要按照餐品名称的字典序排序，因此我们需要遍历订单信息，获取所有的餐品名称并对它们进行排序；
- 数据表的第一列包含了所有的餐桌桌号，并且需要按照桌号排序，因此我们需要遍历订单信息，获取所有的桌号并对它们进行排序；
- 数据表中间包含的信息为「某一桌下单的某一道菜的数量」。
我们可以使用两个哈希表来保存订单中的数据：
- 哈希表 nameSet 保存所有的餐品名称；
- 哈希表 foodsCnt 保存桌号及该桌点餐数量，点餐数量也用一个哈希表保存。
遍历订单并保存信息后，从 nameSet 中提取餐品名称，并按字母顺序排列；从 foodsCnt 中提取桌号，并按桌号升序排列。然后将餐品名称和桌号分别填入点菜展示表的第一行和第一列。对于表中的餐品数量，我们逐行填入，对于每一行，我们遍历餐品名称，在 foodsCnt 中查找对应的点餐数量，然后填入表格中对应位置。
C++
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;
}
};Java
class Solution {
public List<List<String>> displayTable(List<List<String>> orders) {
// 从订单中获取餐品名称和桌号，统计每桌点餐数量
Set<String> nameSet=new HashSet<String>();
Map<Integer, Map<String, Integer>> foodsCnt=new HashMap<Integer, Map<String, Integer>>();
for (List<String> order : orders) {
nameSet.add(order.get(2));
int id=Integer.parseInt(order.get(1));
Map<String, Integer> map=foodsCnt.getOrDefault(id, new HashMap<String, Integer>());
map.put(order.get(2), map.getOrDefault(order.get(2), 0) + 1);
foodsCnt.put(id, map);
}
// 提取餐品名称，并按字母顺序排列
int n=nameSet.size();
List<String> names=new ArrayList<String>();
for (String name : nameSet) {
names.add(name);
}
Collections.sort(names);
// 提取桌号，并按餐桌桌号升序排列
int m=foodsCnt.size();
List<Integer> ids=new ArrayList<Integer>();
for (int id : foodsCnt.keySet()) {
ids.add(id);
}
Collections.sort(ids);
// 填写点菜展示表
List<List<String>> table=new ArrayList<List<String>>();
List<String> header=new ArrayList<String>();
header.add("Table");
for (String name : names) {
header.add(name);
}
table.add(header);
for (int i=0; i < m; ++i) {
int id=ids.get(i);
Map<String, Integer> cnt=foodsCnt.get(id);
List<String> row=new ArrayList<String>();
row.add(Integer.toString(id));
for (int j=0; j < n; ++j) {
row.add(Integer.toString(cnt.getOrDefault(names.get(j), 0)));
}
table.add(row);
}
return table;
}
}C#
public class Solution {
public IList<IList<string>> DisplayTable(IList<IList<string>> orders) {
// 从订单中获取餐品名称和桌号，统计每桌点餐数量
ISet<string> nameSet=new HashSet<string>();
Dictionary<int, Dictionary<string, int>> foodsCnt=new Dictionary<int, Dictionary<string, int>>();
foreach (IList<string> order in orders) {
nameSet.Add(order[2]);
int id=int.Parse(order[1]);
Dictionary<string, int> dictionary=foodsCnt.ContainsKey(id) ? foodsCnt[id] : new Dictionary<string, int>();
if (dictionary.ContainsKey(order[2])) {
++dictionary[order[2]];
} else {
dictionary.Add(order[2], 1);
}
if (!foodsCnt.ContainsKey(id)) {
foodsCnt.Add(id, dictionary);
}
}
// 提取餐品名称，并按字母顺序排列
int n=nameSet.Count;
List<string> names=new List<string>();
foreach (string name in nameSet) {
names.Add(name);
}
names.Sort((a, b)=> string.CompareOrdinal(a, b));
// 提取桌号，并按餐桌桌号升序排列
int m=foodsCnt.Count;
List<int> ids=new List<int>();
foreach (int id in foodsCnt.Keys) {
ids.Add(id);
}
ids.Sort();
// 填写点菜展示表
IList<IList<string>> table=new List<IList<string>>();
IList<string> header=new List<string>();
header.Add("Table");
foreach (string name in names) {
header.Add(name);
}
table.Add(header);
for (int i=0; i < m; ++i) {
int id=ids[i];
Dictionary<string, int> cnt=foodsCnt[id];
IList<string> row=new List<string>();
row.Add(id.ToString());
for (int j=0; j < n; ++j) {
int val=cnt.ContainsKey(names[j]) ? cnt[names[j]] : 0;
row.Add(val.ToString());
}
table.Add(row);
}
return table;
}
}Golang
func displayTable(orders [][]string) [][]string {
// 从订单中获取餐品名称和桌号，统计每桌点餐数量
nameSet :=map[string]struct{}{}
foodsCnt :=map[int]map[string]int{}
for _, order :=range orders {
id, _ :=strconv.Atoi(order[1])
food :=order[2]
nameSet[food]=struct{}{}
if foodsCnt[id]==nil {
foodsCnt[id]=map[string]int{}
}
foodsCnt[id][food]++
}
// 提取餐品名称，并按字母顺序排列
n :=len(nameSet)
names :=make([]string, 0, n)
for name :=range nameSet {
names=append(names, name)
}
sort.Strings(names)
// 提取桌号，并按餐桌桌号升序排列
m :=len(foodsCnt)
ids :=make([]int, 0, m)
for id :=range foodsCnt {
ids=append(ids, id)
}
sort.Ints(ids)
// 填写点菜展示表
table :=make([][]string, m+1)
table[0]=make([]string, 1, n+1)
table[0][0]="Table"
table[0]=append(table[0], names...)
for i, id :=range ids {
cnt :=foodsCnt[id]
table[i+1]=make([]string, n+1)
table[i+1][0]=strconv.Itoa(id)
for j, name :=range names {
table[i+1][j+1]=strconv.Itoa(cnt[name])
}
}
return table
}Javascript
var displayTable=function(orders) {
// 从订单中获取餐品名称和桌号，统计每桌点餐数量
const nameSet=new Set();
const foodsCnt=new Map();
for (const order of orders) {
nameSet.add(order[2]);
const id=parseInt(order[1]);
const map=foodsCnt.get(id) || new Map();
map.set(order[2], (map.get(order[2]) || 0) + 1);
foodsCnt.set(id, map);
}
// 提取餐品名称，并按字母顺序排列
const n=nameSet.size;
const names=[];
for (const name of nameSet) {
names.push(name);
}
names.sort();
// 提取桌号，并按餐桌桌号升序排列
const m=foodsCnt.size;
const ids=[];
for (const id of foodsCnt.keys()) {
ids.push(id);
}
ids.sort((a, b)=> a - b);
// 填写点菜展示表
const table=[];
const header=[];
header.push("Table");
for (const name of names) {
header.push(name);
}
table.push(header);
for (let i=0; i < m; ++i) {
const id=ids[i];
const cnt=foodsCnt.get(id);
const row=[];
row.push(id.toString());
for (let j=0; j < n; ++j) {
row.push((cnt.get(names[j]) || 0).toString());
}
table.push(row);
}
return table;
};复杂度分析
为了便于进行复杂度分析，我们将所有字符串长度均视作常数。
- 时间复杂度：O(T+NlogN+MlogM+MN)。其中 T 是数组 orders 的长度，N 是数据表的列数（即餐品的数量），M 是数据表的行数（即餐桌的数量）。时间复杂度由以下几个部分组成：
- 遍历订单并保存信息的时间复杂度为 O(T)；
- 对餐品名称和餐桌编号分别进行排序，时间复杂度分别为 O(NlogN) 和 O(MlogM)；
- 将数据逐行填入表格，时间复杂度为 O(MN)。
- 空间复杂度：O(T + N + M) 。注意这里只计算额外的空间复杂度，不计入存放最终数据表（即答案）需要的空间。
本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系
我们日常工作中，商务招待很常见，大到公司总裁、总经理，小到部门职员，都会涉及到，掌握一点招待技巧，尤其是点菜技巧，肯定会让别人寡目相看，小编就从以下几点浅谈下点菜技巧，就当我是抛砖引玉了，您可以在评论区留言，我们共同学习，共同进步。
< class="pgc-img">一、摸好底，即做好点菜前准备工作
在我们正式点菜前，或者更早一些，要充分做好一些准备工作，如如：可先行了解下就餐的餐馆的特点，属于哪个菜系，这个菜系，有哪些名菜或目前流行菜式。最重要的是有必要问清同席者忌口、有没有民族习惯或其它特殊忌讳（尤其是了解所要招待的重要客人的喜好），因为现在的商务招待，并不仅仅是吃饭那么简单，而是有一定“目的”的。
< class="pgc-img">二、算好量，即点菜的数量
这个数量非常关键，点多了浪费，点少了不够吃，显得小气，这个数量必须拿捏到位。其实原则很简单，可根据人数和费用合理选择菜肴，基本上保证一人一菜，外加一汤和一两样点心就可以了，如果多了，也不会显得浪费，但是少了，略加一两个菜就行了，主食可以不算进数量内的。
< class="pgc-img">三、点好菜，即点菜的细节
至于点什么菜呢？也很简单：荤素搭配，凉热搭配，五味俱全等。
1、荤素搭配，荤菜和素菜要合理搭配，比如：一桌12菜来说，可以6荤菜、6素菜，或者8荤菜、4素菜，荤菜有：鸡肉、鸭肉、鱼肉、羊肉、牛肉、驴肉等等，具体看用餐者喜好。
< class="pgc-img">2、凉热搭配，凉菜和热菜要合理搭配，比如：一桌12菜来说，最好是4凉菜，8热菜，尽量凉菜少于热菜。
< class="pgc-img">3、五味俱全，还要注意口味搭配是否重复，甜酸、麻辣、盐酥等口味要适当搭配，当然这个要看用餐者喜好，不能吃辣的，就尽量别点辣菜。
< class="pgc-img">4、尽量点特色菜、招牌菜
咨询下所在饭店服务生，可尽量点些特色菜肴、招牌菜，这样也会给客人“不虚此行”的好感。
< class="pgc-img">5、年龄搭配
注意用餐者的年龄。比如：
老年居多的话，要点质地软嫩、口味清淡、低脂肪的菜肴；
中青年多的话要点味道浓香、油脂较多的菜；
女客多的话要多点酸甜菜肴或甜味精致小点心，美女们肯定百吃不厌。
< class="pgc-img">6、注意时节，健康饮食
点菜时应时顺季菜肴，可点些当地有特色的当季菜肴，古人云：“春多酸，夏多苦，秋多辛，冬多咸，调以滑甘”是有道理的。
< class="pgc-img">好了，以上就是今天分享的点菜技巧了，简单概括就是：摸好底、算好量、点好菜，写到这里，我的肚子已经咕咕在叫了。
期待您的支持，您的支持是我继续写作的动力源泉！也期待你在评论区留言，分享下您的一些小技巧，我们一起成长！
< class="pgc-img">满汉全席
有一家饭店用上了电脑“点菜”这个新方法。电脑“点菜”，是NCR电脑公司开发出来的一套点菜系统。这种机器大小如一本中型日记本，工作人员握在手中，根据客人需要，把所点菜式按编号按键送入机器内，再把安装在附近的插头插上，与主机连接，这时所点的菜单会极快地输送到主机、厨房和柜台。厨房按菜单做菜，柜台亦按菜单计算价格，使厨房能达到3分钟内上菜的作业速度，而柜台也能迅速而准确地计算价格，以及在一天的营业结束时迅速结账。
这种电脑点菜系统，最大的好处是可以帮助中央厨房清点每一天的出货量，计算每一天的人货量，以及时补货，避免传统的靠厨房人员凭经验判断的误差。这种系统在管理层次上有三项好处:
(1) 消除各种人为弊端，出纳及服务人员根本无法做假账;
(2)降低服务人员人事费用，以电脑代劳，人手自然可以减少;
< class="pgc-img">(3)立即明白损益情况，不必等到月底结账。这样的电脑点菜系统，是近年来以经营餐厅起家的蔡礼乐集团首先在台湾推出的，以对抗麦当劳在台湾饮食业影响
