Posts tagged as “medium”

花花酱 LeetCode 2139. Minimum Moves to Reach Target Score

By zxi on January 30, 2022

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target.

In one move, you can either:

Increment the current integer by one (i.e., x = x + 1).
Double the current integer (i.e., x = 2 * x).

You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times.

Given the two integers target and maxDoubles, return the minimum number of moves needed to reach target starting with 1.

Example 1:

Input: target = 5, maxDoubles = 0
Output: 4
Explanation: Keep incrementing by 1 until you reach target.

Example 2:

Input: target = 19, maxDoubles = 2
Output: 7
Explanation: Initially, x = 1
Increment 3 times so x = 4
Double once so x = 8
Increment once so x = 9
Double again so x = 18
Increment once so x = 19

Example 3:

Input: target = 10, maxDoubles = 4
Output: 4
Explanation:Initially, x = 1
Increment once so x = 2
Double once so x = 4
Increment once so x = 5
Double again so x = 10

Constraints:

1 <= target <= 10⁹
0 <= maxDoubles <= 100

Solution: Reverse + Greedy

If num is odd, decrement it by 1. Divide num by 2 until maxdoubles times. Apply decrementing until 1 reached.

ex1: 19 (dec)-> 18 (div1)-> 9 (dec) -> 8 (div2)-> 4 (dec)-> 3 (dec)-> 2 (dec)-> 1

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

C++

// Author: Huahua

class Solution {

public:

int minMoves(int target, int maxDoubles) {

int ans = 0;

while (maxDoubles-- && target != 1) {

if (target & 1)

--target, ++ans;

++ans;

target >>= 1;

}

ans += (target - 1);

return ans;

}

};

花花酱 LeetCode 2135. Count Words Obtained After Adding a Letter

By zxi on January 17, 2022

You are given two 0-indexed arrays of strings startWords and targetWords. Each string consists of lowercase English letters only.

For each string in targetWords, check if it is possible to choose a string from startWords and perform a conversion operation on it to be equal to that from targetWords.

The conversion operation is described in the following two steps:

Append any lowercase letter that is not present in the string to its end.
- For example, if the string is "abc", the letters 'd', 'e', or 'y' can be added to it, but not 'a'. If 'd' is added, the resulting string will be "abcd".
Rearrange the letters of the new string in any arbitrary order.
- For example, "abcd" can be rearranged to "acbd", "bacd", "cbda", and so on. Note that it can also be rearranged to "abcd" itself.

Return the number of strings in targetWords that can be obtained by performing the operations on any string of startWords.

Note that you will only be verifying if the string in targetWords can be obtained from a string in startWords by performing the operations. The strings in startWords do not actually change during this process.

Example 1:

Input: startWords = ["ant","act","tack"], targetWords = ["tack","act","acti"]
Output: 2
Explanation:
- In order to form targetWords[0] = "tack", we use startWords[1] = "act", append 'k' to it, and rearrange "actk" to "tack".
- There is no string in startWords that can be used to obtain targetWords[1] = "act".
  Note that "act" does exist in startWords, but we must append one letter to the string before rearranging it.
- In order to form targetWords[2] = "acti", we use startWords[1] = "act", append 'i' to it, and rearrange "acti" to "acti" itself.

Example 2:

Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1
Explanation:
- In order to form targetWords[0] = "abc", we use startWords[0] = "ab", add 'c' to it, and rearrange it to "abc".
- There is no string in startWords that can be used to obtain targetWords[1] = "abcd".

Constraints:

1 <= startWords.length, targetWords.length <= 5 * 10⁴
1 <= startWords[i].length, targetWords[j].length <= 26
Each string of startWords and targetWords consists of lowercase English letters only.
No letter occurs more than once in any string of startWords or targetWords.

Solution: Bitmask w/ Hashtable

Since there is no duplicate letters in each word, we can use a bitmask to represent a word.

Step 1: For each word in startWords, we obtain its bitmask and insert it into a hashtable.
Step 2: For each word in targetWords, enumerate it’s letter and unset 1 bit (skip one letter) and see whether it’s in the hashtable or not.

E.g. for target word “abc”, its bitmask is 0…0111, and we test whether “ab” or “ac” or “bc” in the hashtable or not.

Time complexity: O(n * 26^2)
Space complexity: O(n * 26)

C++

// Author: Huahua

class Solution {

public:

int wordCount(vector<string>& startWords, vector<string>& targetWords) {

unordered_set<int> s;

auto getKey = [](const string& s) {

return accumulate(begin(s), end(s), 0, [](int key, char c) { return key | (1 << (c - 'a')); });

};

for (const string& w : startWords)

s.insert(getKey(w));

return accumulate(begin(targetWords), end(targetWords), 0, [&](int ans, const string& w) {

const int key = getKey(w);

return ans + any_of(begin(w), end(w), [&](char c) { return s.count(key ^ (1 << (c - 'a'))); });

});

}

};

花花酱 LeetCode 2134. Minimum Swaps to Group All 1’s Together II

By zxi on January 17, 2022

A swap is defined as taking two distinct positions in an array and swapping the values in them.

A circular array is defined as an array where we consider the first element and the last element to be adjacent.

Given a binary circular array nums, return the minimum number of swaps required to group all 1‘s present in the array together at any location.

Example 1:

Input: nums = [0,1,0,1,1,0,0]
Output: 1
Explanation: Here are a few of the ways to group all the 1's together:
[0,0,1,1,1,0,0] using 1 swap.
[0,1,1,1,0,0,0] using 1 swap.
[1,1,0,0,0,0,1] using 2 swaps (using the circular property of the array).
There is no way to group all 1's together with 0 swaps.
Thus, the minimum number of swaps required is 1.

