Huahua’s Tech Road

花花酱 LeetCode 1755. Closest Subsequence Sum

By zxi on February 13, 2021

You are given an integer array nums and an integer goal.

You want to choose a subsequence of nums such that the sum of its elements is the closest possible to goal. That is, if the sum of the subsequence’s elements is sum, then you want to minimize the absolute difference abs(sum - goal).

Return the minimum possible value of abs(sum - goal).

Note that a subsequence of an array is an array formed by removing some elements (possibly all or none) of the original array.

Example 1:

Input: nums = [5,-7,3,5], goal = 6
Output: 0
Explanation: Choose the whole array as a subsequence, with a sum of 6.
This is equal to the goal, so the absolute difference is 0.

Example 2:

Input: nums = [7,-9,15,-2], goal = -5
Output: 1
Explanation: Choose the subsequence [7,-9,-2], with a sum of -4.
The absolute difference is abs(-4 - (-5)) = abs(1) = 1, which is the minimum.

Example 3:

Input: nums = [1,2,3], goal = -7
Output: 7

Constraints:

1 <= nums.length <= 40
-10⁷ <= nums[i] <= 10⁷
-10⁹ <= goal <= 10⁹

Solution: Binary Search

Since n is too large to generate sums for all subsets O(2^n), we have to split the array into half, generate two sum sets. O(2^(n/2)).

Then the problem can be reduced to find the closet sum by picking one number (sum) each from two different arrays which can be solved in O(mlogm), where m = 2^(n/2).

So final time complexity is O(n * 2^(n/2))
Space complexity: O(2^(n/2))

C++

// Author: Huahua

class Solution {

public:

int minAbsDifference(vector<int>& nums, int goal) {

const int n = nums.size();

int ans = abs(goal);

vector<int> t1{0}, t2{0};

t1.reserve(1 << (n / 2 + 1));

t2.reserve(1 << (n / 2 + 1));

for (int i = 0; i < n / 2; ++i)

for (int j = t1.size() - 1; j >= 0; --j)

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

for (int i = n / 2; i < n; ++i)

for (int j = t2.size() - 1; j >= 0; --j)

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

set<int> s2(begin(t2), end(t2));

for (int x : unordered_set<int>(begin(t1), end(t1))) {

auto it = s2.lower_bound(goal - x);

if (it != s2.end())

ans = min(ans, abs(goal - x - *it));

if (it != s2.begin())

ans = min(ans, abs(goal - x - *prev(it)));

}

return ans;

}

};

花花酱 LeetCode 1754. Largest Merge Of Two Strings

By zxi on February 7, 2021

You are given two strings word1 and word2. You want to construct a string merge in the following way: while either word1 or word2 are non-empty, choose one of the following options:

If word1 is non-empty, append the first character in word1 to merge and delete it from word1.
- For example, if word1 = "abc" and merge = "dv", then after choosing this operation, word1 = "bc" and merge = "dva".
If word2 is non-empty, append the first character in word2 to merge and delete it from word2.
- For example, if word2 = "abc" and merge = "", then after choosing this operation, word2 = "bc" and merge = "a".

Return the lexicographically largest merge you can construct.

A string a is lexicographically larger than a string b (of the same length) if in the first position where a and b differ, a has a character strictly larger than the corresponding character in b. For example, "abcd" is lexicographically larger than "abcc" because the first position they differ is at the fourth character, and d is greater than c.

Example 1:

Input: word1 = "cabaa", word2 = "bcaaa"
Output: "cbcabaaaaa"
Explanation: One way to get the lexicographically largest merge is:
- Take from word1: merge = "c", word1 = "abaa", word2 = "bcaaa"
- Take from word2: merge = "cb", word1 = "abaa", word2 = "caaa"
- Take from word2: merge = "cbc", word1 = "abaa", word2 = "aaa"
- Take from word1: merge = "cbca", word1 = "baa", word2 = "aaa"
- Take from word1: merge = "cbcab", word1 = "aa", word2 = "aaa"
- Append the remaining 5 a's from word1 and word2 at the end of merge.

Example 2:

Input: word1 = "abcabc", word2 = "abdcaba"
Output: "abdcabcabcaba"

Constraints:

1 <= word1.length, word2.length <= 3000
word1 and word2 consist only of lowercase English letters.

