Posts tagged as “medium”

花花酱 LeetCode 1424. Diagonal Traverse II

By zxi on April 26, 2020

Given a list of lists of integers, nums, return all elements of nums in diagonal order as shown in the below images.

Example 1:

Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]

Example 2:

Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]

Example 3:

Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]]
Output: [1,4,2,5,3,8,6,9,7,10,11]

Example 4:

Input: nums = [[1,2,3,4,5,6]]
Output: [1,2,3,4,5,6]

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i].length <= 10^5
1 <= nums[i][j] <= 10^9
There at most 10^5 elements in nums.

Solution: Hashtable

Use diagonal index (i + j) as key.

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> findDiagonalOrder(vector<vector<int>>& nums) {

vector<vector<int>> m;

for (int i = 0; i < nums.size(); ++i)

for (int j = 0; j < nums[i].size(); ++j) {

if (m.size() <= i + j) m.push_back({});

m[i + j].push_back(nums[i][j]);

}

vector<int> ans;

for (const auto& d : m)

ans.insert(end(ans), rbegin(d), rend(d));

return ans;

}

};

Python

# Author: Huahua

class Solution:

def findDiagonalOrder(self, nums):

m = []

for i, row in enumerate(nums):

for j, v in enumerate(row):

if i + j >= len(m): m.append([])

m[i+j].append(v)

return [v for d in m for v in reversed(d)]

花花酱 LeetCode 1423. Maximum Points You Can Obtain from Cards

By zxi on April 25, 2020

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

1 <= cardPoints.length <= 10^5
1 <= cardPoints[i] <= 10^4
1 <= k <= cardPoints.length

Solution: Sliding Window

Time complexity: O(k)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maxScore(vector<int>& p, int k) {

const int n = p.size();

int cur = accumulate(begin(p), begin(p) + k, 0);

int ans = cur;

for (int i = 0; i < k; ++i) {

cur = cur - p[k - i - 1] + p[n - i - 1];

ans = max(ans, cur);

}

return ans;

}

};

花花酱 LeetCode 1419. Minimum Number of Frogs Croaking

By zxi on April 20, 2020

Given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed. Return the minimum number of different frogs to finish all the croak in the given string.

A valid “croak” means a frog is printing 5 letters ‘c’, ’r’, ’o’, ’a’, ’k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of valid “croak” return -1.

Example 1:

Input: croakOfFrogs = "croakcroak"
Output: 1 
Explanation: One frog yelling "croak" twice.

Example 2:

Input: croakOfFrogs = "crcoakroak"
Output: 2 
Explanation: The minimum number of frogs is two. 
The first frog could yell "crcoakroak".
The second frog could yell later "crcoakroak".

Example 3:

Input: croakOfFrogs = "croakcrook"
Output: -1
Explanation: The given string is an invalid combination of "croak" from different frogs.

Example 4:

Input: croakOfFrogs = "croakcroa"
Output: -1

Constraints:

1 <= croakOfFrogs.length <= 10^5
All characters in the string are: 'c', 'r', 'o', 'a' or 'k'.

Solution: Hashtable

Count the frequency of the letters, we need to make sure f[c] >= f[r] >= f[o] >= f[a] >= f[k] holds all the time, otherwise return -1.
whenever encounter c, increase the current frog, whenever there is k, decrease the frog count.
Don’t forget to check the current frog number, should be 0 in the end, otherwise there are open letters.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minNumberOfFrogs(string croakOfFrogs) {

vector<int> idx(26);

idx['c' - 'a'] = 0;

idx['r' - 'a'] = 1;

idx['o' - 'a'] = 2;

idx['a' - 'a'] = 3;

idx['k' - 'a'] = 4;

vector<int> count(5);

int cur = 0;

int ans = 0;

for (char ch : croakOfFrogs) {

const int i = idx[ch - 'a'];

++count[i];

if (ch == 'c') {

ans = max(ans, ++cur);

continue;

}

if (count[i] > count[i - 1]) return -1;

if (ch == 'k') --cur;

}

return cur ? -1 : ans;

}

};

花花酱 LeetCode 1418. Display Table of Food Orders in a Restaurant

By zxi on April 20, 2020

