Posts tagged as “search”

花花酱 LeetCode 1655. Distribute Repeating Integers

By zxi on November 14, 2020

You are given an array of n integers, nums, where there are at most 50 unique values in the array. You are also given an array of m customer order quantities, quantity, where quantity[i] is the amount of integers the i^th customer ordered. Determine if it is possible to distribute nums such that:

The i^th customer gets exactly quantity[i] integers,
The integers the i^th customer gets are all equal, and
Every customer is satisfied.

Return true if it is possible to distribute nums according to the above conditions.

Example 1:

Input: nums = [1,2,3,4], quantity = [2]
Output: false
Explanation: The 0th customer cannot be given two different integers.

Example 2:

Input: nums = [1,2,3,3], quantity = [2]
Output: true
Explanation: The 0th customer is given [3,3]. The integers [1,2] are not used.

Example 3:

Input: nums = [1,1,2,2], quantity = [2,2]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [2,2].

Example 4:

Input: nums = [1,1,2,3], quantity = [2,2]
Output: false
Explanation: Although the 0th customer could be given [1,1], the 1st customer cannot be satisfied.

Example 5:

Input: nums = [1,1,1,1,1], quantity = [2,3]
Output: true
Explanation: The 0th customer is given [1,1], and the 1st customer is given [1,1,1].

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 1000
m == quantity.length
1 <= m <= 10
1 <= quantity[i] <= 10⁵
There are at most 50 unique values in nums.

Solution1: Backtracking

Time complexity: O(|vals|^m)
Space complexity: O(|vals| + m)

C++

// Author: Huahua

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

unordered_map<int, int> m;

for (int x : nums) ++m[x];

vector<int> cnt;

for (const auto& [x, c] : m) cnt.push_back(c);

const int q = quantity.size();

const int n = cnt.size();

function<bool(int)> dfs = [&](int d) {

if (d == q) return true;

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

if (cnt[i] >= quantity[d]) {

cnt[i] -= quantity[d];

if (dfs(d + 1)) return true;

cnt[i] += quantity[d];

}

return false;

};

sort(rbegin(cnt), rend(cnt));

sort(rbegin(quantity), rend(quantity));

return dfs(0);

}

};

Solution 2: Bitmask + all subsets

dp(mask, i) := whether we can distribute to a subset of customers represented as a bit mask, using the i-th to (n-1)-th numbers.

Time complexity: O(2^m * m * |vals|) = O(2^10 * 10 * 50)
Space complexity: O(2^m * |vals|)

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<vector<optional<bool>>> cache(1 << m, vector<optional<bool>>(n));

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

function<bool(int, int)> dp = [&](int mask, int i) -> bool {

if (mask == 0) return true;

if (i == n) return false;

auto& ans = cache[mask][i];

if (ans.has_value()) return ans.value();

int cur = mask;

while (cur) {

if (sums[cur] <= cnt[i] && dp(mask ^ cur, i + 1)) {

ans = true;

return true;

}

cur = (cur - 1) & mask;

}

ans = dp(mask, i + 1);

return ans.value();

};

return dp((1 << m) - 1, 0);

}

};

Python3

# Author: Huahua

class Solution:

def canDistribute(self, nums: List[int],

quantity: List[int]) -> bool:

cnts = list(Counter(nums).values())

m = len(quantity)

n = len(cnts)

sums = [0] * (1 << m)

for mask in range(1 << m):

for i in range(m):

if mask & (1 << i): sums[mask] += quantity[i]

@lru_cache(None)

def dp(mask: int, i: int) -> bool:

if not mask: return True

if i < 0: return False

cur = mask

while cur:

if sums[cur] <= cnts[i] and dp(mask ^ cur, i - 1):

return True

cur = (cur - 1) & mask

return dp(mask, i - 1)

return dp((1 << m) - 1, n - 1)

Bottom up:

C++

class Solution {

public:

bool canDistribute(vector<int>& nums, vector<int>& quantity) {

vector<int> cnt;

unordered_map<int, int> freq;

for (int x : nums) ++freq[x];

for (const auto& [x, f] : freq) cnt.push_back(f);

const int n = cnt.size();

const int m = quantity.size();

vector<int> sums(1 << m);

for (int mask = 0; mask < 1 << m; ++mask)

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

if (mask & (1 << i))

sums[mask] += quantity[i];

// dp[mask][i] := use first i types to satisfy mask customers.

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

dp[0][0] = 1;

for (int mask = 0; mask < 1 << m; ++mask)

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

dp[mask][i + 1] |= dp[mask][i];

for (int cur = mask; cur; cur = (cur - 1) & mask)

if (sums[cur] <= cnt[i] && dp[mask ^ cur][i])

dp[mask][i + 1] = 1;

}

return dp[(1 << m) - 1][n];

}

};

