Posts tagged as “easy”

花花酱 LeetCode 2053. Kth Distinct String in an Array

By zxi on November 1, 2021

A distinct string is a string that is present only once in an array.

Given an array of strings arr, and an integer k, return the k^th distinct string present in arr. If there are fewer than k distinct strings, return an empty string "".

Note that the strings are considered in the order in which they appear in the array.

Example 1:

Input: arr = ["d","b","c","b","c","a"], k = 2
Output: "a"
Explanation:
The only distinct strings in arr are "d" and "a".
"d" appears 1^st, so it is the 1^st distinct string.
"a" appears 2^nd, so it is the 2^nd distinct string.
Since k == 2, "a" is returned.

Example 2:

Input: arr = ["aaa","aa","a"], k = 1
Output: "aaa"
Explanation:
All strings in arr are distinct, so the 1^st string "aaa" is returned.

Example 3:

Input: arr = ["a","b","a"], k = 3
Output: ""
Explanation:
The only distinct string is "b". Since there are fewer than 3 distinct strings, we return an empty string "".

Constraints:

1 <= k <= arr.length <= 1000
1 <= arr[i].length <= 5
arr[i] consists of lowercase English letters.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

string kthDistinct(vector<string>& arr, int k) {

unordered_map<string, int> m;

for (const string& s : arr)

++m[s];

for (const string& s : arr)

if (m[s] == 1 && --k == 0) return s;

return "";

}

};

花花酱 LeetCode 2047. Number of Valid Words in a Sentence

By zxi on October 24, 2021

A sentence consists of lowercase letters ('a' to 'z'), digits ('0' to '9'), hyphens ('-'), punctuation marks ('!', '.', and ','), and spaces (' ') only. Each sentence can be broken down into one or more tokens separated by one or more spaces ' '.

A token is a valid word if:

It only contains lowercase letters, hyphens, and/or punctuation (no digits).
There is at most one hyphen '-'. If present, it should be surrounded by lowercase characters ("a-b" is valid, but "-ab" and "ab-" are not valid).
There is at most one punctuation mark. If present, it should be at the end of the token.

Examples of valid words include "a-b.", "afad", "ba-c", "a!", and "!".

Given a string sentence, return the number of valid words in sentence.

Example 1:

Input: sentence = "cat and  dog"
Output: 3
Explanation: The valid words in the sentence are "cat", "and", and "dog".

Example 2:

Input: sentence = "!this  1-s b8d!"
Output: 0
Explanation: There are no valid words in the sentence.
"!this" is invalid because it starts with a punctuation mark.
"1-s" and "b8d" are invalid because they contain digits.

Example 3:

Input: sentence = "alice and  bob are playing stone-game10"
Output: 5
Explanation: The valid words in the sentence are "alice", "and", "bob", "are", and "playing".
"stone-game10" is invalid because it contains digits.

Example 4:

Input: sentence = "he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."
Output: 6
Explanation: The valid words in the sentence are "he", "bought", "pencils,", "erasers,", "and", and "pencil-sharpener.".

Constraints:

1 <= sentence.length <= 1000
sentence only contains lowercase English letters, digits, ' ', '-', '!', '.', and ','.
There will be at least 1 token.

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

int countValidWords(string sentence) {

stringstream ss(sentence);

string word;

int ans = 0;

while (ss >> word) {

bool valid = true;

int hyphen = 0;

int punctuation = 0;

char p = ' ';

for (char c : word) {

if (c == '-') {

if (++hyphen > 1 || !isalpha(p)) {

valid = false;

break;

}

} else if (c == '!' || c == '.' || c == ',') {

if (++punctuation > 1 || p == '-') {

valid = false;

break;

}

} else if (isalpha(c)) {

if (punctuation) {

valid = false;

break;

}

} else {

valid = false;

break;

}

p = c;

}

if (word.back() == '-')

valid = false;

if (valid) ++ans;

}

return ans;

}

};

Solution 2: Regex

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

Python

# Author: Huahua

class Solution:

def countValidWords(self, sentence: str) -> int:

ans = 0

for word in sentence.split():

if word.strip() and re.fullmatch('^([a-z]+(-?[a-z]+)?)?[\.,!]?$', word.strip()):

ans += 1

return ans

花花酱 LeetCode 2022. Convert 1D Array Into 2D Array

By zxi on October 23, 2021

You are given a 0-indexed 1-dimensional (1D) integer array original, and two integers, m and n. You are tasked with creating a 2-dimensional (2D) array with m rows and n columns using all the elements from original.

The elements from indices 0 to n - 1 (inclusive) of original should form the first row of the constructed 2D array, the elements from indices n to 2 * n - 1 (inclusive) should form the second row of the constructed 2D array, and so on.

Return an m x n 2D array constructed according to the above procedure, or an empty 2D array if it is impossible.

Example 1:

Input: original = [1,2,3,4], m = 2, n = 2
Output: [[1,2],[3,4]]
Explanation:
The constructed 2D array should contain 2 rows and 2 columns.
The first group of n=2 elements in original, [1,2], becomes the first row in the constructed 2D array.
The second group of n=2 elements in original, [3,4], becomes the second row in the constructed 2D array.

Example 2:

