Huahua’s Tech Road

花花酱 LeetCode 1626. Best Team With No Conflicts

By zxi on October 18, 2020

You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.

However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.

Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the i^th player, respectively, return the highest overall score of all possible basketball teams.

Example 1:

Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

Example 2:

Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

Example 3:

Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players.

Constraints:

1 <= scores.length, ages.length <= 1000
scores.length == ages.length
1 <= scores[i] <= 10⁶
1 <= ages[i] <= 1000

Solution: Sort + DP

Sort by (age, score) in descending order. For j < i, age[j] >= age[i]

dp[i] = max(dp[j] | score[j] >= score[i], j < i) + score[i]

Basically, we want to find the player j with best score among [0, i), and make sure score[i] <= score[j] (since age[j] >= age[i]) then we won’t have any conflicts.

ans = max(dp)

C++

// Author: Huahua

class Solution {

public:

int bestTeamScore(vector<int>& scores, vector<int>& ages) {

const int n = scores.size();

vector<pair<int, int>> players(n);

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

players[i] = {ages[i], scores[i]};

sort(rbegin(players), rend(players));

// dp[i] = max score of the first i players, i must be selected.

vector<int> dp(n);

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

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

if (players[i].second <= players[j].second)

dp[i] = max(dp[i], dp[j]);

dp[i] += players[i].second;

}

return *max_element(begin(dp), end(dp));

}

};

花花酱 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 1624. Largest Substring Between Two Equal Characters

By zxi on October 18, 2020

Given a string s, return the length of the longest substring between two equal characters, excluding the two characters. If there is no such substring return -1.

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

Example 1:

Input: s = "aa"
Output: 0
Explanation: The optimal substring here is an empty substring between the two 'a's.

Example 2:

Input: s = "abca"
Output: 2
Explanation: The optimal substring here is "bc".

Example 3:

Input: s = "cbzxy"
Output: -1
Explanation: There are no characters that appear twice in s.

Example 4:

Input: s = "cabbac"
Output: 4
Explanation: The optimal substring here is "abba". Other non-optimal substrings include "bb" and "".

Constraints:

1 <= s.length <= 300
s contains only lowercase English letters.

Solution: Hashtable

Remember the first position each letter occurs.

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

C++

class Solution {

public:

int maxLengthBetweenEqualCharacters(string s) {

vector<int> first(26, -1);

int ans = -1;

for (int i = 0; i < s.length(); ++i) {

int& p = first[s[i] - 'a'];

if (p != -1) {

ans = max(ans, i - p - 1);

} else {

p = i;

}

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;

}

};

Huahua's Tech Road

花花酱 LeetCode 1626. Best Team With No Conflicts

Solution: Sort + DP

C++

花花酱 LeetCode 1625. Lexicographically Smallest String After Applying Operations

Solution: Search

C++

花花酱 LeetCode 1624. Largest Substring Between Two Equal Characters

Solution: Hashtable

C++

花花酱 LeetCode 1621. Number of Sets of K Non-Overlapping Line Segments

Solution 1: Naive DP (TLE)

C++

Solution 2: DP w/ Prefix Sum

Python3

Solution 3: DP / 3D State

Python3

Solution 4: DP / Mathematical induction

Python3

Solution 5: DP / Reduction

C++

花花酱 LeetCode 1620. Coordinate With Maximum Network Quality

Solution: Brute Force

C++