Posts published in “Search”

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

}

};

花花酱 LeetCode 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

By zxi on June 3, 2020

Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i.

All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).

Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).

We want to calculate the probability that the two boxes have the same number of distinct balls.

Example 1:

Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:

Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1/12):
[1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1]
After that we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:

Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:

Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:

Input: balls = [6,6,6,6,6,6]
Output: 0.90327

Constraints:

1 <= balls.length <= 8
1 <= balls[i] <= 6
sum(balls) is even.
Answers within 10^-5 of the actual value will be accepted as correct.

Solution 0: Permutation (TLE)

Enumerate all permutations of the balls, count valid ones and divide that by the total.

Time complexity: O((8*6)!) = O(48!)
After deduplication: O(48!/(6!)^8) ~ 1.7e38
Space complexity: O(8*6)

C++

// Author: Huahua, TLE 4/21 passed

class Solution {

public:

double getProbability(vector<int>& balls) {

const int k = balls.size();

vector<int> bs;

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

for (int j = 0; j < balls[i]; ++j)

bs.push_back(i);

const int n = bs.size();

double total = 0.0;

double valid = 0.0;

// d : depth

// used : bitmap of bs's usage

// c1: bitmap of colors of box1

// c2: bitmap of colors of box1

function<void(int, long, int, int)> dfs = [&](int d, long used, int c1, int c2) {

if (d == n) {

total += 1;

valid += __builtin_popcount(c1) == __builtin_popcount(c2);

return;

}

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

if (used & (1L << i)) continue;

// Deduplication.

if (i > 0 && bs[i] == bs[i - 1] && !(used & (1L << (i - 1)))) continue;

int tc1 = (d < n / 2) ? (c1 | (1 << bs[i])) : c1;

int tc2 = (d < n / 2) ? c2 : (c2 | (1 << bs[i]));

dfs(d + 1, used | (1L << i), tc1, tc2);

}

};

dfs(0, 0, 0, 0);

return valid / total;

}

};

Solution 1: Combination

For each color, put n_i balls into box1, the left t_i – n_i balls go to box2.
permutations = fact(n//2) / PROD(fact(n_i)) * fact(n//2) * PROD(fact(t_i – n_i))
E.g
balls = [1×2, 2×6, 3×4]
One possible combination:
box1: 1 22 333
box2: 1 2222 3
permutations = 6! / (1! * 2! * 3!) * 6! / (1! * 4! * 1!) = 1800

Time complexity: O((t+1)^k) = O(7^8)
Space complexity: O(k + (t*k)) = O(8 + 48)

C++

// Author: Huahua

class Solution {

public:

double getProbability(vector<int>& balls) {

const int n = accumulate(begin(balls), end(balls), 0);

const int k = balls.size();

double total = 0.0;

double valid = 0.0;

vector<double> fact(50, 1.0);

for (int i = 1; i < fact.size(); ++i)

fact[i] = fact[i - 1] * i;

// d: depth

// b1, b2: # of balls in box1, box2

// c1, c2: # of distinct colors in box1, box2

// p1, p2: # permutations of duplicate balls in box1, box2

function<void(int, int, int, int, int, double, double)> dfs = [&]

(int d, int b1, int b2, int c1, int c2, double p1, double p2) {

if (b1 > n / 2 || b2 > n / 2) return;

if (d == k) {

const double count = fact[b1] / p1 * fact[b2] / p2;

total += count;

valid += count * (c1 == c2);

return;

}

for (int s1 = 0; s1 <= balls[d]; ++s1) {

const int s2 = balls[d] - s1;

dfs(d + 1,

b1 + s1,

b2 + s2,

c1 + (s1 > 0),

c2 + (s2 > 0),

p1 * fact[s1],

p2 * fact[s2]);

}

};

dfs(0, 0, 0, 0, 0, 1.0, 1.0);

return valid / total;

}

};

vector version

C++

// Author: Huahua

class Solution {

public:

double getProbability(vector<int>& balls) {

const int k = balls.size();

const int n = accumulate(begin(balls), end(balls), 0);

vector<double> fact(49, 1.0);

for (int i = 1; i < fact.size(); ++i)

fact[i] = fact[i - 1] * i;

auto perms = [&](const vector<int>& bs, int n) -> double {

double p = fact[n];

for (int b : bs) p /= fact[b];

return p;

};

vector<int> box1, box2;

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

const int n1 = accumulate(begin(box1), end(box1), 0);

const int n2 = accumulate(begin(box2), end(box2), 0);

if (n1 > n / 2 || n2 > n / 2) return 0;

if (d == k)

return (box1.size() == box2.size()) * perms(box1, n1) * perms(box2, n2);

double total = 0;

for (int s1 = 0; s1 <= balls[d]; ++s1) {

const int s2 = balls[d] - s1;

if (s1) box1.push_back(s1);

if (s2) box2.push_back(s2);

total += dfs(d + 1);

if (s1) box1.pop_back();

if (s2) box2.pop_back();

}

return total;

};

return dfs(0) / perms(balls, n);

}

};

花花酱 LeetCode 1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

By zxi on May 5, 2020

You are given an m * n matrix, mat, and an integer k, which has its rows sorted in non-decreasing order.

You are allowed to choose exactly 1 element from each row to form an array. Return the Kth smallest array sum among all possible arrays.

Example 1:

Input: mat = [[1,3,11],[2,4,6]], k = 5
Output: 7
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,2], [1,4], [3,2], [3,4], [1,6]. Where the 5th sum is 7.

Example 2:

Input: mat = [[1,3,11],[2,4,6]], k = 9
Output: 17

Example 3:

Input: mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
Output: 9
Explanation: Choosing one element from each row, the first k smallest sum are:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]. Where the 7th sum is 9.

Example 4:

Input: mat = [[1,1,10],[2,2,9]], k = 7
Output: 12

Constraints:

m == mat.length
n == mat.length[i]
1 <= m, n <= 40
1 <= k <= min(200, n ^ m)
1 <= mat[i][j] <= 5000
mat[i] is a non decreasing array.

Solution 1: Priority Queue

Generate the arrays in order.

Each node is {sum, idx_0, idx_1, …, idx_m},

Start with {sum_0, 0, 0, …, 0}.

For expansion, pick one row and increase its index

Time complexity: O(k * m ^ 2* log k)
Space complexity: O(k)

C++

// Author: Huahua

class Solution {

public:

int kthSmallest(vector<vector<int>>& mat, int k) {

const int m = mat.size();

const int n = mat[0].size();

priority_queue<vector<int>> q;

vector<int> node(m + 1); // {-sum, idx_0, idx_1, ..., idx_m}

for (int i = 0; i < m; ++i) node[0] -= mat[i][0];

q.push(node);

set<vector<int>> seen{{node}};

while (!q.empty()) {

const vector<int> cur = q.top(); q.pop();

if (--k == 0) return -cur[0];

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

if (cur[i] == n - 1) continue;

vector<int> nxt(cur);

++nxt[i]; // increase i-th row's index.

// Update sum.

nxt[0] -= (mat[i - 1][nxt[i]] - mat[i - 1][nxt[i] - 1]);

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

q.push(move(nxt));

}

return -1;

}

};