easy Archives - Page 48 of 75 - 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 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();

}

};

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

Posts tagged as “easy”

花花酱 LeetCode 1137. N-th Tribonacci Number

Solution: DP

C++

花花酱 LeetCode 1115. Print FooBar Alternately

Solution: Mutex

C++

花花酱 LeetCode 1114. Print in Order

Solution 1: Mutex

C++

Solution 2: Busy waiting

C++

花花酱 LeetCode 217. Contains Duplicate

Solution 1: HashTable

C++

Solution 2: Sorting

C++

花花酱 LeetCode 226. Invert Binary Tree

Solution: Recursion

C++

Python3