Posts tagged as “easy”

花花酱 LeetCode 1704. Determine if String Halves Are Alike

By zxi on December 27, 2020

You are given a string s of even length. Split this string into two halves of equal lengths, and let a be the first half and b be the second half.

Two strings are alike if they have the same number of vowels ('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'). Notice that s contains uppercase and lowercase letters.

Return true if a and b are alike. Otherwise, return false.

Example 1:

Input: s = "book"
Output: true
Explanation: a = "bo" and b = "ok". a has 1 vowel and b has 1 vowel. Therefore, they are alike.

Example 2:

Input: s = "textbook"
Output: false
Explanation: a = "text" and b = "book". a has 1 vowel whereas b has 2. Therefore, they are not alike.
Notice that the vowel o is counted twice.

Example 3:

Input: s = "MerryChristmas"
Output: false

Example 4:

Input: s = "AbCdEfGh"
Output: true

Constraints:

2 <= s.length <= 1000
s.length is even.
s consists of uppercase and lowercase letters.

Solution: Counting

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

Python3

# Author: Huahua

class Solution:

def halvesAreAlike(self, s: str) -> bool:

def count(s: str) -> int:

return sum(c in 'aeiouAEIOU' for c in s)

n = len(s)

return count(s[:n//2]) == count(s[n//2:])

花花酱 LeetCode 1700. Number of Students Unable to Eat Lunch

By zxi on December 26, 2020

The school cafeteria offers circular and square sandwiches at lunch break, referred to by numbers 0 and 1 respectively. All students stand in a queue. Each student either prefers square or circular sandwiches.

The number of sandwiches in the cafeteria is equal to the number of students. The sandwiches are placed in a stack. At each step:

If the student at the front of the queue prefers the sandwich on the top of the stack, they will take it and leave the queue.
Otherwise, they will leave it and go to the queue’s end.

This continues until none of the queue students want to take the top sandwich and are thus unable to eat.

You are given two integer arrays students and sandwiches where sandwiches[i] is the type of the i^th sandwich in the stack (i = 0 is the top of the stack) and students[j] is the preference of the j^th student in the initial queue (j = 0 is the front of the queue). Return the number of students that are unable to eat.

Example 1:

Input: students = [1,1,0,0], sandwiches = [0,1,0,1]
Output: 0 
Explanation:
- Front student leaves the top sandwich and returns to the end of the line making students = [1,0,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,0,1,1].
- Front student takes the top sandwich and leaves the line making students = [0,1,1] and sandwiches = [1,0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [1,1,0].
- Front student takes the top sandwich and leaves the line making students = [1,0] and sandwiches = [0,1].
- Front student leaves the top sandwich and returns to the end of the line making students = [0,1].
- Front student takes the top sandwich and leaves the line making students = [1] and sandwiches = [1].
- Front student takes the top sandwich and leaves the line making students = [] and sandwiches = [].
Hence all students are able to eat.

Example 2:

Input: students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
Output: 3

Constraints:

1 <= students.length, sandwiches.length <= 100
students.length == sandwiches.length
sandwiches[i] is 0 or 1.
students[i] is 0 or 1.

Solution 1: Simulation

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int countStudents(vector<int>& students, vector<int>& sandwiches) {

queue<int> q;

for (int s : students) q.push(s);

int c = 0;

int i = 0;

while (!q.empty()) {

int s = q.front(); q.pop();

if (s == sandwiches[i]) {

++i;

c = 0;

} else {

q.push(s);

}

if (++c > q.size()) break;

}

return q.size();

}

};

Solution 2: Counting

Count student’s preferences. Then process students from 1 to n, if there is no sandwich for current student then we can stop, since he/she will block all the students behind him/her.

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

C++

// Author: Huahua

class Solution {

public:

int countStudents(vector<int>& students, vector<int>& sandwiches) {

const int n = students.size();

vector<int> c(2);

for (int p : students) ++c[p];

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

if (--c[sandwiches[i]] < 0) return n - i;

return 0;

}

};

花花酱 LeetCode 1694. Reformat Phone Number

By zxi on December 20, 2020

You are given a phone number as a string number. number consists of digits, spaces ' ', and/or dashes '-'.

You would like to reformat the phone number in a certain manner. Firstly, remove all spaces and dashes. Then, group the digits from left to right into blocks of length 3 until there are 4 or fewer digits. The final digits are then grouped as follows:

2 digits: A single block of length 2.
3 digits: A single block of length 3.
4 digits: Two blocks of length 2 each.

The blocks are then joined by dashes. Notice that the reformatting process should never produce any blocks of length 1 and produce at most two blocks of length 2.

Return the phone number after formatting.

Example 1:

Input: number = "1-23-45 6"
Output: "123-456"
Explanation: The digits are "123456".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 3 digits remaining, so put them in a single block of length 3. The 2nd block is "456".
Joining the blocks gives "123-456".

Example 2:

Input: number = "123 4-567"
Output: "123-45-67"
Explanation: The digits are "1234567".
Step 1: There are more than 4 digits, so group the next 3 digits. The 1st block is "123".
Step 2: There are 4 digits left, so split them into two blocks of length 2. The blocks are "45" and "67".
Joining the blocks gives "123-45-67".

Example 3:

Input: number = "123 4-5678"
Output: "123-456-78"
Explanation: The digits are "12345678".
Step 1: The 1st block is "123".
Step 2: The 2nd block is "456".
Step 3: There are 2 digits left, so put them in a single block of length 2. The 3rd block is "78".
Joining the blocks gives "123-456-78".

Example 4:

Input: number = "12"
Output: "12"

Example 5:

Input: number = "--17-5 229 35-39475 "
Output: "175-229-353-94-75"

Constraints:

2 <= number.length <= 100
number consists of digits and the characters '-' and ' '.
There are at least two digits in number.

Solution:

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

C++

// Author: Huahua

class Solution {

public:

string reformatNumber(string number) {

string ans;

const int total = count_if(begin(number), end(number),

[](char c) { return isdigit(c); });

int l = 0;

for (char c : number) {

if (!isdigit(c)) continue;

ans += c;

++l;

if ((l % 3 == 0 && total - l >= 4) ||

(total % 3 != 0 && total - l == 2)

|| (total % 3 == 0 && total - l == 3))

ans += "-";

}

return ans;

}

};

花花酱 LeetCode 1688. Count of Matches in Tournament

By zxi on December 13, 2020

You are given an integer n, the number of teams in a tournament that has strange rules:

If the current number of teams is even, each team gets paired with another team. A total of n / 2 matches are played, and n / 2 teams advance to the next round.
If the current number of teams is odd, one team randomly advances in the tournament, and the rest gets paired. A total of (n - 1) / 2 matches are played, and (n - 1) / 2 + 1 teams advance to the next round.

Return the number of matches played in the tournament until a winner is decided.

Example 1:

Input: n = 7
Output: 6
Explanation: Details of the tournament: 
- 1st Round: Teams = 7, Matches = 3, and 4 teams advance.
- 2nd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 3rd Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 3 + 2 + 1 = 6.

Example 2:

Input: n = 14
Output: 13
Explanation: Details of the tournament:
- 1st Round: Teams = 14, Matches = 7, and 7 teams advance.
- 2nd Round: Teams = 7, Matches = 3, and 4 teams advance.
- 3rd Round: Teams = 4, Matches = 2, and 2 teams advance.
- 4th Round: Teams = 2, Matches = 1, and 1 team is declared the winner.
Total number of matches = 7 + 3 + 2 + 1 = 13.

Constraints:

1 <= n <= 200

Solution: Simulation / Recursion

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

C++

// Ver 1

class Solution {

public:

int numberOfMatches(int n) {

int ans = 0;

while (n > 1) {

ans += n / 2 + (n & 1);

n /= 2;

}

return ans;

}

};

// Ver 2

class Solution {

public:

int numberOfMatches(int n) {

return n > 1 ? n / 2 + (n & 1) + numberOfMatches(n / 2) : 0;

}

};

花花酱 LeetCode 1684. Count the Number of Consistent Strings

By zxi on December 12, 2020

You are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.

Example 2:

Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
Output: 7
Explanation: All strings are consistent.

Example 3:

Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
Output: 4
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.

Constraints:

1 <= words.length <= 10⁴
1 <= allowed.length <=26
1 <= words[i].length <= 10
The characters in allowed are distinct.
words[i] and allowed contain only lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int countConsistentStrings(string allowed, vector<string>& words) {

vector<int> m(26);

for (char c : allowed) m[c - 'a'] = 1;

int ans = 0;

for (const string& w : words)

ans += all_of(begin(w), end(w), [&m](char c) { return m[c - 'a']; });

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def countConsistentStrings(self, allowed: str, words: List[str]) -> int:

return sum(all(c in allowed for c in w) for w in words)