Press "Enter" to skip to content

Huahua's Tech Road

花花酱 LeetCode 1042. Flower Planting With No Adjacent

You have N gardens, labelled 1 to N.  In each garden, you want to plant one of 4 types of flowers.

paths[i] = [x, y] describes the existence of a bidirectional path from garden x to garden y.

Also, there is no garden that has more than 3 paths coming into or leaving it.

Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)-th garden.  The flower types are denoted 1, 2, 3, or 4.  It is guaranteed an answer exists.

Example 1:

Input: N = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]

Example 2:

Input: N = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Note:

  • 1 <= N <= 10000
  • 0 <= paths.size <= 20000
  • No garden has 4 or more paths coming into or leaving it.
  • It is guaranteed an answer exists.

Solution: Graph coloring, choose any available color

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

C++

花花酱 LeetCode 630. Course Schedule III

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on dth day. A course should be taken continuouslyfor t days and must be finished before or on the dth day. You will start at the 1st day.

Given n online courses represented by pairs (t,d), your task is to find the maximal number of courses that can be taken.

Example:

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3
Explanation: 
There're totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Note:

  1. The integer 1 <= d, t, n <= 10,000.
  2. You can’t take two courses simultaneously.

Solution: Priority queue

  1. Sort courses by end date
  2. Use a priority queue (Max-Heap) to store the course lengths or far
  3. Swap with a longer course if we could not take the current one

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

C++

花花酱 LeetCode 640. Solve the Equation

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

Solution: Parse the equation

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

C++

花花酱 LeetCode 838. Push Dominoes

here are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state. 

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

  1. 0 <= N <= 10^5
  2. String dominoes contains only 'L‘, 'R' and '.'

Solution: Simulation

Simulate the push process, record the steps from L and R for each domino.
steps(L) == steps(R) => “.”
steps(L) < steps(R) => “L”
steps(L) > steps(R) => “R”

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

C++

花花酱 LeetCode Weekly Contest 135 (1037, 1038, 1039, 1040)

LeetCode 1037. Valid Boomerang

Solution: Math
Time complexity: O(1)
Space complexity: O(1)

C++

LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

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

C++

1039. Minimum Score Triangulation of Polygon

Solution: DP

Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j
answer: dp[0][n – 1]

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

C++/bottom-up

C++/top-down

Python

1040. Moving Stones Until Consecutive II

Solution: Sliding Window

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

C++