Example 2:

Input: nums = [0,1,1,1,0,0,1,1,0]
Output: 2
Explanation: Here are a few of the ways to group all the 1's together:
[1,1,1,0,0,0,0,1,1] using 2 swaps (using the circular property of the array).
[1,1,1,1,1,0,0,0,0] using 2 swaps.
There is no way to group all 1's together with 0 or 1 swaps.
Thus, the minimum number of swaps required is 2.

Example 3:

Input: nums = [1,1,0,0,1]
Output: 0
Explanation: All the 1's are already grouped together due to the circular property of the array.
Thus, the minimum number of swaps required is 0.

Constraints:

1 <= nums.length <= 10⁵
nums[i] is either 0 or 1.

Solution: Sliding Window

Step 1: Count how many ones are there in the array. Assume it’s K.
Step 2: For each window of size k, count how many ones in the window, we have to swap 0s out with 1s to fill the window. ans = min(ans, k – ones).

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

C++

// Author: Huahua

class Solution {

public:

int minSwaps(vector<int>& nums) {

const int n = nums.size();

const int k = accumulate(begin(nums), end(nums), 0);

int ans = INT_MAX;

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

if (i >= k) cur -= nums[(i - k + n) % n];

cur += nums[i % n];

ans = min(ans, k - cur);

}

return ans;

}

};

花花酱 LeetCode 2131. Longest Palindrome by Concatenating Two Letter Words

By zxi on January 9, 2022

You are given an array of strings words. Each element of words consists of two lowercase English letters.

Create the longest possible palindrome by selecting some elements from words and concatenating them in any order. Each element can be selected at most once.

Return the length of the longest palindrome that you can create. If it is impossible to create any palindrome, return 0.

A palindrome is a string that reads the same forward and backward.

Example 1:

Input: words = ["lc","cl","gg"]
Output: 6
Explanation: One longest palindrome is "lc" + "gg" + "cl" = "lcggcl", of length 6.
Note that "clgglc" is another longest palindrome that can be created.

Example 2:

Input: words = ["ab","ty","yt","lc","cl","ab"]
Output: 8
Explanation: One longest palindrome is "ty" + "lc" + "cl" + "yt" = "tylcclyt", of length 8.
Note that "lcyttycl" is another longest palindrome that can be created.

Example 3:

Input: words = ["cc","ll","xx"]
Output: 2
Explanation: One longest palindrome is "cc", of length 2.
Note that "ll" is another longest palindrome that can be created, and so is "xx".

Constraints:

1 <= words.length <= 10⁵
words[i].length == 2
words[i] consists of lowercase English letters.

Solution: Match mirrored words

For any pair of mirrored words, e.g. ‘ab’ <-> ‘ba’ or ‘aa’ <-> ‘aa’, we can extend the existing longest palindrome, ans += 4.
For any unpaired words with same letter, e.g. ‘cc’, we can only use one and put in the middle of the pladrome, ans += 2.

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

C++

// Author: Huahua

class Solution {

public:

int longestPalindrome(vector<string>& words) {

int ans = 0;

int same = 0;

vector<vector<int>> m(26, vector<int>(26));

for (const string& word : words) {

const int a = word[0] - 'a';

const int b = word[1] - 'a';

if (m[b][a]) {

--m[b][a];

ans += 4;

} else {

++m[a][b];

}

for (int i = 0; i < 26; ++i)

if (m[i][i]) {

ans += 2;

break;

}

return ans;

}

};

花花酱 LeetCode 2130. Maximum Twin Sum of a Linked List

By zxi on January 9, 2022

In a linked list of size n, where n is even, the i^th node (0-indexed) of the linked list is known as the twin of the (n-1-i)^th node, if 0 <= i <= (n / 2) - 1.

For example, if n = 4, then node 0 is the twin of node 3, and node 1 is the twin of node 2. These are the only nodes with twins for n = 4.

The twin sum is defined as the sum of a node and its twin.

Given the head of a linked list with even length, return the maximum twin sum of the linked list.

Example 1:

Input: head = [5,4,2,1]
Output: 6
Explanation:
Nodes 0 and 1 are the twins of nodes 3 and 2, respectively. All have twin sum = 6.
There are no other nodes with twins in the linked list.
Thus, the maximum twin sum of the linked list is 6.

Example 2:

Input: head = [4,2,2,3]
Output: 7
Explanation:
The nodes with twins present in this linked list are:
- Node 0 is the twin of node 3 having a twin sum of 4 + 3 = 7.
- Node 1 is the twin of node 2 having a twin sum of 2 + 2 = 4.
Thus, the maximum twin sum of the linked list is max(7, 4) = 7.

Example 3:

Input: head = [1,100000]
Output: 100001
Explanation:
There is only one node with a twin in the linked list having twin sum of 1 + 100000 = 100001.

Constraints:

The number of nodes in the list is an even integer in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Solution: Two Pointers + Reverse List

Use fast slow pointers to find the middle point and reverse the second half.

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

C++

// Author: Huahua

class Solution {

public:

int pairSum(ListNode* head) {

auto reverse = [](ListNode* head, ListNode* prev = nullptr) {

while (head) {

swap(head->next, prev);

swap(head, prev);

}

return prev;

};

ListNode* fast = head;

ListNode* slow = head;

while (fast) {

fast = fast->next->next;

slow = slow->next;

}

slow = reverse(slow);

int ans = 0;

while (slow) {

ans = max(ans, head->val + slow->val);

head = head->next;

slow = slow->next;

}

return ans;

}

};