Posts tagged as “easy”

花花酱 LeetCode 1189. Maximum Number of Balloons

By zxi on September 15, 2019

Given a string text, you want to use the characters of text to form as many instances of the word “balloon” as possible.

You can use each character in text at most once. Return the maximum number of instances that can be formed.

Example 1:

Input: text = "nlaebolko"
Output: 1

Example 2:

Input: text = "loonbalxballpoon"
Output: 2

Example 3:

Input: text = "leetcode"
Output: 0

Constraints:

1 <= text.length <= 10^4
text consists of lower case English letters only.

Solution: HashTable

Use a hashtable to count the occurrence of each letter and find the bottleneck one.

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

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfBalloons(string text) {

map<char, int> c;

for (char t : text) ++c[t];

return min({c['b'], c['a'], c['l'] / 2, c['o'] / 2, c['n']});

}

};

花花酱 LeetCode 1176. Diet Plan Performance

By zxi on August 31, 2019

A dieter consumes calories[i] calories on the i-th day. For every consecutive sequence of k days, they look at T, the total calories consumed during that sequence of k days:

If T < lower, they performed poorly on their diet and lose 1 point;
If T > upper, they performed well on their diet and gain 1 point;
Otherwise, they performed normally and there is no change in points.

Return the total number of points the dieter has after all calories.length days.

Note that: The total points could be negative.

Example 1:

Input: calories = [1,2,3,4,5], k = 1, lower = 3, upper = 3
Output: 0
Explaination: calories[0], calories[1] < lower and calories[3], calories[4] > upper, total points = 0.

Example 2:

Input: calories = [3,2], k = 2, lower = 0, upper = 1
Output: 1
Explaination: calories[0] + calories[1] > upper, total points = 1.

Example 3:

Input: calories = [6,5,0,0], k = 2, lower = 1, upper = 5
Output: 0
Explaination: calories[0] + calories[1] > upper, calories[2] + calories[3] < lower, total points = 0.

Constraints:

1 <= k <= calories.length <= 10^5
0 <= calories[i] <= 20000
0 <= lower <= upper

Solution: Sliding Window

Maintain the sum of a sliding window length of k.

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

C++

// Author: Huahua

class Solution {

public:

int dietPlanPerformance(vector<int>& calories, int k, int lower, int upper) {

int ans = 0;

int t = accumulate(begin(calories), begin(calories) + k - 1, 0);

for (int i = k - 1; i < calories.size(); ++i) {

if (i >= k) t -= calories[i - k];

t += calories[i];

if (t > upper) ++ans;

if (t < lower) --ans;

}

return ans;

}

};

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