Given the array orders, which represents the orders that customers have done in a restaurant. More specifically orders[i]=[customerName_i,tableNumber_i,foodItem_i] where customerName_i is the name of the customer, tableNumber_i is the table customer sit at, and foodItem_i is the item customer orders.

Return the restaurant’s “display table”. The “display table” 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 “Table”, 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.

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","0","0"]] 
Explanation:
The displaying table looks like:
Table,Beef Burrito,Ceviche,Fried Chicken,Water
3    ,0           ,2      ,1            ,0
5    ,0           ,1      ,0            ,1
10   ,1           ,0      ,0            ,0
For the table 3: David orders "Ceviche" and "Fried Chicken", and Rous orders "Ceviche".
For the table 5: Carla orders "Water" and "Ceviche".
For the table 10: Corina orders "Beef Burrito".

Example 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"]] 
Explanation: 
For the table 1: Adam and Brianna order "Canadian Waffles".
For the table 12: James, Ratesh and Amadeus order "Fried Chicken".

Example 3:

Input: orders = [["Laura","2","Bean Burrito"],["Jhon","2","Beef Burrito"],["Melissa","2","Soda"]]
Output: [["Table","Bean Burrito","Beef Burrito","Soda"],["2","1","1","1"]]

Constraints:

1 <= orders.length <= 5 * 10^4
orders[i].length == 3
1 <= customerName_i.length, foodItem_i.length <= 20
customerName_i and foodItem_i consist of lowercase and uppercase English letters and the space character.
tableNumber_i is a valid integer between 1 and 500.

Solution: TreeMap/Set + HashTable

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<string>> displayTable(vector<vector<string>>& orders) {

map<int, unordered_map<string, int>> tables;

set<string> foods;

for (const auto& order : orders) {

++tables[stoi(order[1])][order[2]];

foods.insert(order[2]);

}

vector<vector<string>> ans;

ans.push_back({{"Table"}});

ans.back().insert(end(ans.back()), begin(foods), end(foods));

for (auto& [table, m] : tables) {

vector<string> line{to_string(table)};

for (const auto& food : foods)

line.push_back(to_string(m[food]));

ans.push_back(move(line));

}

return ans;

}

};

花花酱 LeetCode 1410. HTML Entity Parser

By zxi on April 11, 2020

HTML entity parser is the parser that takes HTML code as input and replace all the entities of the special characters by the characters itself.

The special characters and their entities for HTML are:

Quotation Mark: the entity is " and symbol character is ".
Single Quote Mark: the entity is ' and symbol character is '.
Ampersand: the entity is & and symbol character is &.
Greater Than Sign: the entity is > and symbol character is >.
Less Than Sign: the entity is < and symbol character is <.
Slash: the entity is &frasl; and symbol character is /.

Given the input text string to the HTML parser, you have to implement the entity parser.

Return the text after replacing the entities by the special characters.

Example 1:

Input: text = "&amp; is an HTML entity but &ambassador; is not."
Output: "& is an HTML entity but &ambassador; is not."
Explanation: The parser will replace the &amp; entity by &

Example 2:

Input: text = "and I quote: &quot;...&quot;"
Output: "and I quote: \"...\""

Example 3:

Input: text = "Stay home! Practice on Leetcode :)"
Output: "Stay home! Practice on Leetcode :)"

Example 4:

Input: text = "x &gt; y &amp;&amp; x &lt; y is always false"
Output: "x > y && x < y is always false"

Example 5:

Input: text = "leetcode.com&frasl;problemset&frasl;all"
Output: "leetcode.com/problemset/all"

Constraints:

1 <= text.length <= 10^5
The string may contain any possible characters out of all the 256 ASCII characters.

Solution: Simulation

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string entityParser(string text) {

map<string, string> m{

{""", "\""}, {"'", "'"}, {"&", "&"},

{">", ">"}, {"<", "<"}, {"&frasl;", "/"}};

string ans;

string buf;

for (char c : text) {

buf += c;

if (buf.back() != ';') continue;

const int l = buf.size();

for (const auto& [k, v] : m) {

const int kl = k.length();

if (l >= kl && buf.substr(l - kl) == k) {

ans += buf.substr(0, l - kl) + v;

buf.clear();

break;

}

return ans + buf;

}

};