Huahua’s Tech Road

花花酱 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 1422. Maximum Score After Splitting a String

By zxi on April 25, 2020

Given a string s of zeros and ones, return the maximum score after splitting the string into two non-empty substrings (i.e. left substring and right substring).

The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

Example 1:

Input: s = "011101"
Output: 5 
Explanation: 
All possible ways of splitting s into two non-empty substrings are:
left = "0" and right = "11101", score = 1 + 4 = 5 
left = "01" and right = "1101", score = 1 + 3 = 4 
left = "011" and right = "101", score = 1 + 2 = 3 
left = "0111" and right = "01", score = 1 + 1 = 2 
left = "01110" and right = "1", score = 2 + 1 = 3

Example 2:

Input: s = "00111"
Output: 5
Explanation: When left = "00" and right = "111", we get the maximum score = 2 + 3 = 5

Example 3:

Input: s = "1111"
Output: 3

Constraints:

2 <= s.length <= 500
The string s consists of characters ‘0’ and ‘1’ only.

Solution 1: Brute Force

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

Solution 2: Counting

2.1 Two passes,
1st, count the number of ones of the entire string
2nd, inc zeros or dec ones according to s[i]
ans = max(zeros + ones)

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

C++

// Author: Huahua

class Solution {

public:

int maxScore(string s) {

int ones = 0;

for (char c : s)

if (c == '1') ++ones;

int zeros = 0;

int ans = 0;

for (int i = 0; i < s.length() - 1; ++i) {

if (s[i] == '0') ++zeros;

else --ones;

ans = max(ans, zeros + ones);

}

return ans;

}

};

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

By zxi on April 20, 2020

Given three integers n, m and k. Consider the following algorithm to find the maximum element of an array of positive integers:

You should build the array arr which has the following properties:

arr has exactly n integers.
1 <= arr[i] <= m where (0 <= i < n).
After applying the mentioned algorithm to arr, the value search_cost is equal to k.

Return the number of ways to build the array arr under the mentioned conditions. As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: n = 2, m = 3, k = 1
Output: 6
Explanation: The possible arrays are [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]

Example 2:

Input: n = 5, m = 2, k = 3
Output: 0
Explanation: There are no possible arrays that satisify the mentioned conditions.

Example 3:

Input: n = 9, m = 1, k = 1
Output: 1
Explanation: The only possible array is [1, 1, 1, 1, 1, 1, 1, 1, 1]

Example 4:

Input: n = 50, m = 100, k = 25
Output: 34549172
Explanation: Don't forget to compute the answer modulo 1000000007

Example 5:

Input: n = 37, m = 17, k = 7
Output: 418930126

Constraints:

1 <= n <= 50
1 <= m <= 100
0 <= k <= n

Solution: DP

dp[n][m][k] := ways to build given n,m,k.

dp[n][m][k] = sum(dp[n-1][m][k] + dp[n-1][i-1][k-1] – dp[n-1][i-1][k]), 1 <= i <= m
dp[1][m][1] = m
dp[n][m][k] = 0 if k < 1 or k > m or k > n

Time complexity: O(n*m^2*k)
Space complexity: O(n*m*k)

C++

// Author: Huahua

int mem[51][101][51] = {0};

class Solution {

public:

int numOfArrays(int n, int m, int k) {

const int kMod = 1e9 + 7;

function<int(int, int, int)> dp = [&dp](int n, int m, int k) {

if (k < 1 || k > m || k > n) return 0;

if (n == 1 && k == 1) return m;

if (mem[n][m][k]) return mem[n][m][k];

long ans = 0;

for (int i = 1; i <= m; ++i) {

ans += dp(n - 1, m, k);

ans += dp(n - 1, i - 1, k - 1);

ans -= dp(n - 1, i - 1, k);

ans = (ans + kMod) % kMod;

}

return mem[n][m][k] = ans;

};

return dp(n, m, k);

}

};

花花酱 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;

}

};

Huahua's Tech Road

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

C++

LeetCode 1422. Maximum Score After Splitting a String

Solution 1: Brute Force

Solution 2: Counting

C++

花花酱 LeetCode 1420. Build Array Where You Can Find The Maximum Exactly K Comparisons

Solution: DP

C++

花花酱 LeetCode 1419. Minimum Number of Frogs Croaking

Solution: Hashtable

C++

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

C++