Huahua’s Tech Road

花花酱 LeetCode 1326. Minimum Number of Taps to Open to Water a Garden

By zxi on January 19, 2020

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Solution 1: Greedy

Reduce to 1024. Video Stitching

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

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<pair<int, int>> t;

// O(n) reduction

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

t.emplace_back(max(0, i - ranges[i]),

min(i + ranges[i], n));

// 1024. Video Stiching

sort(begin(t), end(t));

int ans = 0;

int i = 0;

int l = 0;

int e = 0;

while (e < n) {

// Extend to the right most w.r.t t[i].first <= l

while (i <= n && t[i].first <= l)

e = max(e, t[i++].second);

if (l == e) return -1; // Can not extend

l = e;

++ans;

}

return ans;

}

};

Solution 2: Greedy

Reduce to 45. Jump Game II

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

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<int> nums(ranges.size());

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

int s = max(0, i - ranges[i]);

nums[s] = max(nums[s], i + ranges[i]);

}

// 45. Jump Game II

int steps = 0;

int l = 0;

int e = 0;

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

if (i > e) return -1;

if (i > l) { ++steps; l = e; }

e = max(e, nums[i]);

}

return steps;

}

};

花花酱 LeetCode 42. Trapping Rain Water

By zxi on January 15, 2020

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution 1: Brute Force

r[i] = min(max(h[0:i+1]), max(h[i:n]))
ans = sum(r[i])

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

C++

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

int ans = 0;

auto sit = cbegin(height);

auto eit = cend(height);

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

int l = *max_element(sit, sit + i + 1);

int r = *max_element(sit + i, eit);

ans += min(l, r) - height[i];

}

return ans;

}

};

Solution 2: DP

l[i] := max(h[0:i+1])
r[i] := max(h[i:n])
ans = sum(min(l[i], r[i]) – h[i])

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

C++

// Author: Huahua

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

vector<int> l(n);

vector<int> r(n);

int ans = 0;

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

l[i] = i == 0 ? height[i] : max(l[i - 1], height[i]);

for (int i = n - 1; i >= 0; --i)

r[i] = i == n - 1 ? height[i] : max(r[i + 1], height[i]);

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

ans += min(l[i], r[i]) - height[i];

return ans;

}

};

Solution 3: Two Pointers

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

C++

// Author: Huahua, 4 ms, 9.1 MB

class Solution {

public:

int trap(vector<int>& height) {

const int n = height.size();

if (n == 0) return 0;

int l = 0;

int r = n - 1;

int max_l = height[l];

int max_r = height[r];

int ans = 0;

while (l < r) {

if (max_l < max_r) {

ans += max_l - height[l];

max_l = max(max_l, height[++l]);

} else {

ans += max_r - height[r];

max_r = max(max_r, height[--r]);

}

return ans;

}

};

花花酱 LeetCode 1318. Minimum Flips to Make a OR b Equal to c

By zxi on January 13, 2020

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

Input: a = 1, b = 2, c = 3
Output: 0

Constraints:

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

Solution: Bit operation

If the bit of c is 1, a / b at least has one 1. cost = 1 – ((a | b) & 1)
If the bit of c is 0, a / b must be 0, cost = (a & 1) + (b & 1)

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

C++

// Author: Huahua

class Solution {

public:

int minFlips(int a, int b, int c) {

int count = 0;

for (int i = 0; i < 32; ++i) {

if (c & 1) count += 1 - ((a | b) & 1);

else count += (a & 1) + (b & 1);

a >>= 1;

b >>= 1;

c >>= 1;

}

return count;

}

};

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

By zxi on January 13, 2020

Given an integer n. No-Zero integer is a positive integer which doesn’t contain any 0 in its decimal representation.

Return a list of two integers [A, B] where:

A and B are No-Zero integers.
A + B = n

It’s guarateed that there is at least one valid solution. If there are many valid solutions you can return any of them.

Example 1:

Input: n = 2

Output: [1,1]

Explanation: A = 1, B = 1. A + B = n and both A and B don't contain any 0 in their decimal representation.

Example 2:

1 2	<strong>Input:</strong> n = 11 <strong>Output:</strong> [2,9]

Example 3:

1 2	<strong>Input:</strong> n = 10000 <strong>Output:</strong> [1,9999]

Example 4:

1 2	<strong>Input:</strong> n = 69 <strong>Output:</strong> [1,68]

Example 5:

1 2	<strong>Input:</strong> n = 1010 <strong>Output:</strong> [11,999]

Constraints:

2 <= n <= 10^4

Solution: Brute Force

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getNoZeroIntegers(int n) {

auto valid = [](int x) {

if (!x) return false;

while (x) {

if (x % 10 == 0) return false;

x /= 10;

}

return true;

};

for (int i = 1; i <= n / 2; ++i)

if (valid(i) && valid(n - i))

return {i, n - i};

return {};

}

};

花花酱 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers

By zxi on January 12, 2020

You have a keyboard layout as shown above in the XY plane, where each English uppercase letter is located at some coordinate, for example, the letter A is located at coordinate (0,0), the letter B is located at coordinate (0,1), the letter P is located at coordinate (2,3) and the letter Z is located at coordinate (4,1).

Given the string word, return the minimum total distance to type such string using only two fingers. The distance between coordinates (x₁,y₁) and (x₂,y₂) is |x₁ – x₂| + |y₁ – y₂|.

Note that the initial positions of your two fingers are considered free so don’t count towards your total distance, also your two fingers do not have to start at the first letter or the first two letters.

Example 1:

Input: word = "CAKE"
Output: 3
Explanation: 
Using two fingers, one optimal way to type "CAKE" is: 
Finger 1 on letter 'C' -> cost = 0 
Finger 1 on letter 'A' -> cost = Distance from letter 'C' to letter 'A' = 2 
Finger 2 on letter 'K' -> cost = 0 
Finger 2 on letter 'E' -> cost = Distance from letter 'K' to letter 'E' = 1 
Total distance = 3

Example 2:

Input: word = "HAPPY"
Output: 6
Explanation: 
Using two fingers, one optimal way to type "HAPPY" is:
Finger 1 on letter 'H' -> cost = 0
Finger 1 on letter 'A' -> cost = Distance from letter 'H' to letter 'A' = 2
Finger 2 on letter 'P' -> cost = 0
Finger 2 on letter 'P' -> cost = Distance from letter 'P' to letter 'P' = 0
Finger 1 on letter 'Y' -> cost = Distance from letter 'A' to letter 'Y' = 4
Total distance = 6

Example 3:

Input: word = "NEW"
Output: 3

Example 4:

Input: word = "YEAR"
Output: 7

Constraints:

2 <= word.length <= 300
Each word[i] is an English uppercase letter.

Solution: DP

Top down: O(n*27^2)

C++

// Author: Huahua, 64 ms, 46.6 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

vector<vector<vector<int>>> mem(n, vector<vector<int>>(27, vector<int>(27, -1)));

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

// min cost to type word[i:n]. l, r are the last finger positions.

function<int(int, int, int)> dp = [&](int i, int l, int r) {

if (i == n) return 0;

if (mem[i][l][r] >= 0) return mem[i][l][r];

int c = word[i] - 'A';

return mem[i][l][r] = min(dp(i + 1, c, r) + cost(l, c),

dp(i + 1, l, c) + cost(r, c));

};

return dp(0, kRest, kRest);

}

};

C++

// Author: Huahua, 12 ms, 10.1 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

vector<vector<int>> mem(n, vector<int>(27));

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

// min cost to type word[i:n]. o is the last position of the other finger.

// the current finger is at word[i - 1].

function<int(int, int)> dp = [&](int i, int o) {

if (i == n) return 0;

if (mem[i][o]) return mem[i][o];

int p = i == 0 ? kRest : word[i - 1] - 'A';

int c = word[i] - 'A';

return mem[i][o] = min(dp(i + 1, o) + cost(p, c), // same finger

dp(i + 1, p) + cost(o, c)); // other finger

};

return dp(0, kRest);

}

};

C++

// Author: Huahua, 8 ms, 10.1 MB

class Solution {

public:

int minimumDistance(string word) {

constexpr int kRest = 26;

const int n = word.length();

// dp[i][j] : min cost to type word[0:i]

// one finger is at word[i - 1], another finger is at j.

vector<vector<int>> dp(n + 1, vector<int>(27, INT_MAX / 2));

dp[0][kRest] = 0;

auto cost = [](int c1, int c2) {

if (c1 == kRest) return 0;

return abs(c1 / 6 - c2 / 6) + abs(c1 % 6 - c2 % 6);

};

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

int p = i == 0 ? kRest : word[i - 1] - 'A';

int c = word[i] - 'A';

for (int j = 0; j <= 26; ++j) {

dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost(p, c)); // same finger

dp[i + 1][p] = min(dp[i + 1][p], dp[i][j] + cost(j, c)); // other finger

}

return *min_element(begin(dp[n]), end(dp[n]));

}

};

Huahua's Tech Road

花花酱 LeetCode 1326. Minimum Number of Taps to Open to Water a Garden

Solution 1: Greedy

C++

Solution 2: Greedy

C++

花花酱 LeetCode 42. Trapping Rain Water

Solution 1: Brute Force

C++

Solution 2: DP

C++

Solution 3: Two Pointers

C++

花花酱 LeetCode 1318. Minimum Flips to Make a OR b Equal to c

Solution: Bit operation

C++

花花酱 LeetCode 1317. Convert Integer to the Sum of Two No-Zero Integers

Solution: Brute Force

C++

花花酱 LeetCode 1320. Minimum Distance to Type a Word Using Two Fingers

Solution: DP

C++

C++

C++