Posts tagged as “DFS”

花花酱 LeetCode 1849. Splitting a String Into Descending Consecutive Values

By zxi on May 2, 2021

You are given a string s that consists of only digits.

Check if we can split s into two or more non-empty substrings such that the numerical values of the substrings are in descending order and the difference between numerical values of every two adjacent substrings is equal to 1.

For example, the string s = "0090089" can be split into ["0090", "089"] with numerical values [90,89]. The values are in descending order and adjacent values differ by 1, so this way is valid.
Another example, the string s = "001" can be split into ["0", "01"], ["00", "1"], or ["0", "0", "1"]. However all the ways are invalid because they have numerical values [0,1], [0,1], and [0,0,1] respectively, all of which are not in descending order.

Return true if it is possible to split s as described above, or false otherwise.

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

Example 1:

Input: s = "1234"
Output: false
Explanation: There is no valid way to split s.

Example 2:

Input: s = "050043"
Output: true
Explanation: s can be split into ["05", "004", "3"] with numerical values [5,4,3].
The values are in descending order with adjacent values differing by 1.

Example 3:

Input: s = "9080701"
Output: false
Explanation: There is no valid way to split s.

Example 4:

Input: s = "10009998"
Output: true
Explanation: s can be split into ["100", "099", "98"] with numerical values [100,99,98].
The values are in descending order with adjacent values differing by 1.

Constraints:

1 <= s.length <= 20
s only consists of digits.

Solution: DFS

Time complexity: O(2ⁿ)
Space complexity: O(n)

C++

class Solution {

public:

bool splitString(string s) {

const int n = s.length();

vector<long> nums;

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

if (p == n) return nums.size() >= 2;

long cur = 0;

for (int i = p; i < n && cur < 1e11; ++i) {

cur = cur * 10 + (s[i] - '0');

if (nums.empty() || cur + 1 == nums.back()) {

nums.push_back(cur);

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

nums.pop_back();

}

if (!nums.empty() && cur >= nums.back()) break;

}

return false;

};

return dfs(0);

}

};

花花酱 LeetCode 1815. Maximum Number of Groups Getting Fresh Donuts

By zxi on April 5, 2021

There is a donuts shop that bakes donuts in batches of batchSize. They have a rule where they must serve all of the donuts of a batch before serving any donuts of the next batch. You are given an integer batchSize and an integer array groups, where groups[i] denotes that there is a group of groups[i] customers that will visit the shop. Each customer will get exactly one donut.

When a group visits the shop, all customers of the group must be served before serving any of the following groups. A group will be happy if they all get fresh donuts. That is, the first customer of the group does not receive a donut that was left over from the previous group.

You can freely rearrange the ordering of the groups. Return the maximum possible number of happy groups after rearranging the groups.

Example 1:

Input: batchSize = 3, groups = [1,2,3,4,5,6]
Output: 4
Explanation: You can arrange the groups as [6,2,4,5,1,3]. Then the 1^st, 2^nd, 4^th, and 6^th groups will be happy.

Example 2:

Input: batchSize = 4, groups = [1,3,2,5,2,2,1,6]
Output: 4

Constraints:

1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 10⁹

Solution 0: Binary Mask DP

Time complexity: O(n*2ⁿ) TLE
Space complexity: O(2ⁿ)

C++

// Author: Huahua, TLE, 42/67 Passed

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

const int n = groups.size();

vector<int> dp(1 << n);

for (int mask = 0; mask < 1 << n; ++mask) {

int s = 0;

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

if (mask & (1 << i)) s = (s + groups[i]) % b;

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

if (!(mask & (1 << i)))

dp[mask | (1 << i)] = max(dp[mask | (1 << i)],

dp[mask] + (s == 0));

}

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

}

};

Solution 1: Recursion w/ Memoization

State: count of group size % batchSize

C++

// Author: Huahua, 888 ms, 61.9 MB

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

map<vector<int>, int> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

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

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

C++/Hashtable

// Author: Huahua 380 ms, 59.2 MB

