Posts published in “Greedy”

花花酱 LeetCode 853. Car Fleet

By zxi on April 28, 2019

N cars are going to the same destination along a one lane road. The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored – they are assumed to have the same position.

A car fleet is some non-empty set of cars driving at the same position and same speed. Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

0 <= N <= 10 ^ 4
0 < target <= 10 ^ 6
0 < speed[i] <= 10 ^ 6
0 <= position[i] < target
All initial positions are different.

Solution: Greedy

Compute the time when each car can reach target.
Sort cars by position DESC

Answer will be number slow cars in the time array.

Ex 1: 
target = 12
p = [10,8,0,5,3] 
v = [2,4,1,1,3]


p     t
10    1  <- slow -- ^
 8    1             |
 5    7  <- slow -- ^
 3    3             |
 0   12  <- slow -- ^

Ex 2
target = 10
p = [5, 4, 3, 2, 1]
v = [1, 2, 3, 4, 5]

p     t
5     5  <- slow -- ^
4     3             |
3     2.33          |
2     2             |
1     1.8           |

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

C++

// Author: Huahua, running time: 52 ms / 10.9 MB

class Solution {

public:

int carFleet(int target, vector<int>& position, vector<int>& speed) {

vector<pair<int, float>> cars(position.size());

for (int i = 0; i < position.size(); ++i)

cars[i] = {position[i], static_cast<float>(target - position[i]) / speed[i]};

sort(rbegin(cars), rend(cars));

int ans{0};

float max_t{0};

for (const auto& [p, t] : cars)

if (t > max_t) {

max_t = t;

++ans;

}

return ans;

}

};

Python3

class Solution:

def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:

cars = sorted([(p, (target - p) / s) for p, s in zip(position, speed)],

key=lambda x: -x[0])

ans, max_t = 0, 0

for p, t in cars:

if t > max_t:

ans += 1

max_t = t

return ans

花花酱 LeetCode 45. Jump Game II

By zxi on April 28, 2019

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
    Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

Solution: Greedy

Jump as far as possible but lazily.

[2, 3, 1, 1, 4]
i    nums[i]   steps   near   far
-      -         0       0     0
0      2         0       0     2
1      3         1       2     4
2      1         1       2     4
3      1         2       4     4
4      4         2       4     8

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

C++

// Author: Huahua, running time: 12 ms / 10.3 MB

class Solution {

public:

int jump(vector<int>& nums) {

int steps = 0;

int near = 0;

int far = 0;

for (int i = 0; i < nums.size(); ++i) {

if (i > near) {

++steps;

near = far;

}

far = max(far, i + nums[i]);

}

return steps;

}

};

花花酱 LeetCode 1005. Maximize Sum Of Array After K Negations

By zxi on March 9, 2019

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].

Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

Solution: Sorting

Flip as many as negative numbers as possible, if K > # of negative numbers and K is odd, flip the smallest element in the array.

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

C++

// Author: Huahua 8 ms 8.6MB

class Solution {

public:

int largestSumAfterKNegations(vector<int>& A, int K) {

std::sort(begin(A), end(A));

for (int& a : A) {

if (!K) break;

if (a < 0) {

a = -a;

--K;

}

return accumulate(begin(A), end(A), 0) - (K % 2 ? *min_element(begin(A), end(A)) * 2 : 0);

}

};

花花酱 LeetCode 995. Minimum Number of K Consecutive Bit Flips

By zxi on February 17, 2019

In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.

Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

Example 1:

Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].

Example 2:

Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].

Example 3:

Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

Note:

1 <= A.length <= 30000
1 <= K <= A.length

Solution: Greedy

From left most, if there is a 0, that bit must be flipped since the right ones won’t affect left ones.

Time complexity: O(nk) -> O(k)
Space complexity: O(1)

C++ / O(nk)

// Author: Huahua, running time: 5172 ms, 16.4 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

int ans = 0;

for (int i = 0; i <= A.size() - K; ++i) {

if (A[i] == 1) continue;

++ans;

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

A[i + j] ^= 1;

}

for (int i = A.size() - K + 1; i < A.size(); ++i)

if (A[i] == 0) return -1;

return ans;

}

};

C++ / O(n)

// Author: Huahua, running time: 100 ms, 19.6 MB

class Solution {

public:

int minKBitFlips(vector<int>& A, int K) {

vector<int> flipped(A.size());

int ans = 0;

int flip = 0;

for (int i = 0; i < A.size(); ++i) {

if (i >= K) flip ^= flipped[i - K];

if ((A[i] ^ flip) == 0) {

if (i + K > A.size()) return -1;

++ans;

flip ^= 1;

flipped[i] = 1;

}

return ans;

}

};

花花酱 LeetCode 991. Broken Calculator

By zxi on February 10, 2019

On a broken calculator that has a number showing on its display, we can perform two operations:

Double: Multiply the number on the display by 2, or;
Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

1 <= X <= 10^9
1 <= Y <= 10^9

Solution: Greedy

Thinking backwards, making Y <= X by adding 1 or dividing 2.

If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd

Time complexity: O(log(Y-X))
Space complexity: O(1)

C++

// Author: Huahua, running time: 4 ms, 4.7 MB

class Solution {

public:

int brokenCalc(int X, int Y) {

if (X <= Y) return X - Y;

return 1 + brokenCalc(X, Y % 2 ? Y + 1 : Y / 2);

}

};