花花酱 LeetCode 1654. Minimum Jumps to Reach Home

By zxi on November 14, 2020

A certain bug’s home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

It can jump exactly a positions forward (to the right).
It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row.
It cannot jump to any forbidden positions.

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

Constraints:

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
All the elements in forbidden are distinct.
Position x is not forbidden.

Solution: BFS

Normal BFS with two tricks:
1. For each position, we need to track whether it’s reached via a forward jump or backward jump
2. How far should we go? If we don’t limit, it can go forever which leads to TLE/MLE. We can limit the distance to 2*max_jump, e.g. 4000, that’s maximum distance we can jump back to home in one shot.

Time complexity: O(max_distance * 2)
Space complexity: O(max_distance * 2)

C++

// Author: Huahua

class Solution {

public:

int minimumJumps(vector<int>& forbidden, int a, int b, int x) {

constexpr int kMaxPosition = 4000;

if (x == 0) return 0;

queue<pair<int, bool>> q{{{0, true}}};

unordered_set<int> seen1, seen2;

for (int f : forbidden) seen1.insert(f), seen2.insert(f);

seen1.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

auto [cur, forward] = q.front(); q.pop();

if (cur == x) return steps;

if (cur > kMaxPosition) continue; // no way to go back

if (seen1.insert(cur + a).second)

q.emplace(cur + a, true);

if (cur - b >= 0 && forward && seen2.insert(cur - b).second)

q.emplace(cur - b, false);

}

++steps;

}

return -1;

}

};

花花酱 LeetCode 1625. Lexicographically Smallest String After Applying Operations

By zxi on October 18, 2020

You are given a string s of even length consisting of digits from 0 to 9, and two integers a and b.

You can apply either of the following two operations any number of times and in any order on s:

Add a to all odd indices of s (0-indexed). Digits post 9 are cycled back to 0. For example, if s = "3456" and a = 5, s becomes "3951".
Rotate s to the right by b positions. For example, if s = "3456" and b = 1, s becomes "6345".

Return the lexicographically smallest string you can obtain by applying the above operations any number of times on s.

A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. For example, "0158" is lexicographically smaller than "0190" because the first position they differ is at the third letter, and '5' comes before '9'.

Example 1:

Input: s = "5525", a = 9, b = 2
Output: "2050"
Explanation: We can apply the following operations:
Start:  "5525"
Rotate: "2555"
Add:    "2454"
Add:    "2353"
Rotate: "5323"
Add:    "5222"
Add:    "5121"
Rotate: "2151"
Add:    "2050"
There is no way to obtain a string that is lexicographically smaller then "2050".

Example 2:

Input: s = "74", a = 5, b = 1
Output: "24"
Explanation: We can apply the following operations:
Start:  "74"
Rotate: "47"
Add:    "42"
Rotate: "24"
There is no way to obtain a string that is lexicographically smaller then "24".

Example 3:

Input: s = "0011", a = 4, b = 2
Output: "0011"
Explanation: There are no sequence of operations that will give us a lexicographically smaller string than "0011".

Example 4:

Input: s = "43987654", a = 7, b = 3
Output: "00553311"

Constraints:

2 <= s.length <= 100
s.length is even.
s consists of digits from 0 to 9 only.
1 <= a <= 9
1 <= b <= s.length - 1

Solution: Search

C++

// Author: Huahua

class Solution {

public:

string findLexSmallestString(string s, int a, int b) {

unordered_set<string> seen;

string ans(s);

function<void(string)> dfs = [&](const string& s) {

if (!seen.insert(s).second) return;

ans = min(ans, s);

string t(s);

for (int i = 1; i < s.length(); i += 2)

t[i] = (t[i] - '0' + a) % 10 + '0';

dfs(t);

dfs(s.substr(b) + s.substr(0, b));

};

dfs(s);

return ans;

}

};

花花酱 LeetCode 1601. Maximum Number of Achievable Transfer Requests

By zxi on September 27, 2020

We have n buildings numbered from 0 to n - 1. Each building has a number of employees. It’s transfer season, and some employees want to change the building they reside in.

