Posts tagged as “easy”

花花酱 LeetCode 2224. Minimum Number of Operations to Convert Time

By zxi on April 2, 2022

You are given two strings current and correct representing two 24-hour times.

24-hour times are formatted as "HH:MM", where HH is between 00 and 23, and MM is between 00 and 59. The earliest 24-hour time is 00:00, and the latest is 23:59.

In one operation you can increase the time current by 1, 5, 15, or 60 minutes. You can perform this operation any number of times.

Return the minimum number of operations needed to convert current to correct.

Example 1:

Input: current = "02:30", correct = "04:35"
Output: 3
Explanation:
We can convert current to correct in 3 operations as follows:
- Add 60 minutes to current. current becomes "03:30".
- Add 60 minutes to current. current becomes "04:30".
- Add 5 minutes to current. current becomes "04:35".
It can be proven that it is not possible to convert current to correct in fewer than 3 operations.

Example 2:

Input: current = "11:00", correct = "11:01"
Output: 1
Explanation: We only have to add one minute to current, so the minimum number of operations needed is 1.

Constraints:

current and correct are in the format "HH:MM"
current <= correct

Solution: Greedy

Start with 60, then 15, 5 and finally increase 1 minute a time.

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

C++

// Author: Huahua

class Solution {

public:

int convertTime(string current, string correct) {

auto getMinute = [](string_view t) {

return (t[0] - '0') * 10 * 60

+ (t[1] - '0') * 60

+ (t[3] - '0') * 10

+ (t[4] - '0');

};

int t1 = getMinute(current);

int t2 = getMinute(correct);

int ans = 0;

for (int d : {60, 15, 5, 1})

while (t2 - t1 >= d) {

++ans;

t1 += d;

}

return ans;

}

};

花花酱 LeetCode 2220. Minimum Bit Flips to Convert Number

By zxi on April 2, 2022

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0.

For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc.

Given two integers start and goal, return the minimum number of bit flips to convert start to goal.

Example 1:

Input: start = 10, goal = 7
Output: 3
Explanation: The binary representation of 10 and 7 are 1010 and 0111 respectively. We can convert 10 to 7 in 3 steps:
- Flip the first bit from the right: 1010 -> 1011.
- Flip the third bit from the right: 1011 -> 1111.
- Flip the fourth bit from the right: 1111 -> 0111.
It can be shown we cannot convert 10 to 7 in less than 3 steps. Hence, we return 3.

Example 2:

Input: start = 3, goal = 4
Output: 3
Explanation: The binary representation of 3 and 4 are 011 and 100 respectively. We can convert 3 to 4 in 3 steps:
- Flip the first bit from the right: 011 -> 010.
- Flip the second bit from the right: 010 -> 000.
- Flip the third bit from the right: 000 -> 100.
It can be shown we cannot convert 3 to 4 in less than 3 steps. Hence, we return 3.

Constraints:

0 <= start, goal <= 10⁹

Solution: XOR

start ^ goal will give us the bitwise difference of start and goal in binary format.
ans = # of 1 ones in the xor-ed results.
For C++, we can use __builtin_popcount or bitset<32>::count() to get the number of bits set for a given integer.

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

C++

// Author: Huahua

class Solution {

public:

int minBitFlips(int start, int goal) {

return bitset<32>(start ^ goal).count(); // __builtin_popcount(start ^ goal);

}

};

花花酱 LeetCode 2215. Find the Difference of Two Arrays

By zxi on March 28, 2022

Given two 0-indexed integer arrays nums1 and nums2, return a list answer of size 2 where:

answer[0] is a list of all distinct integers in nums1 which are not present in nums2.
answer[1] is a list of all distinct integers in nums2 which are not present in nums1.

Note that the integers in the lists may be returned in any order.

Example 1:

Input: nums1 = [1,2,3], nums2 = [2,4,6]
Output: [[1,3],[4,6]]
Explanation:
For nums1, nums1[1] = 2 is present at index 0 of nums2, whereas nums1[0] = 1 and nums1[2] = 3 are not present in nums2. Therefore, answer[0] = [1,3].
For nums2, nums2[0] = 2 is present at index 1 of nums1, whereas nums2[1] = 4 and nums2[2] = 6 are not present in nums2. Therefore, answer[1] = [4,6].

Example 2:

Input: nums1 = [1,2,3,3], nums2 = [1,1,2,2]
Output: [[3],[]]
Explanation:
For nums1, nums1[2] and nums1[3] are not present in nums2. Since nums1[2] == nums1[3], their value is only included once and answer[0] = [3].
Every integer in nums2 is present in nums1. Therefore, answer[1] = [].

Constraints:

1 <= nums1.length, nums2.length <= 1000
-1000 <= nums1[i], nums2[i] <= 1000

Solution: Hashtable

Use two hashtables to store the unique numbers of array1 and array2 respectfully.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findDifference(vector<int>& nums1, vector<int>& nums2) {

vector<vector<int>> ans(2);

unordered_set<int> s1(begin(nums1), end(nums1));

unordered_set<int> s2(begin(nums2), end(nums2));

for (int x : s1)

if (!s2.count(x)) ans[0].push_back(x);

for (int x : s2)

if (!s1.count(x)) ans[1].push_back(x);

return ans;

}

};

花花酱 LeetCode 2206. Divide Array Into Equal Pairs

By zxi on March 21, 2022

You are given an integer array nums consisting of 2 * n integers.

You need to divide nums into n pairs such that:

Each element belongs to exactly one pair.
The elements present in a pair are equal.

Return true if nums can be divided into n pairs, otherwise return false.

Example 1:

Input: nums = [3,2,3,2,2,2]
Output: true
Explanation: 
There are 6 elements in nums, so they should be divided into 6 / 2 = 3 pairs.
If nums is divided into the pairs (2, 2), (3, 3), and (2, 2), it will satisfy all the conditions.

Example 2:

Input: nums = [1,2,3,4]
Output: false
Explanation: 
There is no way to divide nums into 4 / 2 = 2 pairs such that the pairs satisfy every condition.

Constraints:

nums.length == 2 * n
1 <= n <= 500
1 <= nums[i] <= 500

Solution: Hashtable

Each number has to appear even numbers in order to be paired. Count the frequency of each number, return true if all of them are even numbers, return false otherwise.

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

C++

// Author: Huahua

class Solution {

public:

bool divideArray(vector<int>& nums) {

unordered_map<int, int> m;

for (int num : nums)

++m[num];

return all_of(begin(m), end(m), [](const auto& e) { return e.second % 2 == 0; });

}

};

花花酱 LeetCode 2190. Most Frequent Number Following Key In an Array

By zxi on March 11, 2022

You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

0 <= i <= nums.length - 2,
nums[i] == key and,
nums[i + 1] == target.

Return the target with the maximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

Input: nums = [1,100,200,1,100], key = 1
Output: 100
Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.
No other integers follow an occurrence of key, so we return 100.

Example 2:

Input: nums = [2,2,2,2,3], key = 2
Output: 2
Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.
For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.
target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.

Constraints:

2 <= nums.length <= 1000
1 <= nums[i] <= 1000
The test cases will be generated such that the answer is unique.

Solution: Hashtable

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

C++

// Author: Huahua

class Solution {

public:

int mostFrequent(vector<int>& nums, int key) {

const int n = nums.size();

unordered_map<int, int> m;

int count = 0;

int ans = 0;

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

if (nums[i - 1] == key && ++m[nums[i]] > count) {

count = m[nums[i]];

ans = nums[i];

}

return ans;

}

};