Huahua's Tech Road

花花酱 LeetCode 1137. N-th Tribonacci Number

By zxi on July 27, 2019

The Tribonacci sequence T_n is defined as follows:

T₀ = 0, T₁ = 1, T₂ = 1, and T_n+3 = T_n + T_n+1 + T_n+2 for n >= 0.

Given n, return the value of T_n.

Example 1:

Input: n = 4
Output: 4
Explanation:
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

Example 2:

Input: n = 25
Output: 1389537

Constraints:

0 <= n <= 37
The answer is guaranteed to fit within a 32-bit integer, ie. answer <= 2^31 - 1.

Solution: DP

Time complexity: O(n)
Space complexity: O(n) -> O(1)

C++

// Author: Huahua

class Solution {

public:

int tribonacci(int n) {

if (n == 0) return n;

int t0 = 0;

int t1 = 1;

int t2 = 1;

int t = 1;

for (int i = 3; i <= n; ++i) {

t = t0 + t1 + t2;

t0 = t1;

t1 = t2;

t2 = t;

}

return t;

}

};

花花酱 LeetCode 1138. Alphabet Board Path

By zxi on July 27, 2019

On an alphabet board, we start at position (0, 0), corresponding to character board[0][0].

Here, board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"].

We may make the following moves:

'U' moves our position up one row, if the square exists;
'D' moves our position down one row, if the square exists;
'L' moves our position left one column, if the square exists;
'R' moves our position right one column, if the square exists;
'!' adds the character board[r][c] at our current position (r, c) to the answer.

Return a sequence of moves that makes our answer equal to target in the minimum number of moves. You may return any path that does so.

Example 1:

Input: target = "leet"
Output: "DDR!UURRR!!DDD!"

Example 2:

Input: target = "code"
Output: "RR!DDRR!UUL!R!"

Constraints:

1 <= target.length <= 100
target consists only of English lowercase letters.

Solution: Manhattan walk

Compute the coordinates of each char, walk from (x1, y1) to (x2, y2) in Manhattan way.
Be aware of the last row, we can only walk on ‘z’, so go left and up first if needed.

Time complexity: O(26*26 + n)
Space complexity: O(26*26)

C++

// Author: Huahua

class Solution {

public:

string alphabetBoardPath(string target) {

vector<vector<string>> paths(26, vector<string>(26));

for (int s = 0; s < 26; ++s)

for (int t = 0; t < 26; ++t) {

int dx = t % 5 - s % 5;

int dy = t / 5 - s / 5;

string path;

while (dx < 0) { path.push_back('L'); dx++; }

while (dy < 0) { path.push_back('U'); dy++; }

while (dx > 0) { path.push_back('R'); dx--; }

while (dy > 0) { path.push_back('D'); dy--; }

paths[s][t] = path;

}

char l = 'a';

string ans;

for (char c : target) {

ans += paths[l - 'a'][c - 'a'] + "!";

l = c;

}

return ans;

}

};

花花酱 LeetCode 1117. Building H2O

By zxi on July 25, 2019

There are two kinds of threads, oxygen and hydrogen. Your goal is to group these threads to form water molecules. There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given a releaseHydrogen and releaseOxygen method respectfully, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must be able to immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

In other words:

If an oxygen thread arrives at the barrier when no hydrogen threads are present, it has to wait for two hydrogen threads.
If a hydrogen thread arrives at the barrier when no other threads are present, it has to wait for an oxygen thread and another hydrogen thread.

We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. The key is just that threads pass the barrier in complete sets; thus, if we examine the sequence of threads that bond and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Example 1:

Input: "HOH"
Output: "HHO"
Explanation: "HOH" and "OHH" are also valid answers.

Example 2:

Input: "OOHHHH"
Output: "HHOHHO"
Explanation: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" and "OHHOHH" are also valid answers.

Constraints:

Total length of input string will be 3n, where 1 ≤ n ≤ 30.
Total number of H will be 2n in the input string.
Total number of O will be n in the input string.

Solution: Semaphore

C++

class Semaphore {

public:

Semaphore(int s) : s_(s) {}

void P(int d = 1) {

unique_lock<mutex> lock(m_);

while (s_ < d) {

cv_.wait(lock);

}

s_ -= d;

}

void V(int d = 1) {

unique_lock<mutex> lock(m_);

s_ += d;

cv_.notify_all();

}

private:

mutex m_;

condition_variable cv_;

int s_;

};

class H2O {

public:

H2O():s_h_(2), s_o_(2) { }

void hydrogen(function<void()> releaseHydrogen) {

s_h_.P();

releaseHydrogen();

s_o_.V();

}

void oxygen(function<void()> releaseOxygen) {

s_o_.P(2);

releaseOxygen();

s_h_.V(2);

}

private:

Semaphore s_h_;

Semaphore s_o_;

};

花花酱 LeetCode 1116. Print Zero Even Odd

By zxi on July 24, 2019

Suppose you are given the following code:

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // constructor
  public void zero(printNumber) { ... }  // only output 0's
  public void even(printNumber) { ... }  // only output even numbers
  public void odd(printNumber) { ... }   // only output odd numbers
}

The same instance of ZeroEvenOdd will be passed to three different threads:

Thread A will call zero() which should only output 0’s.
Thread B will call even() which should only ouput even numbers.
Thread C will call odd() which should only output odd numbers.

Each of the thread is given a printNumber method to output an integer. Modify the given program to output the series 010203040506… where the length of the series must be 2n.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously. One of them calls zero(), the other calls even(), and the last one calls odd(). "0102" is the correct output.

Example 2:

Input: n = 5
Output: "0102030405"

Solution: Mutex

C++

// Author: Huahua, 40 ms / 9 MB

class ZeroEvenOdd {

private:

int x;

int n;

mutex m_zero_;

mutex m_odd_;

mutex m_even_;

public:

ZeroEvenOdd(int n) {

this->n = n;

this->x = 1;

m_odd_.lock();

m_even_.lock();

}

// printNumber(x) outputs "x", where x is an integer.

void zero(function<void(int)> printNumber) {

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

m_zero_.lock();

printNumber(0);

if (i % 2 == 0) {

m_odd_.unlock();

} else {

m_even_.unlock();

}

void even(function<void(int)> printNumber) {

for (int i = 2; i <= n; i += 2) {

m_even_.lock();

printNumber(i);

m_zero_.unlock();

}

void odd(function<void(int)> printNumber) {

for (int i = 1; i <= n; i += 2) {

m_odd_.lock();

printNumber(i);

m_zero_.unlock();

}

};

花花酱 LeetCode 1115. Print FooBar Alternately

By zxi on July 23, 2019

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads. Thread A will call foo() while thread B will call bar(). Modify the given program to output “foobar” n times.

Example 1:

Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar(). "foobar" is being output 1 time.

Example 2:

Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

Solution: Mutex

C++

class FooBar {

private:

int n;

std::mutex m1_;

std::mutex m2_;

public:

FooBar(int n) {

this->n = n;

m2_.lock();

}

void foo(function<void()> printFoo) {

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

m1_.lock();

// printFoo() outputs "foo". Do not change or remove this line.

printFoo();

m2_.unlock();

}

void bar(function<void()> printBar) {

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

m2_.lock();

// printBar() outputs "bar". Do not change or remove this line.

printBar();

m1_.unlock();

}

};