Posts tagged as “medium”

花花酱 LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

By zxi on January 9, 2021

Given an integer n, find a sequence that satisfies all of the following:

The integer 1 occurs once in the sequence.
Each integer between 2 and n occurs twice in the sequence.
For every integer i between 2 and n, the distance between the two occurrences of i is exactly i.

The distance between two numbers on the sequence, a[i] and a[j], is the absolute difference of their indices, |j - i|.

Return the lexicographically largest sequence. It is guaranteed that under the given constraints, there is always a solution.

A sequence a is lexicographically larger than a sequence b (of the same length) if in the first position where a and b differ, sequence a has a number greater than the corresponding number in b. For example, [0,1,9,0] is lexicographically larger than [0,1,5,6] because the first position they differ is at the third number, and 9 is greater than 5.

Example 1:

Input: n = 3
Output: [3,1,2,3,2]
Explanation: [2,3,2,1,3] is also a valid sequence, but [3,1,2,3,2] is the lexicographically largest valid sequence.

Example 2:

Input: n = 5
Output: [5,3,1,4,3,5,2,4,2]

Constraints:

1 <= n <= 20

Solution: Search

Search from left to right, largest to smallest.

Time complexity: O(n!)?
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> constructDistancedSequence(int n) {

const int len = 2 * n - 1;

vector<int> ans(len);

function<bool(int, int)> dfs = [&](int i, int s) {

if (i == len) return true;

if (ans[i]) return dfs(i + 1, s);

for (int d = n; d > 0; --d) {

const int j = i + (d == 1 ? 0 : d);

if ((s & (1 << d)) || j >= len || ans[j]) continue;

ans[i] = ans[j] = d;

if (dfs(i + 1, s | (1 << d))) return true;

ans[i] = ans[j] = 0;

}

return false;

};

dfs(0, 0);

return ans;

}

};

Java

// Author: Huahua

class Solution {

private boolean dfs(int[] ans, int n, int i, int s) {

if (i == ans.length) return true;

if (ans[i] > 0) return dfs(ans, n, i + 1, s);

for (int d = n; d > 0; --d) {

int j = i + (d == 1 ? 0 : d);

if ((s & (1 << d)) > 0 || j >= ans.length || ans[j] > 0)

continue;

ans[i] = ans[j] = d;

if (dfs(ans, n, i + 1, s | (1 << d))) return true;

ans[i] = ans[j] = 0;

}

return false;

}

public int[] constructDistancedSequence(int n) {

int[] ans = new int[n * 2 - 1];

dfs(ans, n, 0, 0);

return ans;

}

Python3

# Author: Huahua

class Solution:

def constructDistancedSequence(self, n: int) -> List[int]:

l = n * 2 - 1

ans = [0] * l

def dfs(i, s):

if i == l: return True

if ans[i]: return dfs(i + 1, s)

for d in range(n, 0, -1):

j = i + (0 if d == 1 else d)

if s & (1 << d) or j >= l or ans[j]: continue

ans[i] = ans[j] = d

if dfs(i + 1, s | (1 << d)): return True

ans[i] = ans[j] = 0

return False

dfs(0, 0)

return ans

花花酱 LeetCode 1717. Maximum Score From Removing Substrings

By zxi on January 9, 2021

You are given a string s and two integers x and y. You can perform two types of operations any number of times.

Remove substring "ab" and gain x points.
- For example, when removing "ab" from "cabxbae" it becomes "cxbae".
Remove substring "ba" and gain y points.
- For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return the maximum points you can gain after applying the above operations on s.

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

Constraints:

1 <= s.length <= 10⁵
1 <= x, y <= 10⁴
s consists of lowercase English letters.

Solution: Greedy + Stack

Remove the pattern with the larger score first.

Using a stack to remove all occurrences of a pattern in place in O(n) Time.

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

C++

// Author: Huahua

class Solution {

public:

int maximumGain(string s, int x, int y) {

// Remove patttern p from s for t points each.

// Returns the total score.

auto remove = [&](const string& p, int t) {

int total = 0;

int i = 0;

for (int j = 0; j < s.size(); ++j, ++i) {

s[i] = s[j];

if (i && s[i - 1] == p[0] && s[i] == p[1]) {

i -= 2;

total += t;

}

s.resize(i);

return total;

};

string px{"ab"};

string py{"ba"};

if (y > x) {

swap(px, py);

swap(x, y);

}

return remove(px, x) + remove(py, y);

}

};

花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

By zxi on January 3, 2021

A split of an integer array is good if:

The array is split into three non-empty contiguous subarrays – named left, mid, right respectively from left to right.
The sum of the elements in left is less than or equal to the sum of the elements in mid, and the sum of the elements in mid is less than or equal to the sum of the elements in right.

Given nums, an array of non-negative integers, return the number of good ways to split nums. As the number may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: nums = [1,1,1]
Output: 1
Explanation: The only good way to split nums is [1] [1] [1].

Example 2:

Input: nums = [1,2,2,2,5,0]
Output: 3
Explanation: There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]

Example 3:

Input: nums = [3,2,1]
Output: 0
Explanation: There is no good way to split nums.

Constraints:

3 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁴

Solution 1: Prefix Sum + Binary Search

We split the array into [0 … i] [i + 1… j] [j + 1 … n – 1]
we can use binary search to find the min and max of j for each i.
s.t. sum(0 ~ i) <= sums(i + 1 ~j) <= sums(j + 1 ~ n – 1)
min is lower_bound(2 * sums(0 ~ i))
max is upper_bound(sums(0 ~ i) + (total – sums(0 ~ i)) / 2)

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

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

// [0 .. i] [i + 1 ... j] [j + 1 ... n - 1]

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

auto it1 = lower_bound(begin(nums) + i + 1, end(nums), 2 * nums[i]);

auto it2 = upper_bound(begin(nums), end(nums) - 1, nums[i] + (total - nums[i]) / 2);

if (it2 <= it1) continue;

ans += it2 - it1;

}