struct VectorHasher {

size_t operator()(const vector<int>& V) const {

size_t hash = V.size();

for (auto i : V)

hash ^= i + 0x9e3779b9 + (hash << 6) + (hash >> 2);

return hash;

}

};

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) ++count[g % b];

unordered_map<vector<int>, int, VectorHasher> cache;

function<int(int)> dp = [&](int s) {

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

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

if (!count[i]) continue;

--count[i];

ans = max(ans, (s == 0) + dp((s + b - i) % b));

++count[i];

}

return cache[count] = ans;

};

return count[0] + dp(0);

}

};

C++/OPT

// Author: Huahua, 0 ms, 8.1 MB

class Solution {

public:

int maxHappyGroups(int b, vector<int>& groups) {

int ans = 0;

vector<int> count(b);

for (int g : groups) {

const int r = g % b;

if (r == 0) { ++ans; continue; }

if (count[b - r]) {

--count[b - r];

++ans;

} else {

++count[r];

}

map<vector<int>, int> cache;

function<int(int, int)> dp = [&](int r, int n) {

if (n == 0) return 0;

auto it = cache.find(count);

if (it != cache.end()) return it->second;

int ans = 0;

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

if (!count[i]) continue;

--count[i];

ans = max(ans, (r == 0) + dp((r + b - i) % b, n - 1));

++count[i];

}

return cache[count] = ans;

};

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

return ans + (n ? dp(0, n) : 0);

}

};

花花酱 LeetCode 1774. Closest Dessert Cost

By zxi on February 27, 2021

You would like to make dessert and are preparing to buy the ingredients. You have n ice cream base flavors and m types of toppings to choose from. You must follow these rules when making your dessert:

There must be exactly one ice cream base.
You can add one or more types of topping or have no toppings at all.
There are at most two of each type of topping.

You are given three inputs:

baseCosts, an integer array of length n, where each baseCosts[i] represents the price of the i^th ice cream base flavor.
toppingCosts, an integer array of length m, where each toppingCosts[i] is the price of one of the i^th topping.
target, an integer representing your target price for dessert.

You want to make a dessert with a total cost as close to target as possible.

Return the closest possible cost of the dessert to target. If there are multiple, return the lower one.

Example 1:

Input: baseCosts = [1,7], toppingCosts = [3,4], target = 10
Output: 10
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 7
- Take 1 of topping 0: cost 1 x 3 = 3
- Take 0 of topping 1: cost 0 x 4 = 0
Total: 7 + 3 + 0 = 10.

Example 2:

Input: baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
Output: 17
Explanation: Consider the following combination (all 0-indexed):
- Choose base 1: cost 3
- Take 1 of topping 0: cost 1 x 4 = 4
- Take 2 of topping 1: cost 2 x 5 = 10
- Take 0 of topping 2: cost 0 x 100 = 0
Total: 3 + 4 + 10 + 0 = 17. You cannot make a dessert with a total cost of 18.

Example 3:

Input: baseCosts = [3,10], toppingCosts = [2,5], target = 9
Output: 8
Explanation: It is possible to make desserts with cost 8 and 10. Return 8 as it is the lower cost.

Example 4:

Input: baseCosts = [10], toppingCosts = [1], target = 1
Output: 10
Explanation: Notice that you don't have to have any toppings, but you must have exactly one base.

Constraints:

n == baseCosts.length
m == toppingCosts.length
1 <= n, m <= 10
1 <= baseCosts[i], toppingCosts[i] <= 10⁴
1 <= target <= 10⁴

Solution: DP / Knapsack

Pre-compute the costs of all possible combinations of toppings.

Time complexity: O(sum(toppings) * 2 * (m + n)) ~ O(10^6)
Space complexity: O(sum(toppings)) ~ O(10^5)

C++

// Author: Huahua