Solution: Greedy

Always take a single char from the largest word. (NOT just the current char).

E.g.
ans = “”, w1 = “cabba”, w2 = “bcaaa”
w1 > w2, take from w1
ans = “c”, w1 = “abba”, w2 = “bcaaa”
w1 < w2, take from w2
ans = “cb”, w1 = “abba”, w2 = “caaa”
w1 < w2, take from w2
ans = “cbc”, w1 = “abba”, w2 = “aaa”
w1 > w2, take from w1. Note: both start with “a”, but we need to compare the entire word.
ans = “cbca”, w1 = “bba”, w2 = “aaa”
w1 > w2, take from w1
ans = “cbcab”, w1 = “ba”, w2 = “aaa”
…

Time complexity: O(min(m,n)^2)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string largestMerge(string_view w1, string_view w2) {

string ans;

int m = w1.length(), n = w2.length();

int i = 0, j = 0;

while (i < m && j < n)

ans += w1.substr(i) > w2.substr(j) ? w1[i++] : w2[j++];

ans.append(w1.substr(i));

ans.append(w2.substr(j));

return ans;

}

};

花花酱 LeetCode 1753. Maximum Score From Removing Stones

By zxi on February 7, 2021

You are playing a solitaire game with three piles of stones of sizes a, b, and c respectively. Each turn you choose two different non-empty piles, take one stone from each, and add 1 point to your score. The game stops when there are fewer than two non-empty piles (meaning there are no more available moves).

Given three integers a, b, and c, return the maximum score you can get.

Example 1:

Input: a = 2, b = 4, c = 6
Output: 6
Explanation: The starting state is (2, 4, 6). One optimal set of moves is:
- Take from 1st and 3rd piles, state is now (1, 4, 5)
- Take from 1st and 3rd piles, state is now (0, 4, 4)
- Take from 2nd and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 6 points.

Example 2:

Input: a = 4, b = 4, c = 6
Output: 7
Explanation: The starting state is (4, 4, 6). One optimal set of moves is:
- Take from 1st and 2nd piles, state is now (3, 3, 6)
- Take from 1st and 3rd piles, state is now (2, 3, 5)
- Take from 1st and 3rd piles, state is now (1, 3, 4)
- Take from 1st and 3rd piles, state is now (0, 3, 3)
- Take from 2nd and 3rd piles, state is now (0, 2, 2)
- Take from 2nd and 3rd piles, state is now (0, 1, 1)
- Take from 2nd and 3rd piles, state is now (0, 0, 0)
There are fewer than two non-empty piles, so the game ends. Total: 7 points.

Example 3:

Input: a = 1, b = 8, c = 8
Output: 8
Explanation: One optimal set of moves is to take from the 2nd and 3rd piles for 8 turns until they are empty.
After that, there are fewer than two non-empty piles, so the game ends.

Constraints:

1 <= a, b, c <= 10⁵

Solution 1: Greedy

Take two stones (one each) from the largest two piles, until one is empty.

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

int ans = 0;

while (s[1]-- && s[2]--) {

++ans;

sort(begin(s), end(s));

}

return ans;

}

};

Solution 2: Math

First, let’s assuming a <= b <= c.
There are two conditions:
1. a + b <= c, we can pair c with a first and then b. Total pairs is (a + b + (a + b)) / 2
2. a + b > c, we can pair c with a, b “evenly”, and then pair a with b, total pairs is (a + b + c) / 2

ans = (a + b + min(a + b, c)) / 2

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

C++

class Solution {

public:

int maximumScore(int a, int b, int c) {

array<int, 3> s{a,b,c};

sort(begin(s), end(s));

return (s[0] + s[1] + min(s[0] + s[1], s[2])) / 2;

}

};

花花酱 LeetCode 1752. Check if Array Is Sorted and Rotated

By zxi on February 7, 2021

Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.

There may be duplicates in the original array.

Note: An array A rotated by x positions results in an array B of the same length such that A[i] == B[(i+x) % A.length], where % is the modulo operation.

Example 1:

Input: nums = [3,4,5,1,2]
Output: true
Explanation: [1,2,3,4,5] is the original sorted array.
You can rotate the array by x = 3 positions to begin on the the element of value 3: [3,4,5,1,2].

Example 2:

