This article is participating in Python Theme Month. See the link to the event for more details
Topic describes
This is the 1418 order presentation table from LeetCode, on medium difficulty.
Tag: data structure, hash table, red-black tree
Give you the orders an array, said clients completed orders in the restaurant, specifically, the orders [I] = [customerNamei tableNumberi, foodItemi], including customerNamei is the customer’s name, TableNumberi is the number of the table at which the customer is sitting, and foodItemi is the name of the order.
Please return to the menu of the restaurant. In this Table, the first action in the Table is the title, with the first column being the Table number “Table”, and each column following it is the alphabetical name of the meal. The items in the next row represent the number of items ordered for each table, with the table number in the first column followed by the number of items ordered.
Note: Customer names are not part of the order table. In addition, the data rows in the table should be arranged in ascending order by table number.
Example 1:
Input: orders = [["David","3","Ceviche"],["Corina","10","Beef Burrito"],["David","3","Fried Chicken "], [" Carla ", "5", "Water"], [" Carla ", "5", "Ceviche"], [" Rous ", "3", "Ceviche"]] output: [["Table","Beef Burrito","Ceviche","Fried Chicken ", "Water"], [" 3 ", "0", "2", "1", "0"], [" 5 ", "0", "1", "0", "1"], [" 10 ", "1", "0" and "0" and "0"]] : order display table as shown below: Table,Beef Burrito,Ceviche,Fried Chicken,Water 3,0,2,1,0 5,0,1,0,1 10,1,0,0,0 David ordered "Ceviche" and "Fried Chicken, "while Rous ordered "Ceviche," and Table 5: Carla ordered "Water" and "Ceviche, "table 10: Corina ordered Beef Burrito.Copy the codeExample 2:
Input: orders = [["James","12","Fried Chicken"],["Ratesh","12","Fried Chicken"],["Amadeus","12","Fried Chicken "], [" Adam ", "1", "Canadian Waffles"], [" Brianna ", "1", "Canadian Waffles"]] output: [[" Table ", "Canadian Waffles", "Fried Chicken"], [" 1 ", "2", "0"], [" 12 ", "0", "3"]] : the Table 1: Adam and Brianna both ordered Canadian Waffles, and table 12: James, Ratesh and Amadeus all ordered Fried Chicken.Copy the codeExample 3:
Input: the orders = [[" Laura ", "2", "Bean Burrito"], [" Jhon ", "2", "Beef Burrito"], [" Melissa ", "2", "Soda"]] output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]Copy the codeTip:
- 1 <= orders.length <= 5 *
- orders[i].length == 3
- 1 <= customerNamei.length, foodItemi.length <= 20
- CustomerNamei and foodItemi consist of upper and lower case letters and the space character “”.
- TableNumberi is an integer in the range 1 to 500.
Fundamental analysis
This is a simulation that considers “data structure application” versus “simple design”.
We can deduce the data structure storage format from the final “result”.
The final “result” consists of two parts:
titleBy:“Table” + sort the items to remove weightcomposition- Content: table number + quantity of each item
Based on this, it is not difficult to design a Set to store the content related to title and a Map to store the content related parts.
Some keys to be remapped are table numbers. In order to quickly index the current table number “Quantity of a certain meal”, you need to set another layer of Map. That is, the final storage format is table number: {food: number}.
HashSet & HashMap
With the basic analysis, we can use the most general HashSet and HashMap implementations.
Since a HashSet is based on a HashMap, and the underlying data structure implementation of a HashMap is a hash table, we need to manually order the answers when we construct them.
Java code:
class Solution {
public List<List<String>> displayTable(List<List<String>> os) {
List<List<String>> ans = new ArrayList<>();
// Table number: {food: number}
Map<Integer, Map<String, Integer>> tm = new HashMap<>();
// Meal (used to construct title)
Set<String> ts = new HashSet<>();
for (List<String> o : os) {
String c = o.get(0), t = o.get(1), f = o.get(2);
Integer tidx = Integer.parseInt(t);
ts.add(f);
Map<String, Integer> map = tm.getOrDefault(tidx, new HashMap<>());
map.put(f, map.getOrDefault(f, 0) + 1);
tm.put(tidx, map);
}
int n = tm.size() + 1, m = ts.size() + 1;
// Construct title & manual sort
List<String> foods = new ArrayList<>(ts);
Collections.sort(foods);
List<String> title = new ArrayList<>();
title.add("Table");
title.addAll(foods);
ans.add(title);
// Construct content & manually sort
List<Integer> tables = new ArrayList<>(tm.keySet());
Collections.sort(tables);
for (int tidx : tables) {
Map<String, Integer> map = tm.get(tidx);
List<String> cur = new ArrayList<>();
cur.add(tidx + "");
for (String food : foods) {
cur.add(map.getOrDefault(food, 0) + "");
}
ans.add(cur);
}
returnans; }}Copy the codePython3 code:
class Solution:
def displayTable(self, orders: List[List[str]]) - >List[List[str]] :
ans = []
# Table number: {food: number} (used to construct content)
tm = defaultdict(lambda: defaultdict(int))
# Meal (used to construct title)
ts = set(a)for c,t,f in orders:
tidx = int(t)
ts.add(f)
tm[tidx][f] += 1
n, m = len(tm) + 1.len(ts) + 1
# Construct title & manual sort
foods = sorted(ts)
title = []
title.append("Table")
title += foods
ans.append(title)
# Construct content & manually sort
for tidx in sorted(tm.keys()):
cur = []
cur.append(str(tidx))
for food in foods:
cur.append(str(tm[tidx][food]))
ans.append(cur)
return ans
Copy the code- Time complexity:
HashSet和HashMapThe basic operation is
. The pre-processing complexity of all orders is
; The number of tables after weight removal is
, the number of meals is
, the complexity of sorting the two is respectively
和
; Construct answer complexity is
; The final complexity is
- Space complexity: O(r+c+r∗c)O(R +c+r * c)O(R + C +r∗c)
TreeSet & TreeMap
Similar to the relationship between HashSet and HashMap, TreeSet is based on TreeMap, whose underlying data structure implementation is a red-black tree.
Thanks to Java’s “interface Oriented Programming (IOP)” design, we can easily fit into solution 1HashSetreplaceTreeSetWill,HashMapreplaceTreeMap, and remove the manual sorting related code to get our solution 2.
Simplify our implementation by using TreeMap’s default collation rules (numerical ascending, non-numerical lexicographical ascending).
Note, however, that with the internal ordering nature of TreeMap, tuning may occur on each insert, whereas the solution is to use the collections. sort to sort once. As for the non-custom collections. sort, it is implemented based on Arrays.sort, which comprehensively determines the final sorting scheme according to “array size”, “whether the array itself is roughly ordered” and other factors. In the case of completely random data, the performance efficiency is much better than that of TreeMap’s multiple adjustments. But both are O(nlogn)O(n\log{n})O(nlogn).
Therefore, in the case that all data is given “offline” in advance, solution 1 is actually more recommended.
Java code:
class Solution {
public List<List<String>> displayTable(List<List<String>> os) {
List<List<String>> ans = new ArrayList<>();
// Table number: {food: number}
Map<Integer, Map<String, Integer>> tm = new TreeMap<>();
// Meal (used to construct title)
Set<String> ts = new TreeSet<>();
for (List<String> o : os) {
String c = o.get(0), t = o.get(1), f = o.get(2);
Integer tidx = Integer.parseInt(t);
ts.add(f);
Map<String, Integer> map = tm.getOrDefault(tidx, new HashMap<>());
map.put(f, map.getOrDefault(f, 0) + 1);
tm.put(tidx, map);
}
int n = tm.size() + 1, m = ts.size() + 1;
/ / structure of the title
List<String> title = new ArrayList<>();
title.add("Table");
title.addAll(ts);
ans.add(title);
// Construct content
for (int tidx : tm.keySet()) {
Map<String, Integer> map = tm.get(tidx);
List<String> cur = new ArrayList<>();
cur.add(tidx + "");
for (String food : ts) {
cur.add(map.getOrDefault(food, 0) + "");
}
ans.add(cur);
}
returnans; }}Copy the codePython3 code:
from sortedcontainers import SortedSet, SortedDict
class Solution:
def displayTable(self, orders: List[List[str]]) - >List[List[str]] :
ans = []
# Table number: {food: number} (used to construct content)
tm = SortedDict()
# Meal (used to construct title)
ts = SortedSet()
for c,t,f in orders:
tidx = int(t)
ts.add(f)
if tidx not in tm:
tm[tidx] = defaultdict(int)
tm[tidx][f] += 1
n, m = len(tm) + 1.len(ts) + 1
# constructs the title
title = ["Table"]
title += list(ts)
ans.append(title)
# Construct content
for tidx, cnts in tm.items():
cur = [str(tidx)]
for food in ts:
cur.append(str(cnts[food]))
ans.append(cur)
return ans
Copy the code- Time complexity:
TreeSet和TreeMapThe basic operation is
. The pre-processing complexity of all orders is
; The number of tables after weight removal is
, the number of meals is
, the complexity of the constructed answer is
; The final complexity is
- Space complexity: O(r+c+r∗c)O(R +c+r * c)O(R + C +r∗c)
The last
This is article No.1418 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.
In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.
In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .
In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.