Posts tagged as “medium”

花花酱 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 1621. Number of Sets of K Non-Overlapping Line Segments

By zxi on October 17, 2020

Given n points on a 1-D plane, where the i^th point (from 0 to n-1) is at x = i, find the number of ways we can draw exactly k non-overlapping line segments such that each segment covers two or more points. The endpoints of each segment must have integral coordinates. The k line segments do not have to cover all n points, and they are allowed to share endpoints.

Return the number of ways we can draw k non-overlapping line segments. Since this number can be huge, return it modulo 10⁹ + 7.

Example 1:

Input: n = 4, k = 2
Output: 5
Explanation: 
The two line segments are shown in red and blue.
The image above shows the 5 different ways {(0,2),(2,3)}, {(0,1),(1,3)}, {(0,1),(2,3)}, {(1,2),(2,3)}, {(0,1),(1,2)}.

Example 2:

Input: n = 3, k = 1
Output: 3
Explanation: The 3 ways are {(0,1)}, {(0,2)}, {(1,2)}.

Example 3:

Input: n = 30, k = 7
Output: 796297179
Explanation: The total number of possible ways to draw 7 line segments is 3796297200. Taking this number modulo 10⁹ + 7 gives us 796297179.

Example 4:

Input: n = 5, k = 3
Output: 7

Example 5:

Input: n = 3, k = 2
Output: 1

Constraints:

2 <= n <= 1000
1 <= k <= n-1

Solution 1: Naive DP (TLE)

dp[n][k] := ans of problem(n, k)
dp[n][1] = n * (n – 1) / 2 # C(n,2)
dp[n][k] = 1 if k == n – 1
dp[n][k] = 0 if k >= n
dp[n][k] = sum((i – 1) * dp(n – i + 1, k – 1) 2 <= i < n

Time complexity: O(n^2*k)
Space complexity: O(n*k)

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> cache(n + 1, vector<int>(k + 1));

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

if (k >= n) return 0;

if (k == 1) return n * (n - 1) / 2;

if (k == n - 1) return 1;

int& ans = cache[n][k];

if (ans) return ans;

for (long i = 2; i < n; ++i) {

const int t = ((i - 1) * dp(n - i + 1, k - 1)) % kMod;

ans = (ans + t) % kMod;

}

return ans;

};

return dp(n, k);

}

};

Solution 2: DP w/ Prefix Sum

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

kMod = 10**9 + 7

dp = [[0] * (k + 1) for _ in range(n + 1)]

for i in range(n + 1):

dp[i][0] = 1

for j in range(1, k + 1):

s = 0

for i in range(1, n + 1):

dp[i][j] = (s + dp[i - 1][j])

s += dp[i][j - 1]

return dp[n][k] % kMod

Solution 3: DP / 3D State

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 940 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

kMod = 10**9 + 7

@lru_cache(None)

def dp(n: int, k: int, e: int) -> int:

if k == 0: return 1

if k > n: return 0

return (dp(n - 1, k, e) + dp(n + e - 1, k - e, 1 - e)) % kMod

return dp(n, k, 0)

Solution 4: DP / Mathematical induction

Time complexity: O(nk)
Space complexity: O(nk)

Python3

# Author: Huahua 648 ms

class Solution:

def numberOfSets(self, n: int, k: int) -> int:

@lru_cache(None)

def dp(n: int, k: int) -> int:

if k >= n: return 0

if k == 1: return n * (n - 1) // 2

if k == n - 1: return 1

return 2 * dp(n - 1, k) - dp(n - 2, k) + dp(n - 1, k - 1)

return dp(n, k) % (10**9 + 7)

Solution 5: DP / Reduction

This problem can be reduced to: given n + k – 1 points, pick k segments (2*k points).
if two consecutive points were selected by two segments e.g. i for A and i+1 for B, then they share a point in the original space.
Answer C(n + k – 1, 2*k)

Time complexity: O((n+k)*2) Pascal’s triangle
Space complexity: O((n+k)*2)

C++

class Solution {

public:

int numberOfSets(int n, int k) {

constexpr int kMod = 1e9 + 7;

vector<vector<int>> dp(n + k , vector<int>(n + k));

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

dp[i][0] = dp[i][i] = 1;

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

dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % kMod;

}

return dp[n + k - 1][2 * k];

}

};

花花酱 LeetCode 1620. Coordinate With Maximum Network Quality

By zxi on October 17, 2020

You are given an array of network towers towers and an integer radius, where towers[i] = [x_i, y_i, q_i] denotes the i^th network tower with location (x_i, y_i) and quality factor q_i. All the coordinates are integral coordinates on the X-Y plane, and the distance between two coordinates is the Euclidean distance.

The integer radius denotes the maximum distance in which the tower is reachable. The tower is reachable if the distance is less than or equal to radius. Outside that distance, the signal becomes garbled, and the tower is not reachable.

The signal quality of the i^th tower at a coordinate (x, y) is calculated with the formula ⌊q_i / (1 + d)⌋, where d is the distance between the tower and the coordinate. The network quality at a coordinate is the sum of the signal qualities from all the reachable towers.

Return the integral coordinate where the network quality is maximum. If there are multiple coordinates with the same network quality, return the lexicographically minimum coordinate.

Note:

A coordinate (x1, y1) is lexicographically smaller than (x2, y2) if either x1 < x2 or x1 == x2 and y1 < y2.
⌊val⌋ is the greatest integer less than or equal to val (the floor function).

Example 1:

