Posts tagged as “search”

花花酱 LeetCode 2048. Next Greater Numerically Balanced Number

By zxi on October 25, 2021

An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.

Given an integer n, return the smallest numerically balanced number strictly greater than n.

Example 1:

Input: n = 1
Output: 22
Explanation: 
22 is numerically balanced since:
- The digit 2 occurs 2 times. 
It is also the smallest numerically balanced number strictly greater than 1.

Example 2:

Input: n = 1000
Output: 1333
Explanation: 
1333 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times. 
It is also the smallest numerically balanced number strictly greater than 1000.
Note that 1022 cannot be the answer because 0 appeared more than 0 times.

Example 3:

Input: n = 3000
Output: 3133
Explanation: 
3133 is numerically balanced since:
- The digit 1 occurs 1 time.
- The digit 3 occurs 3 times.
It is also the smallest numerically balanced number strictly greater than 3000.

Constraints:

0 <= n <= 10⁶

Solution: Permutation

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

C++

// Author: Huahua

class Solution {

public:

int nextBeautifulNumber(int n) {

const string t = to_string(n);

vector<int> nums{1,

22,

122, 333,

1333, 4444,

14444, 22333, 55555,

122333, 155555, 224444, 666666};

int ans = 1224444;

for (int num : nums) {

string s = to_string(num);

if (s.size() < t.size()) continue;

else if (s.size() > t.size()) {

ans = min(ans, num);

} else { // same length

do {

if (s > t) ans = min(ans, stoi(s));

} while (next_permutation(begin(s), end(s)));

}

return ans;

}

};

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