Huahua’s Tech Road

花花酱 LeetCode 2235. Add Two Integers

By zxi on April 16, 2022

Given two integers num1 and num2, return the sum of the two integers.

Example 1:

Input: num1 = 12, num2 = 5
Output: 17
Explanation: num1 is 12, num2 is 5, and their sum is 12 + 5 = 17, so 17 is returned.

Example 2:

Input: num1 = -10, num2 = 4
Output: -6
Explanation: num1 + num2 = -6, so -6 is returned.

Constraints:

-100 <= num1, num2 <= 100

Solution: Just sum them up

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

C++

// Author: Huahua

class Solution {

public:

int sum(int num1, int num2) {

return num1 + num2;

}

};

花花酱 LeetCode 2233. Maximum Product After K Increments

By zxi on April 9, 2022

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [0,4], k = 5
Output: 20
Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216
Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 * 4 * 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

1 <= nums.length, k <= 10⁵
0 <= nums[i] <= 10⁶

Solution: priority queue

Always increment the smallest number. Proof?

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

C++

// Author: Huahua

class Solution {

public:

int maximumProduct(vector<int>& nums, int k) {

constexpr int kMod = 1e9 + 7;

priority_queue<int, vector<int>, greater<int>> q(begin(nums), end(nums));

while (k--) {

const int n = q.top();

q.pop();

q.push(n + 1);

}

long long ans = 1;

while (!q.empty()) {

ans *= q.top(); q.pop();

ans %= kMod;

}

return ans;

}

};

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

};

Huahua's Tech Road

花花酱 LeetCode 2235. Add Two Integers

Solution: Just sum them up

C++

花花酱 LeetCode 2233. Maximum Product After K Increments

Solution: priority queue

C++

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