Input: towers = [[1,2,5],[2,1,7],[3,1,9]], radius = 2
Output: [2,1]
Explanation: 
At coordinate (2, 1) the total quality is 13
- Quality of 7 from (2, 1) results in ⌊7 / (1 + sqrt(0)⌋ = ⌊7⌋ = 7
- Quality of 5 from (1, 2) results in ⌊5 / (1 + sqrt(2)⌋ = ⌊2.07⌋ = 2
- Quality of 9 from (3, 1) results in ⌊9 / (1 + sqrt(1)⌋ = ⌊4.5⌋ = 4
No other coordinate has higher quality.

Example 2:

Input: towers = [[23,11,21]], radius = 9
Output: [23,11]

Example 3:

Input: towers = [[1,2,13],[2,1,7],[0,1,9]], radius = 2
Output: [1,2]

Example 4:

Input: towers = [[2,1,9],[0,1,9]], radius = 2
Output: [0,1]
Explanation: Both (0, 1) and (2, 1) are optimal in terms of quality but (0, 1) is lexicograpically minimal.

Constraints:

1 <= towers.length <= 50
towers[i].length == 3
0 <= x_i, y_i, q_i <= 50
1 <= radius <= 50

Solution: Brute Force

Try all possible coordinates from (0, 0) to (50, 50).

Time complexity: O(|X|*|Y|*t)
Space complexity: O(1)

C++

class Solution {

public:

vector<int> bestCoordinate(vector<vector<int>>& towers, int radius) {

constexpr int n = 50;

vector<int> ans;

int max_q = 0;

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

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

int q = 0;

for (const auto& tower : towers) {

const int tx = tower[0], ty = tower[1];

const float d = sqrt((x - tx) * (x - tx) + (y - ty) * (y - ty));

if (d > radius) continue;

q += floor(tower[2] / (1 + d));

}

if (q > max_q) {

max_q = q;

ans = {x, y};

}

return ans;

}

};

花花酱 LeetCode 1616. Split Two Strings to Make Palindrome

By zxi on October 10, 2020

You are given two strings a and b of the same length. Choose an index and split both strings at the same index, splitting a into two strings: a_prefix and a_suffix where a = a_prefix + a_suffix, and splitting b into two strings: b_prefix and b_suffix where b = b_prefix + b_suffix. Check if a_prefix + b_suffix or b_prefix + a_suffix forms a palindrome.

When you split a string s into s_prefix and s_suffix, either s_suffix or s_prefix is allowed to be empty. For example, if s = "abc", then "" + "abc", "a" + "bc", "ab" + "c" , and "abc" + "" are valid splits.

Return true if it is possible to form a palindrome string, otherwise return false.

Notice that x + y denotes the concatenation of strings x and y.

Example 1:

Input: a = "x", b = "y"
Output: true
Explaination: If either a or b are palindromes the answer is true since you can split in the following way:
a_prefix = "", a_suffix = "x"
b_prefix = "", b_suffix = "y"
Then, a_prefix + b_suffix = "" + "y" = "y", which is a palindrome.

Example 2:

Input: a = "abdef", b = "fecab"
Output: true

Example 3:

Input: a = "ulacfd", b = "jizalu"
Output: true
Explaination: Split them at index 3:
a_prefix = "ula", a_suffix = "cfd"
b_prefix = "jiz", b_suffix = "alu"
Then, a_prefix + b_suffix = "ula" + "alu" = "ulaalu", which is a palindrome.

Example 4:

Input: a = "xbdef", b = "xecab"
Output: false

Constraints:

1 <= a.length, b.length <= 10⁵
a.length == b.length
a and b consist of lowercase English letters

Solution: Greedy

Try to match the prefix of A and suffix of B (or the other way) as much as possible and then check whether the remaining part is a palindrome or not.

e.g. A = “abcxyzzz”, B = “uuuvvcba”
A’s prefix abc matches B’s suffix cba
We just need to check whether “xy” or “vv” is palindrome or not.
The concatenated string “abc|vvcba” is a palindrome, left abc is from A and vvcba is from B.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkPalindromeFormation(string a, string b) {

auto isPalindrome = [](const string& s, int i, int j) {

while (i < j && s[i] == s[j]) ++i, --j;

return i >= j;

};

auto check = [&isPalindrome](const string& a, const string& b) {

int i = 0;

int j = a.length() - 1;

while (a[i] == b[j]) ++i, --j;

return isPalindrome(a, i, j) || isPalindrome(b, i, j);

};

return check(a, b) || check(b, a);

}

};

花花酱 LeetCode 1615. Maximal Network Rank

By zxi on October 10, 2020

There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [a_i, b_i] indicates that there is a bidirectional road between cities a_i and b_i.

The network rankof two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.

The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.

Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.

Example 1:

Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.

Example 2:

Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.

Example 3:

Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.

Constraints:

2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= a_i, b_i <= n-1
a_i != b_i
Each pair of cities has at most one road connecting them.

Solution: Counting degrees and all pairs

Counting degrees for each node, if a and b are not connected, ans = degrees(a) + degrees(b), otherwise ans -= 1

Time complexity: O(E + V^2)
Space complexity: O(E)

C++

// Author: Huahua

class Solution {

public:

int maximalNetworkRank(int n, vector<vector<int>>& roads) {

vector<int> degrees(n);

unordered_set<int> connected;

for (const auto& road : roads) {

++degrees[road[0]];

++degrees[road[1]];

connected.insert((road[0] << 16) | road[1]);

connected.insert((road[1] << 16) | road[0]);

}

int ans = 0;

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

for (int j = i + 1; j < n; ++j)

ans = max(ans, degrees[i] + degrees[j]

- (connected.count((i << 16) | j) ? 1 : 0));

return ans;

}

};