return ans % kMod;

}

};

Solution 2: Prefix Sum + Two Pointers

The right end of the middle array is in range [j, k – 1] and there are k – j choices.
Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int waysToSplit(vector<int>& nums) {

constexpr int kMod = 1e9 + 7;

const int n = nums.size();

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

nums[i] += nums[i - 1];

const int total = nums.back();

long ans = 0;

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

j = max(j, i + 1);

while (j < n - 1 && nums[j] < 2 * nums[i]) ++j;

k = max(k, j);

while (k < n - 1 && 2 * nums[k] <= nums[i] + total) ++k;

ans += (k - j);

}

return ans % kMod;

}

};

花花酱 LeetCode 1711. Count Good Meals

By zxi on January 2, 2021

A good meal is a meal that contains exactly two different food items with a sum of deliciousness equal to a power of two.

You can pick any two different foods to make a good meal.

Given an array of integers deliciousness where deliciousness[i] is the deliciousness of the i^th item of food, return the number of different good meals you can make from this list modulo 10⁹ + 7.

Note that items with different indices are considered different even if they have the same deliciousness value.

Example 1:

Input: deliciousness = [1,3,5,7,9]
Output: 4
Explanation: The good meals are (1,3), (1,7), (3,5) and, (7,9).
Their respective sums are 4, 8, 8, and 16, all of which are powers of 2.

Example 2:

Input: deliciousness = [1,1,1,3,3,3,7]
Output: 15
Explanation: The good meals are (1,1) with 3 ways, (1,3) with 9 ways, and (1,7) with 3 ways.

Constraints:

1 <= deliciousness.length <= 10⁵
0 <= deliciousness[i] <= 2²⁰

Solution: Hashtable

Same idea as LeetCode 1: Two Sum

Use a hashtable to store the occurrences of all the numbers added so far. For a new number x, check all possible 2^i – x. ans += freq[2^i – x] 0 <= i <= 21

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

C++

class Solution {

public:

int countPairs(vector<int>& A) {

constexpr int kMod = 1e9 + 7;

unordered_map<int, int> m;

long ans = 0;

for (int x : A) {

for (int t = 1; t <= 1 << 21; t *= 2) {

auto it = m.find(t - x);

if (it != end(m)) ans += it->second;

}

++m[x];

}

return ans % kMod;

}

};

Python3

class Solution:

def countPairs(self, deliciousness: List[int]) -> int:

sums = [1<<i for i in range(22)]

m = defaultdict(int)

ans = 0

for x in deliciousness:

for t in sums:

if t - x in m: ans += m[t - x]

m[x] += 1

return ans % (10**9 + 7)

Posts tagged as “medium”

花花酱 LeetCode 1721. Swapping Nodes in a Linked List

Solution:

C++

花花酱 LeetCode 1718. Construct the Lexicographically Largest Valid Sequence

Solution: Search

C++

Java

Python3

花花酱 LeetCode 1717. Maximum Score From Removing Substrings

Solution: Greedy + Stack

C++

花花酱 LeetCode 1712. Ways to Split Array Into Three Subarrays

Solution 1: Prefix Sum + Binary Search

C++

Solution 2: Prefix Sum + Two Pointers

C++

花花酱 LeetCode 1711. Count Good Meals

Solution: Hashtable

C++

Python3