Posts published in July 2019

花花酱 LeetCode 232. Implement Queue using Stacks

By zxi on July 22, 2019

Implement the following operations of a queue using stacks.

push(x) — Push element x to the back of queue.
pop() — Removes the element from in front of queue.
peek() — Get the front element.
empty() — Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // returns 1
queue.pop();   // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack — which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Solution: Use two stacks

amortized cost: O(1)

C++

class MyQueue {

public:

/** Initialize your data structure here. */

MyQueue() {}

/** Push element x to the back of queue. */

void push(int x) {

s1_.push(x);

}

/** Removes the element from in front of queue and returns that element. */

int pop() {

if (s2_.empty()) move();

int top = s2_.top();

s2_.pop();

return top;

}

/** Get the front element. */

int peek() {

if (s2_.empty()) move();

return s2_.top();

}

/** Returns whether the queue is empty. */

bool empty() {

return s1_.empty() && s2_.empty();

}

private:

stack<int> s1_;

stack<int> s2_;

void move() {

while (!s1_.empty()) {

s2_.push(s1_.top());

s1_.pop();

}

};

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

花花酱 LeetCode 1129. Shortest Path with Alternating Colors

By zxi on July 20, 2019

Consider a directed graph, with nodes labelled 0, 1, ..., n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.

Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.

Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).

Example 1:

Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
Output: [0,1,-1]

Example 2:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
Output: [0,1,-1]

Example 3:

Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]]
Output: [0,-1,-1]

Example 4:

Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]]
Output: [0,1,2]

Example 5:

Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]]
Output: [0,1,1]

Constraints:

1 <= n <= 100
red_edges.length <= 400
blue_edges.length <= 400
red_edges[i].length == blue_edges[i].length == 2
0 <= red_edges[i][j], blue_edges[i][j] < n

Solution: BFS

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

C++

class Solution {

public:

vector<int> shortestAlternatingPaths(int n, vector<vector<int>>& red_edges, vector<vector<int>>& blue_edges) {

vector<unordered_set<int>> edges_r(n);

vector<unordered_set<int>> edges_b(n);

for (const auto& e : red_edges)

edges_r[e[0]].insert(e[1]);

for (const auto& e : blue_edges)

edges_b[e[0]].insert(e[1]);

unordered_set<int> seen_r;

unordered_set<int> seen_b;

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

queue<pair<int, int>> q; // (node, color)

q.push({0, 0}); // red

q.push({0, 1}); // blue

seen_r.insert(0);

seen_b.insert(0);

int steps = 0;

while (!q.empty()) {

int size = q.size();

while (size--) {

int p = q.front().first;

int is_red = q.front().second;

q.pop();

ans[p] = ans[p] >= 0 ? min(ans[p], steps) : steps;

const auto& edges = is_red ? edges_r : edges_b;

auto& seen = is_red ? seen_r : seen_b;

for (int nxt : edges[p]) {

if (seen.count(nxt)) continue;

seen.insert(nxt);

q.push({nxt, 1 - is_red});

}

++steps;

}

return ans;

}

};

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

}

};