You are given an array requests where requests[i] = [from_i, to_i] represents an employee’s request to transfer from building from_i to building to_i.

All buildings are full, so a list of requests is achievable only if for each building, the net change in employee transfers is zero. This means the number of employees leaving is equal to the number of employees moving in. For example if n = 3 and two employees are leaving building 0, one is leaving building 1, and one is leaving building 2, there should be two employees moving to building 0, one employee moving to building 1, and one employee moving to building 2.

Return the maximum number of achievable requests.

Example 1:

Input: n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
Output: 5
Explantion: Let's see the requests:
From building 0 we have employees x and y and both want to move to building 1.
From building 1 we have employees a and b and they want to move to buildings 2 and 0 respectively.
From building 2 we have employee z and they want to move to building 0.
From building 3 we have employee c and they want to move to building 4.
From building 4 we don't have any requests.
We can achieve the requests of users x and b by swapping their places.
We can achieve the requests of users y, a and z by swapping the places in the 3 buildings.

Example 2:

Input: n = 3, requests = [[0,0],[1,2],[2,1]]
Output: 3
Explantion: Let's see the requests:
From building 0 we have employee x and they want to stay in the same building 0.
From building 1 we have employee y and they want to move to building 2.
From building 2 we have employee z and they want to move to building 1.
We can achieve all the requests.

Example 3:

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

Constraints:

1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= from_i, to_i < n

Solution: Combination

Try all combinations: O(2^n * (r + n))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maximumRequests(int n, vector<vector<int>>& requests) {

const int r = requests.size();

int ans = 0;

vector<int> nets(n);

for (int s = 0; s < 1 << r; ++s) {

fill(begin(nets), end(nets), 0);

for (int j = 0; j < r; ++j)

if (s & (1 << j)) {

--nets[requests[j][0]];

++nets[requests[j][1]];

}

if (all_of(begin(nets), end(nets), [](const int x) { return x == 0; }))

ans = max(ans, __builtin_popcount(s));

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

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

r = len(requests)

ans = 0

for s in range(1 << r):

degrees = [0] * n

for i in range(r):

if s & (1 << i):

degrees[requests[i][0]] -= 1

degrees[requests[i][1]] += 1

if not any(degrees):

ans = max(ans, bin(s).count('1'))

return ans

花花酱 LeetCode 1593. Split a String Into the Max Number of Unique Substrings

By zxi on September 21, 2020

Given a string s, return the maximum number of unique substrings that the given string can be split into.

You can split string s into any list of non-empty substrings, where the concatenation of the substrings forms the original string. However, you must split the substrings such that all of them are unique.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "ababccc"
Output: 5
Explanation: One way to split maximally is ['a', 'b', 'ab', 'c', 'cc']. Splitting like ['a', 'b', 'a', 'b', 'c', 'cc'] is not valid as you have 'a' and 'b' multiple times.

Example 2:

Input: s = "aba"
Output: 2
Explanation: One way to split maximally is ['a', 'ba'].

Example 3:

Input: s = "aa"
Output: 1
Explanation: It is impossible to split the string any further.

Constraints:

1 <= s.length <= 16
s contains only lower case English letters.

Solution: Brute Force

Try all combinations.
Time complexity: O(2^n)
Space complexity: O(n)

Iterative/C++

// Author: Huahua

class Solution {

public:

int maxUniqueSplit(string_view s) {

const int n = s.length();

if (n == 1) return 1;

size_t ans = 1;

unordered_set<string_view> seen;

for (int m = 1; m < 1 << (n - 1); ++m) {

if (__builtin_popcount(m) < ans) continue; // 956 ms -> 52 ms

bool valid = true;

int p = 0;

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

if (m & (1 << (i - 1)) || i == n) {

valid &= seen.insert(s.substr(p, i - p)).second;

p = i;

}

if (valid) ans = max(ans, seen.size());

seen.clear();

}

return ans;

}

};

DFS/C++

// Author: Huahua

class Solution {

public:

int maxUniqueSplit(string_view s) {

size_t ans = 1;

const int n = s.length();

unordered_set<string_view> seen;

function<void(int)> dfs = [&](int p) {

if (p == n) {

ans = max(ans, seen.size());

return;

}

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

string_view ss = s.substr(p, i - p + 1);

if (!seen.insert(ss).second) continue;

dfs(i + 1);

seen.erase(ss);

}

};

dfs(0);

return ans;

}

};