Input: nums = [2,1,3,4]
Output: false
Explanation: There is no sorted array once rotated that can make nums.

Example 3:

Input: nums = [1,2,3]
Output: true
Explanation: [1,2,3] is the original sorted array.
You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.

Example 4:

Input: nums = [1,1,1]
Output: true
Explanation: [1,1,1] is the original sorted array.
You can rotate any number of positions to make nums.

Example 5:

Input: nums = [2,1]
Output: true
Explanation: [1,2] is the original sorted array.
You can rotate the array by x = 5 positions to begin on the element of value 2: [2,1].

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution: Counting and checking

Count how many turning points (nums[i] < nums[i – 1]) in the array. Return false if there are more than 1.
For the turning point r, (nums[r] < nums[r – 1), return true if both of the following conditions are satisfied:
1. nums[r – 1] is the largest number, e.g. nums[r – 1] >= nums[n – 1]
2. nums[r] is the smallest number, e.g. nums[r] <= nums[0]

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

C++

// Author: Huahua

class Solution {

public:

bool check(vector<int>& nums) {

int count = 0;

int r = -1;

for (size_t i = 1; i < nums.size(); ++i)

if (nums[i] < nums[i - 1]) {

++count;

r = i;

}

if (count == 0) return true;

if (count > 1) return false;

return nums[r] <= nums[0] && nums[r - 1] >= nums.back();

}

};

花花酱 LeetCode 1751. Maximum Number of Events That Can Be Attended II

By zxi on February 6, 2021

You are given an array of events where events[i] = [startDay_i, endDay_i, value_i]. The i^th event starts at startDay_iand ends at endDay_i, and if you attend this event, you will receive a value of value_i. You are also given an integer k which represents the maximum number of events you can attend.

You can only attend one event at a time. If you choose to attend an event, you must attend the entire event. Note that the end day is inclusive: that is, you cannot attend two events where one of them starts and the other ends on the same day.

Return the maximum sum of values that you can receive by attending events.

Example 1:

Input: events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
Output: 7
Explanation: Choose the green events, 0 and 1 (0-indexed) for a total value of 4 + 3 = 7.

Example 2:

Input: events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
Output: 10
Explanation: Choose event 2 for a total value of 10.
Notice that you cannot attend any other event as they overlap, and that you do not have to attend k events.

Example 3:

Input: events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
Output: 9
Explanation: Although the events do not overlap, you can only attend 3 events. Pick the highest valued three.

Constraints:

1 <= k <= events.length
1 <= k * events.length <= 10⁶
1 <= startDay_i <= endDay_i <= 10⁹
1 <= value_i <= 10⁶

Solution: DP + Binary Search

Sort events by ending time.
dp[i][j] := max value we can get by attending at most j events among events[0~i].
dp[i][j] = max(dp[i – 1][j], dp[p][j – 1] + value[i])
p is the first event that does not overlap with the current one.

Time complexity: O(nlogn + nk)
Space complexity: O(nk)

C++

// Author: Huahua

class Solution {

public:

int maxValue(vector<vector<int>>& events, int k) {

const int n = events.size();

vector<vector<int>> dp(n + 1, vector<int>(k + 1));

vector<int> e(n);

auto comp = [](const vector<int>& a, const vector<int>& b) {

return a[1] < b[1];

};

sort(begin(events), end(events), comp);

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

const int p = lower_bound(begin(events),

begin(events) + i,

vector<int>{0, events[i - 1][0], 0},

comp) - begin(events);

for (int j = 1; j <= k; ++j)

dp[i][j] = max(dp[i - 1][j],

dp[p][j - 1] + events[i - 1][2]);

}

return dp[n][k];

}

};

Huahua's Tech Road

花花酱 LeetCode 1755. Closest Subsequence Sum

Solution: Binary Search

C++

花花酱 LeetCode 1754. Largest Merge Of Two Strings

Solution: Greedy

C++

花花酱 LeetCode 1753. Maximum Score From Removing Stones

Solution 1: Greedy

C++

Solution 2: Math

C++

花花酱 LeetCode 1752. Check if Array Is Sorted and Rotated

Solution: Counting and checking

C++

花花酱 LeetCode 1751. Maximum Number of Events That Can Be Attended II

Solution: DP + Binary Search

C++