Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1125. Smallest Sufficient Team

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

C++/HashTable

花花酱 LeetCode 1124. Longest Well-Performing Interval

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.

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++

花花酱 LeetCode 1109. Corporate Flight Bookings

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++

花花酱 LeetCode 1108. Defanging an IP Address

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

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++

花花酱 LeetCode 391. Perfect Rectangle

Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Example 1:

Example 2:

Example 3:

Example 4:

Solution: Counting corner points

C++