Posts tagged as “easy”

花花酱 LeetCode 1374. Generate a String With Characters That Have Odd Counts

By zxi on March 8, 2020

Given an integer n, return a string with n characters such that each character in such string occurs an odd number of times.

The returned string must contain only lowercase English letters. If there are multiples valid strings, return any of them.

Example 1:

Input: n = 4
Output: "pppz"
Explanation: "pppz" is a valid string since the character 'p' occurs three times and the character 'z' occurs once. Note that there are many other valid strings such as "ohhh" and "love".

Example 2:

Input: n = 2
Output: "xy"
Explanation: "xy" is a valid string since the characters 'x' and 'y' occur once. Note that there are many other valid strings such as "ag" and "ur".

Example 3:

Input: n = 7
Output: "holasss"

Constraints:

1 <= n <= 500

Solution: Greedy

if n is odd, return n ‘a’s.
otherwise, return n -1 ‘a’s and 1 ‘b’

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

C++

// Author: Huahua

class Solution {

public:

string generateTheString(int n) {

return n & 1 ? string(n, 'a') : string(n - 1, 'a') + "b";

}

};

Python3

# Author: Huahua

class Solution:

def generateTheString(self, n: int) -> str:

ans = ['a'] * n if n % 2 == 1 else ['a'] * (n - 1) + ['b']

return ''.join(ans)

花花酱 LeetCode 1370. Increasing Decreasing String

By zxi on March 7, 2020

Given a string s. You should re-order the string using the following algorithm:

Pick the smallest character from s and append it to the result.
Pick the smallest character from s which is greater than the last appended character to the result and append it.
Repeat step 2 until you cannot pick more characters.
Pick the largest character from s and append it to the result.
Pick the largest character from s which is smaller than the last appended character to the result and append it.
Repeat step 5 until you cannot pick more characters.
Repeat the steps from 1 to 6 until you pick all characters from s.

In each step, If the smallest or the largest character appears more than once you can choose any occurrence and append it to the result.

Return the result string after sorting s with this algorithm.

Example 1:

Input: s = "aaaabbbbcccc"
Output: "abccbaabccba"
Explanation: After steps 1, 2 and 3 of the first iteration, result = "abc"
After steps 4, 5 and 6 of the first iteration, result = "abccba"
First iteration is done. Now s = "aabbcc" and we go back to step 1
After steps 1, 2 and 3 of the second iteration, result = "abccbaabc"
After steps 4, 5 and 6 of the second iteration, result = "abccbaabccba"

Example 2:

Input: s = "rat"
Output: "art"
Explanation: The word "rat" becomes "art" after re-ordering it with the mentioned algorithm.

Example 3:

Input: s = "leetcode"
Output: "cdelotee"

Example 4:

Input: s = "ggggggg"
Output: "ggggggg"

Example 5:

Input: s = "spo"
Output: "ops"

Constraints:

1 <= s.length <= 500
s contains only lower-case English letters.

Solution: Counting frequency of each character

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

C++

// Author: Huahua

class Solution {

public:

string sortString(string s) {

vector<int> count(26);

for (char c : s) ++count[c - 'a'];

string ans;

while (ans.length() != s.length()) {

for (char c = 'a'; c <= 'z'; ++c)

if (--count[c - 'a'] >= 0)

ans += c;

for (char c = 'z'; c >= 'a'; --c)

if (--count[c - 'a'] >= 0)

ans += c;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def sortString(self, s: str) -> str:

seq = string.ascii_lowercase + string.ascii_lowercase[::-1]

count = collections.Counter(s)

ans = ""

while len(ans) != len(s):

for c in seq:

if count[c] > 0:

ans += c

count[c] -= 1

return ans

花花酱 LeetCode 1365. How Many Numbers Are Smaller Than the Current Number

By zxi on March 2, 2020

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation: 
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). 
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1). 
For nums[3]=2 there exist one smaller number than it (1). 
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:

2 <= nums.length <= 500
0 <= nums[i] <= 100

Solution 1: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> ans(n);

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

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

if (i != j && nums[j] < nums[i]) ++ans[i];

return ans;

}

};

Solution 2: Sort + Binary Search

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

C++

// Author: Huahua

class Solution {

public:

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

const int n = nums.size();

vector<int> s(nums);

sort(begin(s), end(s));

vector<int> ans(n);

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

ans[i] = distance(begin(s), lower_bound(begin(s), end(s), nums[i]));

return ans;

}

};

Solution 3: Cumulative frequency

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

C++

// Author: Huahua

class Solution {

public:

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

vector<int> f(101);

for (int x : nums) ++f[x];

partial_sum(begin(f), end(f), begin(f));

for (int& x : nums)

x = x == 0 ? 0 : f[x - 1];

return nums;

}

};

花花酱 LeetCode 1360. Number of Days Between Two Dates

By zxi on February 23, 2020

Write a program to count the number of days between two dates.

The two dates are given as strings, their format is YYYY-MM-DD as shown in the examples.

Example 1:

Input: date1 = "2019-06-29", date2 = "2019-06-30"
Output: 1

Example 2:

Input: date1 = "2020-01-15", date2 = "2019-12-31"
Output: 15

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Solution: Convert to days since epoch

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

C++

// Author: Huahua

class Solution {

public:

int daysBetweenDates(string date1, string date2) {

array<int, 12> m{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

auto isLeap = [](int year) {

return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);

};

auto daysFromEpoch = [&](const string& date) {

int year = stoi(date.substr(0, 4));

int month = stoi(date.substr(5, 2));

int days = stoi(date.substr(8, 2));

for (int i = 1970; i < year; ++i)

days += 365 + isLeap(i);

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

days += m[i - 1];

days += month > 2 && isLeap(year);

return days;

};

return abs(daysFromEpoch(date1) - daysFromEpoch(date2));

}

};

花花酱 LeetCode 1356. Sort Integers by The Number of 1 Bits

By zxi on February 22, 2020

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Solution: Sorting

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

C++

// Author: Huahua

class Solution {

public:

vector<int> sortByBits(vector<int>& arr) {

sort(begin(arr), end(arr), [](const int a, const int b){

int key_a = __builtin_popcount(a);

int key_b = __builtin_popcount(b);

if (key_a != key_b) return key_a < key_b;

return a < b;

});

return arr;

}

};

Python3

# Author: Huahua

class Solution:

def sortByBits(self, arr: List[int]) -> List[int]:

return sorted(arr, key=lambda x: (bin(x).count('1') << 16) + x)