Huahua’s Tech Road

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

}

};

花花酱 LeetCode 1109. Corporate Flight Bookings

By zxi on July 11, 2019

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked kseats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Solution: Marking start and end

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

C++

// Author: Huahua

class Solution {

public:

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

vector<int> ans(n + 1);

for (const auto& b : bookings) {

ans[b[0] - 1] += b[2];

ans[b[1]] -= b[2];

}

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

ans[i] += ans[i - 1];

ans.pop_back();

return ans;

}

};

花花酱 LeetCode 1108. Defanging an IP Address

By zxi on July 11, 2019

Given a valid (IPv4) IP address, return a defanged version of that IP address.

A defanged IP address replaces every period "." with "[.]".

Example 1:

Input: address = "1.1.1.1"
Output: "1[.]1[.]1[.]1"

Example 2:

Input: address = "255.100.50.0"
Output: "255[.]100[.]50[.]0"

Constraints:

The given address is a valid IPv4 address.

Solution: String

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

C++

class Solution {

public:

string defangIPaddr(string address) {

string output;

for (const char c : address) {

if (c == '.') output += "[.]";

else output += c;

}

return output;

}

};

Huahua's Tech Road

花花酱 LeetCode 1128. Number of Equivalent Domino Pairs

Solution: HashTable

C++

花花酱 LeetCode 1125. Smallest Sufficient Team

C++/Array

C++/HashTable

花花酱 LeetCode 1124. Longest Well-Performing Interval

Solution: Target sum == 1

C++

花花酱 LeetCode 1109. Corporate Flight Bookings

Solution: Marking start and end

C++

花花酱 LeetCode 1108. Defanging an IP Address

Solution: String

C++