Huahua’s Tech Road

花花酱 LeetCode 2028. Find Missing Observations

By zxi on October 4, 2021

You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.

You are given an integer array rolls of length m where rolls[i] is the value of the i^th observation. You are also given the two integers mean and n.

Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.

The average value of a set of k numbers is the sum of the numbers divided by k.

Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.

Example 1:

Input: rolls = [3,2,4,3], mean = 4, n = 2
Output: [6,6]
Explanation: The mean of all n + m rolls is (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4.

Example 2:

Input: rolls = [1,5,6], mean = 3, n = 4
Output: [2,3,2,2]
Explanation: The mean of all n + m rolls is (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3.

Example 3:

Input: rolls = [1,2,3,4], mean = 6, n = 4
Output: []
Explanation: It is impossible for the mean to be 6 no matter what the 4 missing rolls are.

Example 4:

Input: rolls = [1], mean = 3, n = 1
Output: [5]
Explanation: The mean of all n + m rolls is (1 + 5) / 2 = 3.

Constraints:

m == rolls.length
1 <= n, m <= 10⁵
1 <= rolls[i], mean <= 6

Solution: Math & Greedy

Total sum = (m + n) * mean
Left = Total sum – sum(rolls) = (m + n) * mean – sum(rolls)
If left > 6 * n or left < 1 * n, then there is no solution.
Otherwise, we need to distribute Left into n rolls.
There are very ways to do that, one of them is even distribution, e.g. using the average number as much as possible, and use avg + 1 to fill the gap.
Compute the average and reminder: x = left / n, r = left % n.
there will be n – r of x and r of x + 1 in the output array.

e.g. [1, 5, 6], mean = 3, n = 4
Total sum = (3 + 4) * 3 = 21
Left = 21 – (1 + 5 + 6) = 9
x = 9 / 4 = 2, r = 9 % 4 = 1
Ans = [2, 2, 2, 2+1] = [2,2,2,3]

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

C++

class Solution {

public:

vector<int> missingRolls(vector<int>& rolls, int mean, int n) {

const int m = rolls.size();

int t = accumulate(begin(rolls), end(rolls), 0);

int left = mean * (m + n) - t;

if (left > 6 * n || left < n) return {};

vector<int> ans(n, left / n);

for (int i = 0; i < left % n; ++i) ++ans[i];

return ans;

}

};

花花酱 LeetCode 2027. Minimum Moves to Convert String

By zxi on October 4, 2021

You are given a string s consisting of n characters which are either 'X' or 'O'.

A move is defined as selecting three consecutive characters of s and converting them to 'O'. Note that if a move is applied to the character 'O', it will stay the same.

Return the minimum number of moves required so that all the characters of s are converted to 'O'.

Example 1:

Input: s = "XXX"
Output: 1
Explanation: XXX -> OOO
We select all the 3 characters and convert them in one move.

Example 2:

Input: s = "XXOX"
Output: 2
Explanation: XXOX -> OOOX -> OOOO
We select the first 3 characters in the first move, and convert them to 'O'.
Then we select the last 3 characters and convert them so that the final string contains all 'O's.

Example 3:

Input: s = "OOOO"
Output: 0
Explanation: There are no 'X's in s to convert.

Constraints:

3 <= s.length <= 1000
s[i] is either 'X' or 'O'.

Solution: Straight Forward

if s[i] == ‘X’, change s[i], s[i + 1] and s[i + 2] to ‘O’.

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

C++

class Solution {

public:

int minimumMoves(string s) {

const int n = s.length();

int ans = 0;

for (size_t i = 0; i < n; ++i) {

if (s[i] == 'X') {

ans += 1;

i += 2;

}

return ans;

}

};

花花酱 LeetCode 1906. Minimum Absolute Difference Queries

By zxi on August 15, 2021

The minimum absolute difference of an array a is defined as the minimum value of |a[i] - a[j]|, where 0 <= i < j < a.length and a[i] != a[j]. If all elements of a are the same, the minimum absolute difference is -1.

For example, the minimum absolute difference of the array [5,2,3,7,2] is |2 - 3| = 1. Note that it is not 0 because a[i] and a[j] must be different.

You are given an integer array nums and the array queries where queries[i] = [l_i, r_i]. For each query i, compute the minimum absolute difference of the subarray nums[l_i...r_i] containing the elements of nums between the 0-based indices l_i and r_i (inclusive).

Return an array ans where ans[i] is the answer to the i^th query.

A subarray is a contiguous sequence of elements in an array.

The value of |x| is defined as:

x if x >= 0.
-x if x < 0.

Example 1:

Input: nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
Output: [2,1,4,1]
Explanation: The queries are processed as follows:
- queries[0] = [0,1]: The subarray is [1,3] and the minimum absolute difference is |1-3| = 2.
- queries[1] = [1,2]: The subarray is [3,4] and the minimum absolute difference is |3-4| = 1.
- queries[2] = [2,3]: The subarray is [4,8] and the minimum absolute difference is |4-8| = 4.
- queries[3] = [0,3]: The subarray is [1,3,4,8] and the minimum absolute difference is |3-4| = 1.

Example 2:

Input: nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
Output: [-1,1,1,3]
Explanation: The queries are processed as follows:
- queries[0] = [2,3]: The subarray is [2,2] and the minimum absolute difference is -1 because all the
  elements are the same.
- queries[1] = [0,2]: The subarray is [4,5,2] and the minimum absolute difference is |4-5| = 1.
- queries[2] = [0,5]: The subarray is [4,5,2,2,7,10] and the minimum absolute difference is |4-5| = 1.
- queries[3] = [3,5]: The subarray is [2,7,10] and the minimum absolute difference is |7-10| = 3.

Constraints:

2 <= nums.length <= 10⁵
1 <= nums[i] <= 100
1 <= queries.length <= 2 * 10⁴
0 <= l_i < r_i < nums.length

Solution: Binary Search

Since the value range of num is quiet small [1~100], we can store the indices for each value.
[2, 1, 2, 2, 3] => {1: [1], 2: [0, 2, 3]: 3: [4]}.

For each query, we try all possible value b. Check whether b is the query range using binary search, we also keep tracking the previous available value a, ans will be min{b – a}.

Time complexity: O(n + q * 100 * log(n))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> minDifference(vector<int>& nums, vector<vector<int>>& queries) {

constexpr int kMax = 100;

const int n = nums.size();

vector<vector<int>> idx(kMax + 1);

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

idx[nums[i]].push_back(i);

vector<int> ans;

for (const auto& q: queries) {

int diff = INT_MAX;

for (int a = 0, b = 1; b <= kMax; ++b) {

auto it = lower_bound(begin(idx[b]), end(idx[b]), q[0]);

if (it == end(idx[b]) || *it > q[1]) continue;

if (a) diff = min(diff, b - a);

a = b;

}

ans.push_back(diff == INT_MAX ? -1 : diff);

}

return ans;

}

};

花花酱 LeetCode 1905. Count Sub Islands

By zxi on August 15, 2021

You are given two m x n binary matrices grid1 and grid2 containing only 0‘s (representing water) and 1‘s (representing land). An island is a group of 1‘s connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

Example 1:

Input: grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output: 3
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.

Example 2:

Input: grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
Output: 2 
Explanation: In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.

Constraints:

m == grid1.length == grid2.length
n == grid1[i].length == grid2[i].length
1 <= m, n <= 500
grid1[i][j] and grid2[i][j] are either 0 or 1.

Solution: Coloring

Give each island in grid1 a different color. Whiling using the same method to find island and coloring it in grid2, we also check whether the same cell in grid1 always has the same color.

Time complexity: O(mn)
Space complexity: O(1) modify in place or O(mn)

C++

// Author: Huahua

class Solution {

public:

int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {

const int m = grid1.size();

const int n = grid1[0].size();

int valid = 1;

function<void(int, int, int, int)> color = [&](int i, int j, int c, int p) {

if (i < 0 || i >= m || j < 0 || j >= n) return;

auto& gc = p ? grid2 : grid1;

auto& go = p ? grid1 : grid2;

if (gc[i][j] != 1) return;

gc[i][j] = c;

if (p && go[i][j] != c) valid = 0;

color(i + 1, j, c, p);

color(i - 1, j, c, p);

color(i, j + 1, c, p);

color(i, j - 1, c, p);

};

for (int i = 0, c = 2; i < m; ++i)

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

if (grid1[i][j] == 1) color(i, j, c++, 0);

int ans = 0;

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

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

if (grid2[i][j] == 1 && grid1[i][j]) {

valid = 1;

color(i, j, grid1[i][j], 1);

ans += valid;

}

return ans;

}

};

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

By zxi on August 15, 2021

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

startTime and finishTime are in the format HH:MM.
00 <= HH <= 23
00 <= MM <= 59
startTime and finishTime are not equal.

Solution: String / Simple math

ans = max(0, floor(end / 15) – ceil(start / 15))

Tips:

Write a reusable function to parse time to minutes.
a / b for floor, (a + b – 1) / b for ceil

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

C++

// Author: Huahua

class Solution {

public:

int numberOfRounds(string startTime, string finishTime) {

auto parseTime = [](string t) {

return ((t[0] - '0') * 10 + (t[1] - '0')) * 60 + (t[3] - '0') * 10 + t[4] - '0';

};

int m1 = parseTime(startTime);

int m2 = parseTime(finishTime);

if (m2 < m1) m2 += 24 * 60;

return max(0, m2 / 15 - (m1 + 14) / 15);

}

};

Huahua's Tech Road

花花酱 LeetCode 2028. Find Missing Observations

Solution: Math & Greedy

C++

花花酱 LeetCode 2027. Minimum Moves to Convert String

Solution: Straight Forward

C++

花花酱 LeetCode 1906. Minimum Absolute Difference Queries

Solution: Binary Search

C++

花花酱 LeetCode 1905. Count Sub Islands

Solution: Coloring

C++

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

Solution: String / Simple math

C++