Huahua’s Tech Road

花花酱 LeetCode 630. Course Schedule III

By zxi on May 10, 2019

There are n different online courses numbered from 1 to n. Each course has some duration(course length) t and closed on d_th day. A course should be taken continuouslyfor t days and must be finished before or on the d_th day. You will start at the 1_st 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:

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

Solution: Priority queue

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

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

C++

// Author: Huahua, running time: 196 ms, 40.5 MB

class Solution {

public:

int scheduleCourse(vector<vector<int>>& courses) {

sort(begin(courses), end(courses), [](const auto& a, const auto& b) {

return a[1] < b[1];

});

priority_queue<int> q;

int d = 0;

for (const auto& c: courses) {

if (d + c[0] <= c[1]) {

d += c[0];

q.push(c[0]);

} else if (q.size() && q.top() > c[0]) {

d += c[0] - q.top(); q.pop();

q.push(c[0]);

}

return q.size();

}

};

花花酱 LeetCode 640. Solve the Equation

By zxi on May 10, 2019

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

// Author: Huahua, 0 ms, 8.5 MB

class Solution {

public:

string solveEquation(const string& equation) {

auto parse = [](string_view s) -> vector<int> {

int a{0}, b{0};

int sign = 1;

long t = 0;

bool d = false;

for (char c : s) {

if (isdigit(c)) {

d = true;

t = t * 10 + c - '0';

} else {

if (c == 'x')

a += (d ? t : 1) * sign;

else {

b += t * sign;

sign = c == '+' ? 1 : -1;

}

d = false;

t = 0;

}

b += t * sign;

return {a, b};

};

auto pos = equation.find('=');

auto l = parse(string_view(equation).substr(0, pos));

auto r = parse(string_view(equation).substr(pos + 1));

l[0] -= r[0];

l[1] -= r[1];

if (l[0] == 0)

return l[1] == 0 ? "Infinite solutions" : "No solution";

return "x=" + to_string(-l[1] / l[0]);

}

};

花花酱 LeetCode 838. Push Dominoes

By zxi on May 6, 2019

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:

0 <= N <= 10^5
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++

// Author: Huahua, running time: 24 ms, 15.2 MB

class Solution {

public:

string pushDominoes(string D) {

const int n = static_cast<int>(D.size());

vector<int> L(n, INT_MAX), R(n, INT_MAX);

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

if (D[i] == 'L') {

L[i] = 0;

for (int j = i - 1; j >= 0 && D[j] == '.'; --j)

L[j] = L[j + 1] + 1;

} else if (D[i] == 'R') {

R[i] = 0;

for (int j = i + 1; j < n && D[j] == '.'; ++j)

R[j] = R[j - 1] + 1;

}

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

if (L[i] < R[i]) D[i] = 'L';

else if (L[i] > R[i]) D[i] = 'R';

return D;

}

};

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

By zxi on May 4, 2019

LeetCode 1037. Valid Boomerang

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

C++

class Solution {

public:

bool isBoomerang(vector<vector<int>>& points) {

if (points[0] == points[1] ||

points[1] == points[2] ||

points[0] == points[2]) return false;

int dx0 = points[0][0] - points[1][0];

int dy0 = points[0][1] - points[1][1];

int dx1 = points[0][0] - points[2][0];

int dy1 = points[0][1] - points[2][1];

return dy0 * dx1 != dy1 * dx0;

}

};

LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

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

C++

class Solution {

public:

TreeNode* bstToGst(TreeNode* root) {

int s = 0;

function<void(TreeNode*)> dfs = [&](TreeNode* n) {

if (!n) return;

dfs(n->right);

n->val = s += n->val;

dfs(n->left);

};

dfs(root);

return root;

}

};

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

class Solution {

public:

int minScoreTriangulation(vector<int>& A) {

const int n = A.size();

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

for (int l = 3; 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 + 1; k <= j - 1; ++k)

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

}

return dp[0][n - 1];

}

};

C++/top-down

class Solution {

public:

int minScoreTriangulation(vector<int>& A) {

const int n = A.size();

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

function<int(int, int)> solve = [&](int i, int j) {

if (j - i <= 1) return 0;

if (dp[i][j] != INT_MAX) return dp[i][j];

dp[i][j] = INT_MAX;

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

dp[i][j] = min(dp[i][j],

solve(i, k) + solve(k, j) + A[i] * A[k] * A[j]);

return dp[i][j];

};

return solve(0, n - 1);

}

};

Python

"Author: Huahua"

from functools import lru_cache

class Solution:

def minScoreTriangulation(self, A: List[int]) -> int:

@lru_cache(None)

def dp(i, j):

return 0 if j - i <= 1 else min(dp(i, k) + dp(k, j) + A[i] * A[k] * A[j] for k in range(i + 1, j))

return dp(0, len(A) - 1)

1040. Moving Stones Until Consecutive II

Solution: Sliding Window

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

C++

class Solution {

public:

vector<int> numMovesStonesII(vector<int>& stones) {

const int n = static_cast<int>(stones.size());

sort(begin(stones), end(stones));

int max_steps = max(stones[n - 1] - stones[1] - n + 2,

stones[n - 2] - stones[0] - n + 2);

int min_steps = INT_MAX;

int i = 0;

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

while (stones[j] - stones[i] >= n) ++i;

if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2)

min_steps = min(min_steps, 2);

else

min_steps = min(min_steps, n - (j - i + 1));

}

return {min_steps, max_steps};

}

};

花花酱 LeetCode 851. Loud and Rich

By zxi on May 4, 2019

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x“.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y. Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return answer, where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]), among all people who definitely have equal to or more money than person x.

Example 1:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.

Note:

1 <= quiet.length = N <= 500
0 <= quiet[i] < N, all quiet[i] are different.
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]‘s are all different.
The observations in richer are all logically consistent.

Solution: DFS + Memoization

For person i , remember the quietest person who is richer than person i.

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

C++

// Author: Huahua, running time: 108 ms, 31.6 MB

class Solution {

public:

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {

const int n = quiet.size();

vector<vector<int>> g(n);

for (const auto& r : richer)

g[r[1]].push_back(r[0]);

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

function<void(int)> dfs = [&](int i) {

if (ans[i] != -1) return;

ans[i] = i;

for (int j : g[i]) {

dfs(j);

if (quiet[ans[j]] < quiet[ans[i]])

ans[i] = ans[j];

}

};

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

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 630. Course Schedule III

Solution: Priority queue

C++

花花酱 LeetCode 640. Solve the Equation

Solution: Parse the equation

C++

花花酱 LeetCode 838. Push Dominoes

C++

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

LeetCode 1037. Valid Boomerang

C++

LeetCode 1038. Binary Search Tree to Greater Sum Tree

C++

1039. Minimum Score Triangulation of Polygon

C++/bottom-up

C++/top-down

Python

1040. Moving Stones Until Consecutive II

C++

花花酱 LeetCode 851. Loud and Rich

C++