Huahua’s Tech Road

花花酱 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);

}

};

花花酱 LeetCode 1903. Largest Odd Number in String

By zxi on August 15, 2021

You are given a string num, representing a large integer. Return the largest-valued odd integer (as a string) that is a non-empty substring of num, or an empty string "" if no odd integer exists.

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: num = "52"
Output: "5"
Explanation: The only non-empty substrings are "5", "2", and "52". "5" is the only odd number.

Example 2:

Input: num = "4206"
Output: ""
Explanation: There are no odd numbers in "4206".

Example 3:

Input: num = "35427"
Output: "35427"
Explanation: "35427" is already an odd number.

Constraints:

1 <= num.length <= 10⁵
num only consists of digits and does not contain any leading zeros.

Solution: Find right most odd digit

We just need to find the right most digit that is odd, answer will be num[0:r].

Answer must start with num[0].
Proof:
Assume the largest number is num[i:r] i > 0, we can always extend to the left, e.g. num[i-1:r] which is also an odd number and it’s larger than num[i:r] which contradicts our assumption. Thus the largest odd number (if exists) must start with num[0].

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

C++

// Author: Huahua

class Solution {

public:

string largestOddNumber(string num) {

for (int i = num.length() - 1; i >= 0; --i)

if ((num[i] - '0') & 1) return num.substr(0, i + 1);

return "";

}

};

Huahua's Tech Road

花花酱 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++

花花酱 LeetCode 1903. Largest Odd Number in String

Solution: Find right most odd digit

C++