Posts published in “Greedy”

花花酱 LeetCode 1323. Maximum 69 Number

By zxi on January 20, 2020

Given a positive integer num consisting only of digits 6 and 9.

Return the maximum number you can get by changing at most one digit (6 becomes 9, and 9 becomes 6).

Example 1:

Input: num = 9669
Output: 9969
Explanation: 
Changing the first digit results in 6669.
Changing the second digit results in 9969.
Changing the third digit results in 9699.
Changing the fourth digit results in 9666. 
The maximum number is 9969.

Example 2:

Input: num = 9996
Output: 9999
Explanation: Changing the last digit 6 to 9 results in the maximum number.

Example 3:

Input: num = 9999
Output: 9999
Explanation: It is better not to apply any change.

Constraints:

1 <= num <= 10^4
num‘s digits are 6 or 9.

Solution: Greedy

Replace the highest 6 to 9, if no 6, return the original number.

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

C++

// Author: Huahua

class Solution {

public:

int maximum69Number (int num) {

string s = to_string(num);

for (int i = 0; i < s.length(); ++i) {

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

s[i] = '9';

return stoi(s);

}

return num;

}

};

花花酱 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 1296. Divide Array in Sets of K Consecutive Numbers

By zxi on December 26, 2019

Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into sets of k consecutive numbers
Return True if its possibleotherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

Example 2:

Input: nums = [3,2,1,2,3,4,3,4,5,9,10,11], k = 3
Output: true
Explanation: Array can be divided into [1,2,3] , [2,3,4] , [3,4,5] and [9,10,11].

Example 3:

Input: nums = [3,3,2,2,1,1], k = 3
Output: true

Example 4:

Input: nums = [1,2,3,4], k = 3
Output: false
Explanation: Each array should be divided in subarrays of size 3.

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= k <= nums.length

Solution: BST + Greedy

Start from the smallest available number and find k consecutive numbers.

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

C++

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

const int s = m.cbegin()->first;

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

auto it = m.find(s + i);

if (it == m.cend()) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

C++/V2

// Author: Huahua

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

map<int, int> m;

for (int num : nums) ++m[num];

while (m.size()) {

auto it = m.begin();

const int s = it->first;

for (int i = 0; i < k; ++i, ++it) {

if (it->first != s + i) return false;

if (--it->second == 0) m.erase(it);

}

return true;

}

};

Solution 2: HashTable

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

C++

class Solution {

public:

bool isPossibleDivide(vector<int>& nums, int k) {

if (nums.size() % k) return false;

unordered_map<int, int> m;

for (int num : nums) ++m[num];

queue<int> starts;

for (auto [n, f] : m)

if (!m.count(n - 1)) starts.push(n);

while (!starts.empty()) {

int s = starts.front();

starts.pop();

for (int t = s + k - 1; t >= s; t--) {

if (m[t] < m[s]) return false;

if ((m[t] -= m[s]) == 0) {

m.erase(t);

if (m.count(t + 1)) starts.push(t + 1);

}

return true;

}

};

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

By zxi on November 9, 2019

Given the following details of a matrix with n columns and 2 rows :

The matrix is a binary matrix, which means each element in the matrix can be 0 or 1.
The sum of elements of the 0-th(upper) row is given as upper.
The sum of elements of the 1-st(lower) row is given as lower.
The sum of elements in the i-th column(0-indexed) is colsum[i], where colsum is given as an integer array with length n.

Your task is to reconstruct the matrix with upper, lower and colsum.

Return it as a 2-D integer array.

If there are more than one valid solution, any of them will be accepted.

If no valid solution exists, return an empty 2-D array.

Example 1:

Input: upper = 2, lower = 1, colsum = [1,1,1]
Output: [[1,1,0],[0,0,1]]
Explanation: [[1,0,1],[0,1,0]], and [[0,1,1],[1,0,0]] are also correct answers.

Example 2:

Input: upper = 2, lower = 3, colsum = [2,2,1,1]
Output: []

Example 3:

Input: upper = 5, lower = 5, colsum = [2,1,2,0,1,0,1,2,0,1]
Output: [[1,1,1,0,1,0,0,1,0,0],[1,0,1,0,0,0,1,1,0,1]]

Constraints:

1 <= colsum.length <= 10^5
0 <= upper, lower <= colsum.length
0 <= colsum[i] <= 2

Solution: Greedy?

Two passes:
first pass, only process sum = 2, upper = 1, lower = 1
second pass, only process sum = 1, whoever has more leftover, assign 1 to that row.

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

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> reconstructMatrix(int upper, int lower, vector<int>& colsum) {

const int n = colsum.size();

vector<vector<int>> a(2, vector<int>(n));

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

if (colsum[i] == 2) {

a[0][i] = a[1][i] = 1;

--upper;

--lower;

}

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

if (colsum[i] == 1)

if (upper > lower) {

a[0][i] = 1;

--upper;

} else {

a[1][i] = 1;

--lower;

}

if (upper != 0 || lower != 0) return {};

return a;

}

};

花花酱 LeetCode 1221. Split a String in Balanced Strings

By zxi on October 13, 2019

Balanced strings are those who have equal quantity of ‘L’ and ‘R’ characters.

Given a balanced string s split it in the maximum amount of balanced strings.

Return the maximum amount of splitted balanced strings.

Example 1:

Input: s = "RLRRLLRLRL"
Output: 4
Explanation: s can be split into "RL", "RRLL", "RL", "RL", each substring contains same number of 'L' and 'R'.

Example 2:

Input: s = "RLLLLRRRLR"
Output: 3
Explanation: s can be split into "RL", "LLLRRR", "LR", each substring contains same number of 'L' and 'R'.

Example 3:

Input: s = "LLLLRRRR"
Output: 1
Explanation: s can be split into "LLLLRRRR".

Constraints:

1 <= s.length <= 1000
s[i] = 'L' or 'R'

Solution: Greedy

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

C++

// Author: Huahua

class Solution {

public:

int balancedStringSplit(string s) {

int b = 0;

int ans = 0;

for (char c : s) {

b += c == 'L' ? 1 : -1;

if (b == 0) ++ans;

}

return ans;

}

};

Posts published in “Greedy”

花花酱 LeetCode 1323. Maximum 69 Number

Solution: Greedy

C++

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

Solution 1: Greedy

C++

Solution 2: Greedy

C++

花花酱 LeetCode 1296. Divide Array in Sets of K Consecutive Numbers

Solution: BST + Greedy

C++

C++/V2

Solution 2: HashTable

C++

Related Problems

花花酱 LeetCode 1253. Reconstruct a 2-Row Binary Matrix

Solution: Greedy?

C++

花花酱 LeetCode 1221. Split a String in Balanced Strings

Solution: Greedy

C++