Huahua's Tech Road

花花酱 LeetCode 1129. Shortest Path with Alternating Colors

By zxi on July 20, 2019

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Solution: BFS

Time complexity: O(|V| + |E|)
Space complexity: O(|V| + |E|)

C++

class Solution {

public:

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {

vector<unordered_set<int>> edges_r(n);

vector<unordered_set<int>> edges_b(n);

for (const auto& e : red_edges)

edges_r[e[0]].insert(e[1]);

for (const auto& e : blue_edges)

edges_b[e[0]].insert(e[1]);

unordered_set<int> seen_r;

unordered_set<int> seen_b;

vector<int> ans(n, -1);

queue<pair<int, int>> q; // (node, color)

q.push({0, 0}); // red

q.push({0, 1}); // blue

seen_r.insert(0);

seen_b.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int p = q.front().first;

int is_red = q.front().second;

q.pop();

ans[p] = ans[p] >= 0 ? min(ans[p], steps) : steps;

const auto& edges = is_red ? edges_r : edges_b;

auto& seen = is_red ? seen_r : seen_b;

for (int nxt : edges[p]) {

if (seen.count(nxt)) continue;

seen.insert(nxt);

q.push({nxt, 1 - is_red});

}

++steps;

}

return ans;

}

};

花花酱 1130. Minimum Cost Tree From Leaf Values

By zxi on July 20, 2019

Given an array arr of positive integers, consider all binary trees such that:

Each node has either 0 or 2 children;
The values of arr correspond to the values of each leaf in an in-order traversal of the tree. (Recall that a node is a leaf if and only if it has 0 children.)
The value of each non-leaf node is equal to the product of the largest leaf value in its left and right subtree respectively.

Among all possible binary trees considered, return the smallest possible sum of the values of each non-leaf node. It is guaranteed this sum fits into a 32-bit integer.

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation:
There are two possible trees.  The first has non-leaf node sum 36, and the second has non-leaf node sum 32.

    24            24
   /  \          /  \
  12   4        6    8
 /  \               / \
6    2             2   4

Constraints:

2 <= arr.length <= 40
1 <= arr[i] <= 15
It is guaranteed that the answer fits into a 32-bit signed integer (ie. it is less than 2^31).

Solution: DP

dp[i][j] := answer of build a tree from a[i] ~ a[j]
dp[i][j] = min{dp[i][k] + dp[k+1][j] + max(a[i~k]) * max(a[k+1~j])} i <= k < j

Time complexity: O(n^3)
Space complexity: O(n^2)

C++

class Solution {

public:

int mctFromLeafValues(vector<int>& arr) {

const int n = arr.size();

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

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

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

m[i][i] = arr[i];

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

m[i][j] = max(m[i][j - 1], arr[j]);

}

for (int l = 2; l <= n; ++l)

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

int j = i + l - 1;

dp[i][j] = INT_MAX;

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

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + m[i][k] * m[k+1][j]);

}

return dp[0][n - 1];

}

};

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

By zxi on July 20, 2019

Given a list of dominoes, dominoes[i] = [a, b] is equivalent to dominoes[j] = [c, d] if and only if either (a==c and b==d), or (a==d and b==c) – that is, one domino can be rotated to be equal to another domino.

Return the number of pairs (i, j) for which 0 <= i < j < dominoes.length, and dominoes[i] is equivalent to dominoes[j].

Example 1:

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

Constraints:

1 <= dominoes.length <= 40000
1 <= dominoes[i][j] <= 9

Solution: HashTable

Count how many times each key occurred so far.

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

C++

class Solution {

public:

int numEquivDominoPairs(vector<vector<int>>& dominoes) {

vector<int> m(100);

int ans = 0;

for (const auto& d : dominoes) {

int k1 = d[0] * 10 + d[1];

int k2 = d[1] * 10 + d[0];

ans += m[k1];

if (k1 != k2) ans += m[k2];

++m[k1];

}

return ans;

}

};

花花酱 LeetCode 1125. Smallest Sufficient Team

By zxi on July 15, 2019

In a project, you have a list of required skills req_skills, and a list of people. The i-th person people[i] contains a list of skills that person has.

Consider a sufficient team: a set of people such that for every required skill in req_skills, there is at least one person in the team who has that skill. We can represent these teams by the index of each person: for example, team = [0, 1, 3] represents the people with skills people[0], people[1], and people[3].

Return any sufficient team of the smallest possible size, represented by the index of each person.

You may return the answer in any order. It is guaranteed an answer exists.

Example 1:

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

Example 2:

Input: req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
Output: [1,2]

Constraints:

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
Elements of req_skills and people[i] are (respectively) distinct.
req_skills[i][j], people[i][j][k] are lowercase English letters.
It is guaranteed a sufficient team exists.

Solution: DP

C++/Array

// Author: Huahua, 24 ms / 11 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

const int target = (1 << n) - 1;

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

vector<int> dp((1 << n), INT_MAX / 2);

vector<pair<int, int>> pt((1 << n));

dp[0] = 0;

for (int i = 0; i < people.size(); ++i) {

const int k = skills[i];

if (k == 0) continue;

for (int j = target; j >= 0; --j)

if (dp[j] + 1 < dp[j | k]) {

dp[j | k] = dp[j] + 1;

pt[j | k] = {j, i};

}

int t = target;

vector<int> ans;

while (t) {

ans.push_back(pt[t].second);

t = pt[t].first;

}

return ans;

}

};

C++/HashTable

// Author: Huahua, 272 ms / 94.8 MB

class Solution {

public:

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {

const int n = req_skills.size();

vector<int> skills;

for (const auto& p : people) {

int mask = 0;

for (const string& s: p)

mask |= (1 << find(begin(req_skills), end(req_skills), s) - begin(req_skills));

skills.push_back(mask);

}

unordered_map<int, vector<int>> dp;

dp[0] = {};

for (int i = 0; i < people.size(); ++i) {

unordered_map<int, vector<int>> tmp(dp);

for (const auto& kv : dp) {

int k = kv.first | skills[i];

if (!tmp.count(k) || kv.second.size() + 1 < tmp[k].size()) {

tmp[k] = kv.second;

tmp[k].push_back(i);

}

tmp.swap(dp);

}

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

}

};

花花酱 LeetCode 1124. Longest Well-Performing Interval

By zxi on July 14, 2019

We are given hours, a list of the number of hours worked per day for a given employee.

A day is considered to be a tiring day if and only if the number of hours worked is (strictly) greater than 8.

A well-performing interval is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days.

Return the length of the longest well-performing interval.

Example 1:

Input: hours = [9,9,6,0,6,6,9]
Output: 3
Explanation: The longest well-performing interval is [9,9,6].

Constraints:

1 <= hours.length <= 10000
0 <= hours[i] <= 16

Solution: Target sum == 1

This problem can be reduced to find the longest subarray with sum of 1, or the longest subarray starting from left-most that has a sum greater than 0.

e.g. [6, 6, (6, 9, 9), 6, 6] => sum = 1
e.g. [9, 9, 9] => sum = 3

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

C++

// Author: Huahua

class Solution {

public:

int longestWPI(vector<int>& hours) {

const int n = hours.size();

for (int& v : hours) v = v > 8 ? 1 : -1;

int s = 0;

unordered_map<int, int> idx;

int ans = 0;

for (int i = 0; i < hours.size(); ++i) {

s += hours[i];

if (s > 0)

ans = i + 1;

if (!idx.count(s))

idx[s] = i;

if (idx.count(s - 1))

ans = max(ans, i - idx[s - 1]);

}

return ans;

}

};