class Solution {

public:

int closestCost(vector<int>& bs, vector<int>& ts, int target) {

const int kMax = 2 * accumulate(begin(ts), end(ts), 0);

int min_diff = INT_MAX;

int ans = INT_MAX;

vector<int> dp(kMax + 1);

dp[0] = 1;

for (int t : ts) {

for (int i = kMax; i >= 0; --i) {

if (!dp[i]) continue;

if (i + t <= kMax) dp[i + t] = 1;

if (i + 2 * t <= kMax) dp[i + 2 * t] = 1;

}

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

if (!dp[i]) continue;

for (int b : bs) {

const int diff = abs(b + i - target);

if (diff < min_diff || diff == min_diff && b + i < ans) {

min_diff = diff;

ans = b + i;

}

return ans;

}

};

Solution 2: DFS

Combination

Time complexity: O(3^m * n)
Space complexity: O(m)

C++

// Author: Huahua

class Solution {

public:

int closestCost(vector<int>& bs, vector<int>& ts, int target) {

const int m = ts.size();

int min_diff = INT_MAX;

int ans = INT_MAX;

function<void(int, int)> dfs = [&](int s, int cur) {

if (s == m) {

for (int b : bs) {

const int total = b + cur;

const int diff = abs(total - target);

if (diff < min_diff

|| diff == min_diff && total < ans) {

min_diff = diff;

ans = total;

}

return;

}

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

dfs(i + 1, cur);

dfs(i + 1, cur + ts[i]);

dfs(i + 1, cur + ts[i] * 2);

}

};

dfs(0, 0);

return ans;

}

};

花花酱 LeetCode 1766. Tree of Coprimes

By zxi on February 20, 2021

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of n nodes numbered from 0 to n - 1 and exactly n - 1 edges. Each node has a value associated with it, and the root of the tree is node 0.

To represent this tree, you are given an integer array nums and a 2D array edges. Each nums[i] represents the i^th node’s value, and each edges[j] = [u_j, v_j] represents an edge between nodes u_j and v_j in the tree.

Two values x and y are coprime if gcd(x, y) == 1 where gcd(x, y) is the greatest common divisor of x and y.

An ancestor of a node i is any other node on the shortest path from node i to the root. A node is not considered an ancestor of itself.

Return an array ans of size n, where ans[i] is the closest ancestor to node i such that nums[i] and nums[ans[i]] are coprime, or -1 if there is no such ancestor.

Example 1:

Input: nums = [2,3,3,2], edges = [[0,1],[1,2],[1,3]]
Output: [-1,0,0,1]
Explanation: In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

Example 2:

Input: nums = [5,6,10,2,3,6,15], edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: [-1,0,-1,0,0,0,-1]

Constraints:

nums.length == n
1 <= nums[i] <= 50
1 <= n <= 10⁵
edges.length == n - 1
edges[j].length == 2
0 <= u_j, v_j < n
u_j != v_j

Solution: DFS + Stack

Pre-compute for coprimes for each number.

For each node, enumerate all it’s coprime numbers, find the deepest occurrence.

Time complexity: O(n * max(nums))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> getCoprimes(vector<int>& nums, vector<vector<int>>& edges) {

constexpr int kMax = 50;

const int n = nums.size();

vector<vector<int>> g(n);

for (const auto& e : edges) {

g[e[0]].push_back(e[1]);

g[e[1]].push_back(e[0]);

}

vector<vector<int>> coprime(kMax + 1);

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

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

if (gcd(i, j) == 1) coprime[i].push_back(j);

vector<int> ans(n, INT_MAX);

vector<vector<pair<int, int>>> p(kMax + 1);

function<void(int, int)> dfs = [&](int cur, int d) {

int max_d = -1;

int ancestor = -1;

for (int co : coprime[nums[cur]])

if (!p[co].empty() && p[co].back().first > max_d) {

max_d = p[co].back().first;

ancestor = p[co].back().second;

}

ans[cur] = ancestor;

p[nums[cur]].emplace_back(d, cur);

for (int nxt : g[cur])

if (ans[nxt] == INT_MAX) dfs(nxt, d + 1);

p[nums[cur]].pop_back();

};

dfs(0, 0);

return ans;

}

};

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