Posts tagged as “medium”

花花酱 LeetCode 150. Evaluate Reverse Polish Notation

By zxi on July 22, 2019

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Solution: Stack

Use a stack to store the operands, pop two whenever there is an operator, compute the result and push back to the stack.

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

C++

class Solution {

public:

int evalRPN(vector<string>& tokens) {

stack<int> s;

for (const string& token : tokens) {

if (isdigit(token.back())) {

s.push(stoi(token));

} else {

int n2 = s.top(); s.pop();

int n1 = s.top(); s.pop();

int n = 0;

switch (token[0]) {

case '+': n = n1 + n2; break;

case '-': n = n1 - n2; break;

case '*': n = n1 * n2; break;

case '/': n = n1 / n2; break;

}

s.push(n);

}

return s.top();

}

};

Python3

# Author: Huahua

class Solution:

def evalRPN(self, tokens: List[str]) -> int:

s = []

for token in tokens:

if token[-1] not in '+-*/':

s.append(int(token))

else:

n2 = s.pop()

n1 = s.pop()

if token == '+': n = n1 + n2

elif token == '-': n = n1 - n2

elif token == '*': n = n1 * n2

elif token == '/': n = int(n1 / n2)

s.append(n)

return s[-1]

Just for fun, f-string with eval

Python3

# Author: Huahua

class Solution:

def evalRPN(self, tokens: List[str]) -> int:

s = []

for token in tokens:

if token[-1] not in '+-*/':

s.append(int(token))

else:

n2 = s.pop()

n1 = s.pop()

s.append(int(eval(f'{n1}{token}{n2}')))

return s[-1]

花花酱 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 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 1094. Car Pooling

By zxi on June 22, 2019

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Solution1: Min heap

Sort events by location

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

C++

// Author: Huahua

class Solution {

public:

bool carPooling(vector<vector<int>>& trips, int capacity) {

priority_queue<int> q;

for (const auto& trip : trips) {

int pick_up = -((trip[1] << 10) | (1 << 9) | trip[0]);

int drop_off = -((trip[2] << 10) | trip[0]);

q.push(pick_up);

q.push(drop_off);

}

while (q.size()) {

int key = -q.top(); q.pop();

int sign = ((key >> 9) & 1) ? 1: -1;

int num = key & 0xFF;

if ((capacity -= sign * num) < 0)

return false;

}

return true;

}

};

Solution 2: Preprocessing

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

C++

// Author: Huahua

class Solution {

public:

bool carPooling(vector<vector<int>>& trips, int capacity) {

vector<int> d(1001);

for (const auto& trip : trips) {

d[trip[1]] -= trip[0];

d[trip[2]] += trip[0];

}

for (const int c : d)

if ((capacity += c) < 0) return false;

return true;

}

};

花花酱 1054. Distant Barcodes

By zxi on May 28, 2019

In a warehouse, there is a row of barcodes, where the i-th barcode is barcodes[i].

Rearrange the barcodes so that no two adjacent barcodes are equal. You may return any answer, and it is guaranteed an answer exists.

Example 1:

Input: [1,1,1,2,2,2]
Output: [2,1,2,1,2,1]

Example 2:

Input: [1,1,1,1,2,2,3,3]
Output: [1,3,1,3,2,1,2,1]

Note:

1 <= barcodes.length <= 10000
1 <= barcodes[i] <= 10000

Soluton: Sorting

Sort the element by their frequency in descending order. Fill the most frequent element first in even positions, if reach the end of the array, start from position 1 then 3, 5, …

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

C++

// Author: Huahua, 216 ms, 18.2 MB

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

const int n = barcodes.size();

vector<int> f(10001);

for (int v : barcodes) ++f[v];

sort(begin(barcodes), end(barcodes), [&](const int a, const int b){

return f[a] == f[b] ? a > b : f[a] > f[b];

});

vector<int> ans(n);

int pos = 0;

for (int v : barcodes) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};

Solution 2: Find the most frequent

Actually, we only need to find the most frequent element and put in the even positions, then put the rest of the groups of elements in any order.

e.g. [1, 1, 2, 2, 2, 2, 2, 3, 4]
Can be
5*2 [2 – 2 – 2 – 2 – 2]
4*1 [2 4 2 – 2 – 2 – 2]
3*1 [2 4 2 3 2 – 2 – 2]
1*2 [ 2 3 2 3 2 1 2 1 2]

if we start with any other groups rather than 2, if will become:
[3 2 2 – 2 – 2 – 2 ] which is wrong…

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

C++

// Author: Huahua, 172 ms (99.89%), 18 MB (< 100%)

class Solution {

public:

vector<int> rearrangeBarcodes(vector<int>& barcodes) {

constexpr int kMaxV = 10001;

const int n = barcodes.size();

vector<int> f(kMaxV);

int max_f = 0;

int max_v = 0;

for (int v : barcodes)

if (++f[v] > max_f) {

max_f = f[v];

max_v = v;

}

vector<int> ans(n);

int pos = 0;

while (f[max_v]-- > 0) {

ans[pos] = max_v;

if ((pos += 2)>= n) pos = 1;

}

for (int v = 1; v < kMaxV; ++v) {

while (f[v]-- > 0) {

ans[pos] = v;

if ((pos += 2) >= n) pos = 1;

}

return ans;

}

};