Huahua’s Tech Road

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

By zxi on April 9, 2022

You are given a 0-indexed string expression of the form "<num1>+<num2>" where <num1> and <num2> represent positive integers.

Add a pair of parentheses to expression such that after the addition of parentheses, expression is a valid mathematical expression and evaluates to the smallest possible value. The left parenthesis must be added to the left of '+' and the right parenthesis must be added to the right of '+'.

Return expression after adding a pair of parentheses such that expression evaluates to the smallest possible value. If there are multiple answers that yield the same result, return any of them.

The input has been generated such that the original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Example 1:

Input: expression = "247+38"
Output: "2(47+38)"
Explanation: The expression evaluates to 2 * (47 + 38) = 2 * 85 = 170.
Note that "2(4)7+38" is invalid because the right parenthesis must be to the right of the '+'.
It can be shown that 170 is the smallest possible value.

Example 2:

Input: expression = "12+34"
Output: "1(2+3)4"
Explanation: The expression evaluates to 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20.

Example 3:

Input: expression = "999+999"
Output: "(999+999)"
Explanation: The expression evaluates to 999 + 999 = 1998.

Constraints:

3 <= expression.length <= 10
expression consists of digits from '1' to '9' and '+'.
expression starts and ends with digits.
expression contains exactly one '+'.
The original value of expression, and the value of expression after adding any pair of parentheses that meets the requirements fits within a signed 32-bit integer.

Solution: Brute Force

Try all possible positions to add parentheses and evaluate the new expression.

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

C++

// Author: Huahua

class Solution {

public:

string minimizeResult(string expression) {

const int n = expression.size();

auto p = expression.find('+');

int best = INT_MAX;

string ans;

for (int l = 0; l < p; ++l)

for (int r = p + 2; r < n + 1; ++r) {

const int m1 = l ? stoi(expression.substr(0, l)) : 1;

const int m2 = (r < n) ? stoi(expression.substr(r)) : 1;

const int n1 = stoi(expression.substr(l, p));

const int n2 = stoi(expression.substr(p + 1, r - p - 1));

const int cur = m1 * (n1 + n2) * m2;

if (cur < best) {

best = cur;

ans = expression;

ans.insert(l, "(");

ans.insert(r + 1, ")");

}

return ans;

}

};

花花酱 LeetCode 2231. Largest Number After Digit Swaps by Parity

By zxi on April 9, 2022

You are given a positive integer num. You may swap any two digits of num that have the same parity (i.e. both odd digits or both even digits).

Return the largest possible value of num after any number of swaps.

Example 1:

Input: num = 1234
Output: 3412
Explanation: Swap the digit 3 with the digit 1, this results in the number 3214.
Swap the digit 2 with the digit 4, this results in the number 3412.
Note that there may be other sequences of swaps but it can be shown that 3412 is the largest possible number.
Also note that we may not swap the digit 4 with the digit 1 since they are of different parities.

Example 2:

Input: num = 65875
Output: 87655
Explanation: Swap the digit 8 with the digit 6, this results in the number 85675.
Swap the first digit 5 with the digit 7, this results in the number 87655.
Note that there may be other sequences of swaps but it can be shown that 87655 is the largest possible number.

Constraints:

1 <= num <= 10⁹

Solution:

Put all even digits into one array, all odd digits into another one, all digits into the third. Sort two arrays, and generate a new number from sorted arrays.

Time complexity: O(logn*loglogn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

int largestInteger(int num) {

vector<int> odd, even, org;

for (int cur = num; cur; cur /= 10) {

((cur & 1) ? odd : even).push_back(cur % 10);

org.push_back(cur % 10);

}

sort(begin(odd), end(odd));

sort(begin(even), end(even));

int ans = 0;

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

if (i) ans *= 10;

auto& cur = (org[org.size() - i - 1] & 1) ? odd : even;

ans += cur.back();

cur.pop_back();

}

return ans;

}

};

花花酱 LeetCode 2227. Encrypt and Decrypt Strings

By zxi on April 3, 2022

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string.

A string is encrypted with the following process:

For each character c in the string, we find the index i satisfying keys[i] == c in keys.
Replace c with values[i] in the string.

A string is decrypted with the following process:

For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s. If there are multiple valid i, we choose any one of them. This means a string could have multiple possible strings it can decrypt to.
Replace s with keys[i] in the string.

Implement the Encrypter class:

Encrypter(char[] keys, String[] values, String[] dictionary) Initializes the Encrypter class with keys, values, and dictionary.
String encrypt(String word1) Encrypts word1 with the encryption process described above and returns the encrypted string.
int decrypt(String word2) Returns the number of possible strings word2 could decrypt to that also appear in dictionary.

Example 1:

Input
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
Output

[null, “eizfeiam”, 2]

