Huahua's Tech Road

花花酱 LeetCode 1114. Print in Order

By zxi on July 23, 2019

Suppose we have a class:

public class Foo {

  public void first() { print("first"); }

  public void second() { print("second"); }

  public void third() { print("third"); }

}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Example 1:

Input: [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seems to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.

Solution 1: Mutex

C++

// Author: Huahua, 128 ms / 8.2 MB

class Foo {

public:

Foo() {

first_.lock();

second_.lock();

}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove this line.

printFirst();

first_.unlock();

}

void second(function<void()> printSecond) {

first_.lock();

// printSecond() outputs "second". Do not change or remove this line.

printSecond();

first_.unlock();

second_.unlock();

}

void third(function<void()> printThird) {

second_.lock();

// printThird() outputs "third". Do not change or remove this line.

printThird();

second_.unlock();

}

private:

std::mutex first_;

std::mutex second_;

};

Solution 2: Busy waiting

C++

// Author: Huahua, 176 ms / 9.2 MB

#include <unistd.h>

class Foo {

public:

Foo() {}

void first(function<void()> printFirst) {

// printFirst() outputs "first". Do not change or remove this line.

printFirst();

state_ = 1;

}

void second(function<void()> printSecond) {

while (state_ != 1) usleep(1);

// printSecond() outputs "second". Do not change or remove this line.

printSecond();

state_ = 2;

}

void third(function<void()> printThird) {

while (state_ != 2) usleep(1);

// printThird() outputs "third". Do not change or remove this line.

printThird();

state_ = 3;

}

private:

int state_ = 0;

};

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