Posts published in “Search”

花花酱 LeetCode 2044. Count Number of Maximum Bitwise-OR Subsets

By zxi on October 17, 2021

Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

An array a is a subset of an array b if a can be obtained from b by deleting some (possibly zero) elements of b. Two subsets are considered different if the indices of the elements chosen are different.

The bitwise OR of an array a is equal to a[0] OR a[1] OR ... OR a[a.length - 1] (0-indexed).

Example 1:

Input: nums = [3,1]
Output: 2
Explanation: The maximum possible bitwise OR of a subset is 3. There are 2 subsets with a bitwise OR of 3:
- [3]
- [3,1]

Example 2:

Input: nums = [2,2,2]
Output: 7
Explanation: All non-empty subsets of [2,2,2] have a bitwise OR of 2. There are 2³ - 1 = 7 total subsets.

Example 3:

Input: nums = [3,2,1,5]
Output: 6
Explanation: The maximum possible bitwise OR of a subset is 7. There are 6 subsets with a bitwise OR of 7:
- [3,5]
- [3,1,5]
- [3,2,5]
- [3,2,1,5]
- [2,5]
- [2,1,5]

Constraints:

1 <= nums.length <= 16
1 <= nums[i] <= 10⁵

Solution: Brute Force

Try all possible subsets

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

C++

// Author: Huahua

class Solution {

public:

int countMaxOrSubsets(vector<int>& nums) {

const int n = nums.size();

int max_or = 0;

int count = 0;

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

int cur_or = 0;

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

if (s >> i & 1) cur_or |= nums[i];

if (cur_or > max_or) {

max_or = cur_or;

count = 1;

} else if (cur_or == max_or) {

++count;

}

return count;

}

};

花花酱 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 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 1765. Map of Highest Peak

By zxi on February 20, 2021

You are given an integer matrix isWater of size m x n that represents a map of land and water cells.

If isWater[i][j] == 0, cell (i, j) is a land cell.
If isWater[i][j] == 1, cell (i, j) is a water cell.

You must assign each cell a height in a way that follows these rules:

The height of each cell must be non-negative.
If the cell is a water cell, its height must be 0.
Any two adjacent cells must have an absolute height difference of at most 1. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is maximized.

Return an integer matrix height of size m x n where height[i][j] is cell (i, j)‘s height. If there are multiple solutions, return any of them.

Example 1:

Input: isWater = [[0,1],[0,0]]
Output: [[1,0],[2,1]]
Explanation: The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

Example 2:

Input: isWater = [[0,0,1],[1,0,0],[0,0,0]]
Output: [[1,1,0],[0,1,1],[1,2,2]]
Explanation: A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

Constraints:

m == isWater.length
n == isWater[i].length
1 <= m, n <= 1000
isWater[i][j] is 0 or 1.
There is at least one water cell.

Solution: BFS

h[y][x] = min distance of (x, y) to any water cell.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {

const int m = isWater.size();

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

vector<vector<int>> ans(m, vector<int>(n, INT_MIN));

queue<pair<int, int>> q;

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

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

if (isWater[y][x]) {

q.emplace(x, y);

ans[y][x] = 0;

}

const vector<int> dirs{0, -1, 0, 1, 0};

while (!q.empty()) {

const auto [cx, cy] = q.front();

q.pop();

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

const int x = cx + dirs[i];

const int y = cy + dirs[i + 1];

if (x < 0 || x >= n || y < 0 || y >= m) continue;

if (ans[y][x] != INT_MIN) continue;

ans[y][x] = ans[cy][cx] + 1;

q.emplace(x, y);

}

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