{"id":6646,"date":"2020-04-20T00:32:06","date_gmt":"2020-04-20T07:32:06","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6646"},"modified":"2020-04-20T00:32:42","modified_gmt":"2020-04-20T07:32:42","slug":"leetcode-1418-display-table-of-food-orders-in-a-restaurant","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1418-display-table-of-food-orders-in-a-restaurant\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1418. Display Table of Food Orders in a Restaurant"},"content":{"rendered":"\n

Given the array orders<\/code>, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei<\/sub>,tableNumberi<\/sub>,foodItemi<\/sub>]<\/code> where customerNamei<\/sub><\/code> is the name of the customer, tableNumberi<\/sub><\/code> is the table customer sit at, and foodItemi<\/sub><\/code> is the item customer orders.<\/p>\n\n\n\n

Return the restaurant’s \u201cdisplay table<\/strong>\u201d<\/em>. The \u201cdisplay table<\/strong>\u201d is a table whose row entries denote how many of each food item each table ordered. The first column is the table number and the remaining columns correspond to each food item in alphabetical order. The first row should be a header whose first column is \u201cTable\u201d, followed by the names of the food items. Note that the customer names are not part of the table. Additionally, the rows should be sorted in numerically increasing order.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> orders = [[\"David\",\"3\",\"Ceviche\"],[\"Corina\",\"10\",\"Beef Burrito\"],[\"David\",\"3\",\"Fried Chicken\"],[\"Carla\",\"5\",\"Water\"],[\"Carla\",\"5\",\"Ceviche\"],[\"Rous\",\"3\",\"Ceviche\"]]\nOutput:<\/strong> [[\"Table\",\"Beef Burrito\",\"Ceviche\",\"Fried Chicken\",\"Water\"],[\"3\",\"0\",\"2\",\"1\",\"0\"],[\"5\",\"0\",\"1\",\"0\",\"1\"],[\"10\",\"1\",\"0\",\"0\",\"0\"]] \nExplanation:\n<\/strong>The displaying table looks like:\nTable,Beef Burrito,Ceviche,Fried Chicken,Water<\/strong>\n3    ,0           ,2      ,1            ,0\n5    ,0           ,1      ,0            ,1\n10   ,1           ,0      ,0            ,0\nFor the table 3: David orders \"Ceviche\" and \"Fried Chicken\", and Rous orders \"Ceviche\".\nFor the table 5: Carla orders \"Water\" and \"Ceviche\".\nFor the table 10: Corina orders \"Beef Burrito\". \n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> orders = [[\"James\",\"12\",\"Fried Chicken\"],[\"Ratesh\",\"12\",\"Fried Chicken\"],[\"Amadeus\",\"12\",\"Fried Chicken\"],[\"Adam\",\"1\",\"Canadian Waffles\"],[\"Brianna\",\"1\",\"Canadian Waffles\"]]\nOutput:<\/strong> [[\"Table\",\"Canadian Waffles\",\"Fried Chicken\"],[\"1\",\"2\",\"0\"],[\"12\",\"0\",\"3\"]] \nExplanation:<\/strong> \nFor the table 1: Adam and Brianna order \"Canadian Waffles\".\nFor the table 12: James, Ratesh and Amadeus order \"Fried Chicken\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> orders = [[\"Laura\",\"2\",\"Bean Burrito\"],[\"Jhon\",\"2\",\"Beef Burrito\"],[\"Melissa\",\"2\",\"Soda\"]]\nOutput:<\/strong> [[\"Table\",\"Bean Burrito\",\"Beef Burrito\",\"Soda\"],[\"2\",\"1\",\"1\",\"1\"]]\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= orders.length <= 5 * 10^4<\/code><\/li>
  • orders[i].length == 3<\/code><\/li>
  • 1 <= customerNamei<\/sub>.length, foodItemi<\/sub>.length <= 20<\/code><\/li>
  • customerNamei<\/sub><\/code> and foodItemi<\/sub><\/code> consist of lowercase and uppercase English letters and the space character.<\/li>
  • tableNumberi<\/sub> <\/code>is a valid integer between 1<\/code> and 500<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: TreeMap\/Set + HashTable<\/p>\n\n\n\n
    Time complexity: O(nlogn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector> displayTable(vector>& orders) {\n    map> tables;\n    set foods;\n    for (const auto& order : orders) {\n      ++tables[stoi(order[1])][order[2]];\n      foods.insert(order[2]);\n    }\n    vector> ans;\n    ans.push_back({{\"Table\"}});    \n    ans.back().insert(end(ans.back()), begin(foods), end(foods));\n    for (auto& [table, m] : tables) {\n      vector line{to_string(table)};\n      for (const auto& food : foods)\n        line.push_back(to_string(m[food]));\n      ans.push_back(move(line));\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerNamei,tableNumberi,foodItemi] where customerNamei is the name of the customer, tableNumberi is the table customer sit at,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,462,177,243],"class_list":["post-6646","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-map","tag-medium","tag-set","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6646","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6646"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6646\/revisions"}],"predecessor-version":[{"id":6648,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6646\/revisions\/6648"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6646"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6646"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6646"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}