Posts tagged as “easy”

花花酱 LeetCode 1952. Three Divisors

By zxi on December 31, 2021

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

Constraints:

1 <= n <= 10⁴

Solution: Enumerate divisors.

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

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

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

if (n % i == 0) ++c;

return c == 3;

}

};

Optimization

Only need to enumerate divisors up to sqrt(n). Special handle for the d * d == n case.

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

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

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

if (n % i == 0)

c += 1 + (i * i != n);

return c == 3;

}

};

花花酱 LeetCode 1945. Sum of Digits of String After Convert

By zxi on December 31, 2021

You are given a string s consisting of lowercase English letters, and an integer k.

First, convert s into an integer by replacing each letter with its position in the alphabet (i.e., replace 'a' with 1, 'b' with 2, …, 'z' with 26). Then, transform the integer by replacing it with the sum of its digits. Repeat the transform operation k times in total.

For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:

Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
Transform #2: 17 ➝ 1 + 7 ➝ 8

Return the resulting integer after performing the operations described above.

Example 1:

Input: s = "iiii", k = 1
Output: 36
Explanation: The operations are as follows:
- Convert: "iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

Example 2:

Input: s = "leetcode", k = 2
Output: 6
Explanation: The operations are as follows:
- Convert: "leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

Example 3:

Input: s = "zbax", k = 2
Output: 8

Constraints:

1 <= s.length <= 100
1 <= k <= 10
s consists of lowercase English letters.

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int getLucky(string s, int k) {

int ans = 0;

for (char c : s) {

int n = c - 'a' + 1;

ans += n % 10;

ans += n / 10;

}

while (--k) {

int n = ans;

ans = 0;

while (n) {

ans += n % 10;

n /= 10;

}

return ans;

}

};

花花酱 LeetCode 1941. Check if All Characters Have Equal Number of Occurrences

By zxi on December 31, 2021

Given a string s, return true if s is a good string, or false otherwise.

A string s is good if all the characters that appear in s have the same number of occurrences (i.e., the same frequency).

Example 1:

Input: s = "abacbc"
Output: true
Explanation: The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

Example 2:

Input: s = "aaabb"
Output: false
Explanation: The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

Constraints:

1 <= s.length <= 1000
s consists of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

bool areOccurrencesEqual(string s) {

vector<int> m(26);

int maxCount = 0;

for (char c : s)

maxCount = max(maxCount, ++m[c - 'a']);

return all_of(begin(m), end(m), [maxCount](int c) -> bool {

return c == 0 || c == maxCount;

});

}

};

Python3

# Author: Huahua

class Solution:

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

return len(set(Counter(s).values())) == 1

花花酱 LeetCode 1935. Maximum Number of Words You Can Type

By zxi on December 31, 2021

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string text of words separated by a single space (no leading or trailing spaces) and a string brokenLetters of all distinct letter keys that are broken, return the number of words in text you can fully type using this keyboard.

Example 1:

Input: text = "hello world", brokenLetters = "ad"
Output: 1
Explanation: We cannot type "world" because the 'd' key is broken.

Example 2:

Input: text = "leet code", brokenLetters = "lt"
Output: 1
Explanation: We cannot type "leet" because the 'l' and 't' keys are broken.

Example 3:

Input: text = "leet code", brokenLetters = "e"
Output: 0
Explanation: We cannot type either word because the 'e' key is broken.

Constraints:

1 <= text.length <= 10⁴
0 <= brokenLetters.length <= 26
text consists of words separated by a single space without any leading or trailing spaces.
Each word only consists of lowercase English letters.
brokenLetters consists of distinct lowercase English letters.

Solution: Hashset / bitset

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

C++

// Author: Huahua

class Solution {

public:

int canBeTypedWords(string text, string brokenLetters) {

const int n = text.size();

bitset<26> b;

for (char c : brokenLetters) b.set(c - 'a');

int ans = 0;

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

if (i == n || text[i] == ' ') {

if (!broken) ++ans;

broken = 0;

} else {

broken |= b[text[i] - 'a'];

}

return ans;

}

};

花花酱 LeetCode 1929. Concatenation of Array

By zxi on December 30, 2021

Given an integer array nums of length n, you want to create an array ans of length 2n where ans[i] == nums[i] and ans[i + n] == nums[i] for 0 <= i < n (0-indexed).

Specifically, ans is the concatenation of two nums arrays.

Return the array ans.

Example 1:

Input: nums = [1,2,1]
Output: [1,2,1,1,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[0],nums[1],nums[2]]
- ans = [1,2,1,1,2,1]

Example 2:

Input: nums = [1,3,2,1]
Output: [1,3,2,1,1,3,2,1]
Explanation: The array ans is formed as follows:
- ans = [nums[0],nums[1],nums[2],nums[3],nums[0],nums[1],nums[2],nums[3]]
- ans = [1,3,2,1,1,3,2,1]

Constraints:

n == nums.length
1 <= n <= 1000
1 <= nums[i] <= 1000

Solution: Pre-allocation

Pre-allocate an array of length 2 * n.
ans[i] = nums[i % n]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getConcatenation(vector<int>& nums) {

const int n = nums.size();

vector<int> ans(2 * n);

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

ans[i] = nums[i % n];

return ans;

}

};