Explanation Encrypter encrypter = new Encrypter([[‘a’, ‘b’, ‘c’, ‘d’], [“ei”, “zf”, “ei”, “am”], [“abcd”, “acbd”, “adbc”, “badc”, “dacb”, “cadb”, “cbda”, “abad”]); encrypter.encrypt(“abcd”); // return “eizfeiam”. // ‘a’ maps to “ei”, ‘b’ maps to “zf”, ‘c’ maps to “ei”, and ‘d’ maps to “am”. encrypter.decrypt(“eizfeiam”); // return 2. // “ei” can map to ‘a’ or ‘c’, “zf” maps to ‘b’, and “am” maps to ‘d’. // Thus, the possible strings after decryption are “abad”, “cbad”, “abcd”, and “cbcd”. // 2 of those strings, “abad” and “abcd”, appear in dictionary, so the answer is 2.

Constraints:

1 <= keys.length == values.length <= 26
values[i].length == 2
1 <= dictionary.length <= 100
1 <= dictionary[i].length <= 100
All keys[i] and dictionary[i] are unique.
1 <= word1.length <= 2000
1 <= word2.length <= 200
All word1[i] appear in keys.
word2.length is even.
keys, values[i], dictionary[i], word1, and word2 only contain lowercase English letters.
At most 200 calls will be made to encrypt and decrypt in total.

Solution:

For encryption, follow the instruction. Time complexity: O(len(word)) = O(2000)
For decryption, try all words in the dictionary and encrypt them and compare the encrypted string with the word to decrypt. Time complexity: O(sum(len(word_in_dict))) = O(100*100)

Worst case: 200 calls to decryption, T = 200 * O(100 * 100) = O(2*10⁶)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26),

dict(dictionary) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

return count_if(begin(dict), end(dict), [&](const string& w){

return encrypt(w) == word2;

});

}

private:

vector<string> vals;

vector<string> dict;

};

Optimization

Pre-compute answer for all the words in dictionary.

decrypt: Time complexity: O(1)

C++

// Author: Huahua

class Encrypter {

public:

Encrypter(vector<char>& keys,

vector<string>& values,

vector<string>& dictionary):

vals(26) {

for (size_t i = 0; i < keys.size(); ++i)

vals[keys[i] - 'a'] = values[i];

for (const string& w : dictionary)

++counts[encrypt(w)];

}

string encrypt(string word1) {

string ans;

for (char c : word1)

ans += vals[c - 'a'];

return ans;

}

int decrypt(string word2) {

auto it = counts.find(word2);

return it == counts.end() ? 0 : it->second;

}

private:

vector<string> vals;

unordered_map<string, int> counts;

};

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

By zxi on April 2, 2022

You are given a 0-indexed integer array candies. Each element in the array denotes a pile of candies of size candies[i]. You can divide each pile into any number of sub piles, but you cannot merge two piles together.

You are also given an integer k. You should allocate piles of candies to k children such that each child gets the same number of candies. Each child can take at most one pile of candies and some piles of candies may go unused.

Return the maximum number of candies each child can get.

Example 1:

Input: candies = [5,8,6], k = 3
Output: 5
Explanation: We can divide candies[1] into 2 piles of size 5 and 3, and candies[2] into 2 piles of size 5 and 1. We now have five piles of candies of sizes 5, 5, 3, 5, and 1. We can allocate the 3 piles of size 5 to 3 children. It can be proven that each child cannot receive more than 5 candies.

Example 2:

Input: candies = [2,5], k = 11
Output: 0
Explanation: There are 11 children but only 7 candies in total, so it is impossible to ensure each child receives at least one candy. Thus, each child gets no candy and the answer is 0.

Constraints:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁷
1 <= k <= 10¹²

Solution: Binary Search

Find the smallest L s.t. we can allocate candies to less than k children.

ans = L – 1.

Time complexity: O(nlogm) where n is number of piles, m is sum(candies) / k.
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int maximumCandies(vector<int>& candies, long long k) {

long long total = accumulate(begin(candies), end(candies), 0LL);

long long l = 1;

long long r = total / k + 1;

while (l < r) {

long long m = l + (r - l) / 2;

long long c = 0;

for (int pile : candies)

c += pile / m;

if (c < k)

r = m;

else

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 2225. Find Players With Zero or One Losses

By zxi on April 2, 2022

You are given an integer array matches where matches[i] = [winner_i, loser_i] indicates that the player winner_i defeated player loser_i in a match.

Return a list answer of size 2 where:

answer[0] is a list of all players that have not lost any matches.
answer[1] is a list of all players that have lost exactly one match.

The values in the two lists should be returned in increasing order.

Note:

You should only consider the players that have played at least one match.
The testcases will be generated such that no two matches will have the same outcome.

Example 1:

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

Example 2:

Input: matches = [[2,3],[1,3],[5,4],[6,4]]
Output: [[1,2,5,6],[]]
Explanation:
Players 1, 2, 5, and 6 have not lost any matches.
Players 3 and 4 each have lost two matches.
Thus, answer[0] = [1,2,5,6] and answer[1] = [].

Constraints:

1 <= matches.length <= 10⁵
matches[i].length == 2
1 <= winner_i, loser_i <= 10⁵
winner_i != loser_i
All matches[i] are unique.

Solution: Hashtable

Use a hashtable to store the number of matches each player has lost. Note, also create an entry for those winners who never lose.

Time complexity: O(m), m = # of matches
Space complexity: O(n), n = # of players

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findWinners(vector<vector<int>>& matches) {

unordered_map<int, int> m;

for (const auto& match : matches) {

m[match[0]]; // create an entry for the winner.

++m[match[1]];

}

vector<vector<int>> ans(2);

for (const auto& [player, loses] : m)

if (loses <= 1) ans[loses].push_back(player);

sort(begin(ans[0]), end(ans[0]));

sort(begin(ans[1]), end(ans[1]));

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2232. Minimize Result by Adding Parentheses to Expression

Solution: Brute Force

C++

花花酱 LeetCode 2231. Largest Number After Digit Swaps by Parity

C++

花花酱 LeetCode 2227. Encrypt and Decrypt Strings

Solution:

C++

Optimization

C++

花花酱 LeetCode 2226. Maximum Candies Allocated to K Children

Solution: Binary Search

C++

花花酱 LeetCode 2225. Find Players With Zero or One Losses

Solution: Hashtable

C++