Huahua’s Tech Road

花花酱 LeetCode 217. Contains Duplicate

By zxi on July 22, 2019

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

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

Example 2:

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

Example 3:

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

Solution 1: HashTable

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

C++

// Author: Huahua, 48ms/16.5MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

unordered_set<int> s;

for (int num : nums)

if (!s.insert(num).second) return true;

return false;

}

};

Solution 2: Sorting

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

C++

// Author: Huahua, 28ms/11.4MB

class Solution {

public:

bool containsDuplicate(vector<int>& nums) {

sort(begin(nums), end(nums));

for (int i = 1; i < nums.size(); ++i)

if (nums[i] == nums[i - 1]) return true;

return false;

}

};

花花酱 LeetCode 226. Invert Binary Tree

By zxi on July 22, 2019

Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

Solution: Recursion

Recursive invert the left and right subtrees and swap them.

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

C++

// Author: Huahua

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

if (!root) return nullptr;

TreeNode* tmp = root->right;

root->right = invertTree(root->left);

root->left = invertTree(tmp);

return root;

}

};

Python3

# Author: Huahua

class Solution:

def invertTree(self, root: TreeNode) -> TreeNode:

if not root: return None

root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)

return root

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

}

};

Huahua's Tech Road

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 226. Invert Binary Tree

Solution: Recursion

C++

Python3

花花酱 LeetCode 232. Implement Queue using Stacks

Solution: Use two stacks

C++

花花酱 LeetCode 150. Evaluate Reverse Polish Notation

Solution: Stack

C++

Python3

Python3

花花酱 LeetCode 1129. Shortest Path with Alternating Colors

C++