Input: original = [1,2,3], m = 1, n = 3
Output: [[1,2,3]]
Explanation:
The constructed 2D array should contain 1 row and 3 columns.
Put all three elements in original into the first row of the constructed 2D array.

Example 3:

Input: original = [1,2], m = 1, n = 1
Output: []
Explanation:
There are 2 elements in original.
It is impossible to fit 2 elements in a 1x1 2D array, so return an empty 2D array.

Example 4:

Input: original = [3], m = 1, n = 2
Output: []
Explanation:
There is 1 element in original.
It is impossible to make 1 element fill all the spots in a 1x2 2D array, so return an empty 2D array.

Constraints:

1 <= original.length <= 5 * 10⁴
1 <= original[i] <= 10⁵
1 <= m, n <= 4 * 10⁴

Solution: Brute Force

the i-th element in original array will have index (i//n, i % n) in the 2D array.

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

C++

class Solution {

public:

vector<vector<int>> construct2DArray(vector<int>& original, int m, int n) {

if (original.size() != m * n) return {};

vector<vector<int>> ans(m, vector<int>(n));

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

ans[i / n][i % n] = original[i];

return ans;

}

};

花花酱 LeetCode 2032. Two Out of Three

By zxi on October 21, 2021

Given three integer arrays nums1, nums2, and nums3, return a distinct array containing all the values that are present in at least two out of the three arrays. You may return the values in any order.

Example 1:

Input: nums1 = [1,1,3,2], nums2 = [2,3], nums3 = [3]
Output: [3,2]
Explanation: The values that are present in at least two arrays are:
- 3, in all three arrays.
- 2, in nums1 and nums2.

Example 2:

Input: nums1 = [3,1], nums2 = [2,3], nums3 = [1,2]
Output: [2,3,1]
Explanation: The values that are present in at least two arrays are:
- 2, in nums2 and nums3.
- 3, in nums1 and nums2.
- 1, in nums1 and nums3.

Example 3:

Input: nums1 = [1,2,2], nums2 = [4,3,3], nums3 = [5]
Output: []
Explanation: No value is present in at least two arrays.

Constraints:

1 <= nums1.length, nums2.length, nums3.length <= 100
1 <= nums1[i], nums2[j], nums3[k] <= 100

Solution: Hashmap / Bitmask

s[x] := bitmask of x in all array[i]

s[x] = 101 => x in array0 and array2

Time complexity: O(n1 + n2 + n3)
Space complexity: O(n1 + n2 + n3)

C++

// Author: Huahua

class Solution {

public:

vector<int> twoOutOfThree(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3) {

unordered_map<int, int> s;

for (int x : nums1) s[x] |= 1;

for (int x : nums2) s[x] |= 2;

for (int x : nums3) s[x] |= 4;

vector<int> ans;

for (auto [x, v] : s)

if (__builtin_popcount(v) >= 2) ans.push_back(x);

return ans;

}

};

花花酱 LeetCode 2037. Minimum Number of Moves to Seat Everyone

By zxi on October 18, 2021

There are n seats and n students in a room. You are given an array seats of length n, where seats[i] is the position of the i^th seat. You are also given the array students of length n, where students[j] is the position of the j^th student.

You may perform the following move any number of times:

Increase or decrease the position of the i^th student by 1 (i.e., moving the i^th student from position x to x + 1 or x - 1)

Return the minimum number of moves required to move each student to a seat such that no two students are in the same seat.

Note that there may be multiple seats or students in the same position at the beginning.

Example 1:

Input: seats = [3,1,5], students = [2,7,4]
Output: 4
Explanation: The students are moved as follows:
- The first student is moved from from position 2 to position 1 using 1 move.
- The second student is moved from from position 7 to position 5 using 2 moves.
- The third student is moved from from position 4 to position 3 using 1 move.
In total, 1 + 2 + 1 = 4 moves were used.

Example 2:

Input: seats = [4,1,5,9], students = [1,3,2,6]
Output: 7
Explanation: The students are moved as follows:
- The first student is not moved.
- The second student is moved from from position 3 to position 4 using 1 move.
- The third student is moved from from position 2 to position 5 using 3 moves.
- The fourth student is moved from from position 6 to position 9 using 3 moves.
In total, 0 + 1 + 3 + 3 = 7 moves were used.

Example 3:

Input: seats = [2,2,6,6], students = [1,3,2,6]
Output: 4
Explanation: The students are moved as follows:
- The first student is moved from from position 1 to position 2 using 1 move.
- The second student is moved from from position 3 to position 6 using 3 moves.
- The third student is not moved.
- The fourth student is not moved.
In total, 1 + 3 + 0 + 0 = 4 moves were used.

Constraints:

n == seats.length == students.length
1 <= n <= 100
1 <= seats[i], students[j] <= 100

Solution: Greedy

Sort both arrays, move students[i] to seats[i].

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

C++

// Author: Huahua

class Solution {

public:

int minMovesToSeat(vector<int>& seats, vector<int>& students) {

sort(begin(seats), end(seats));

sort(begin(students), end(students));

int ans = 0;

for (size_t i = 0; i < seats.size(); ++i)

ans += abs(seats[i] - students[i]);

return ans;

}

};