写点什么

【LeetCode】点菜展示表 Java 题解

用户头像
HQ数字卡
关注
发布于: 1 小时前

题目描述

给你一个数组 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,Water3 ,0 ,2 ,1 ,05 ,0 ,1 ,0 ,110 ,1 ,0 ,0 ,0对于餐桌 3:David 点了 "Ceviche" 和 "Fried Chicken",而 Rous 点了 "Ceviche"而餐桌 5:Carla 点了 "Water" 和 "Ceviche"餐桌 10:Corina 点了 "Beef Burrito"
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/display-table-of-food-orders-in-a-restaurant著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 找个题目提干比较长,需要耐心阅读。仔细阅读分析之后,发现这个题目思维逻辑不难,我们需要分别记录 food, table, tableFood 数量并快速取出。

  • 代码中使用了 TreeSet 数据结构。我们来看一下 TreeSet 的说明。是基于 TreeMap 实现,提供 log(n) 的操作时间复杂度。


A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).
复制代码


  • TreeMap 是基于 Red-Black tree 实现。


A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.
复制代码

代码

public List<List<String>> displayTable(List<List<String>> orders) {        Set<String> foods = new TreeSet<>();         Set<String> tableNumbers = new TreeSet<>(new Comparator<String>() {            @Override            public int compare(String o1, String o2) {                return Integer.valueOf(o1) - Integer.valueOf(o2);            }        }); 
Map<String ,Map<String, Integer>> tableFoodsNumber = new HashMap<>(); for (List<String> item : orders) { String tableNumber = item.get(1); String foodItem = item.get(2);
if (!tableNumbers.contains(tableNumber)) { tableNumbers.add(tableNumber); } if (!foods.contains(foodItem)) { foods.add(foodItem); }
Map<String, Integer> foodsNumber; if (tableFoodsNumber.containsKey(tableNumber)) { foodsNumber = tableFoodsNumber.get(tableNumber); } else { foodsNumber = new HashMap<>(); }
foodsNumber.put(foodItem, foodsNumber.getOrDefault(foodItem, 0) + 1); tableFoodsNumber.put(tableNumber, foodsNumber); }
List<List<String>> ans = new ArrayList<>(); List<String> first = new ArrayList<>(); first.add("Table"); for (String food : foods) { first.add(food); } ans.add(first);
for (String tableNumber : tableNumbers) { List<String> temp = new ArrayList<>(); for (String i : first) { if ("Table".equals(i)) { temp.add(tableNumber); } else { temp.add(String.valueOf(tableFoodsNumber.get(tableNumber).getOrDefault(i, 0))); } } ans.add(temp); }
return ans; }
复制代码

总结

  • 上述代码的时间复杂度是 O(n), 空间复杂度是 O(n * n)

  • 坚持每日一题,加油!

发布于: 1 小时前阅读数: 3
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】点菜展示表Java题解