easy – Page 48 – Huahua’s Tech Road

花花酱 LeetCode 1175. Prime Arrangements

By zxi on August 31, 2019

Return the number of permutations of 1 to n so that prime numbers are at prime indices (1-indexed.)

(Recall that an integer is prime if and only if it is greater than 1, and cannot be written as a product of two positive integers both smaller than it.)

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: n = 5
Output: 12
Explanation: For example [1,2,5,4,3] is a valid permutation, but [5,2,3,4,1] is not because the prime number 5 is at index 1.

Example 2:

Input: n = 100
Output: 682289015

Constraints:

1 <= n <= 100

Solution: Permutation

Count the number of primes in range [1, n], assuming there are p primes and n – p non-primes, we can permute each group separately.
ans = p! * (n – p)!

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

C++

// Author: Huahua

class Solution {

public:

int numPrimeArrangements(int n) {

const int kMod = 1e9 + 7;

int p = 0;

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

p += isPrime(i);

long ans = 1;

for (int i = 1; i <= p; ++i)

ans = (ans * i) % kMod;

for (int i = 1; i <= n - p; ++i)

ans = (ans * i) % kMod;

return ans;

}

private:

bool isPrime(int x) {

if (x < 2) return false;

if (x == 2) return true;

for (int i = 2; i <= sqrt(x); ++i)

if (x % i == 0) return false;

return true;

}

};

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

By zxi on August 17, 2019

You are given an array of strings words and a string chars.

A string is good if it can be formed by characters from chars (each character can only be used once).

Return the sum of lengths of all good strings in words.

Example 1:

Input: words = ["cat","bt","hat","tree"], chars = "atach"
Output: 6
Explanation: 
The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Example 2:

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"
Output: 10
Explanation: 
The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Note:

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
All strings contain lowercase English letters only.

Solution: Hashtable

Use a hashtable to store each letter’s frequency of the string and compare that with each word.

Time complexity: O(n + sum(len(word))
Space complexity: O(1)

C++

// Author: Huahua, 72 ms, 20 MB

class Solution {

public:

int countCharacters(vector<string>& words, string chars) {

vector<int> counts(26);

for (char c : chars) ++counts[c - 'a'];

int ans = 0;

for (const string& word : words) {

vector<int> cur(26);

bool valid = true;

for (char c: word)

if (++cur[c - 'a'] > counts[c - 'a']) {

valid = false;

break;

}

if (valid) ans += word.length();

}

return ans;

}

};

Python#

# Author: Huahua

class Solution:

def countCharacters(self, words: List[str], chars: str) -> int:

counts = collections.Counter(chars)

def isValid(word):

cur = collections.Counter(word)

for c in cur:

if c not in counts or cur[c] > counts[c]:

return False

return True

ans = 0

for word in words:

ans += len(word) if isValid(word) else 0

return ans

花花酱 LeetCode 1154. Day of the Year

By zxi on August 11, 2019

Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.

Example 1:

Input: date = "2019-01-09"
Output: 9
Explanation: Given date is the 9th day of the year in 2019.

Example 2:

Input: date = "2019-02-10"
Output: 41

Example 3:

Input: date = "2003-03-01"
Output: 60

Example 4:

Input: date = "2004-03-01"
Output: 61

Constraints:

date.length == 10
date[4] == date[7] == '-', and all other date[i]‘s are digits
date represents a calendar date between Jan 1st, 1900 and Dec 31, 2019.

Solution:

Key: checking whether that year is a leap year or not.
is_leap = (year % 4 == 0 and year % 100 !=0) or year % 400 == 0

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

Python

# Author: Huahua

class Solution:

def dayOfYear(self, date: str) -> int:

y, m, d = int(date.split("-")[0]), int(date.split("-")[1]), int(date.split("-")[2])

leap = (y % 4 == 0 and y % 100 != 0) or y % 400 == 0

days = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]

s = sum(days[0:m-1]) + d

if leap and m > 2: s += 1

return s

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

}

};

Posts tagged as “easy”

花花酱 LeetCode 1175. Prime Arrangements

Solution: Permutation

C++

花花酱 LeetCode 1160. Find Words That Can Be Formed by Characters

Solution: Hashtable

C++

Python#

花花酱 LeetCode 1154. Day of the Year

Solution:

Python

花花酱 LeetCode 1137. N-th Tribonacci Number

Solution: DP

C++

花花酱 LeetCode 1115. Print FooBar Alternately

Solution: Mutex

C++