Greedy Others¶
Table of Contents¶
- 2740. Find the Value of the Partition (Medium)
- 1033. Moving Stones Until Consecutive (Medium)
- 1864. Minimum Number of Swaps to Make the Binary String Alternating (Medium)
- 1899. Merge Triplets to Form Target Triplet (Medium)
- 2498. Frog Jump II (Medium)
- 134. Gas Station (Medium)
- 2311. Longest Binary Subsequence Less Than or Equal to K (Medium)
- 3443. Maximum Manhattan Distance After K Changes (Medium)
- 3002. Maximum Size of a Set After Removals (Medium)
- 2412. Minimum Money Required Before Transactions (Hard)
- 659. Split Array into Consecutive Subsequences (Medium)
- 2732. Find a Good Subset of the Matrix (Hard)
- 2790. Maximum Number of Groups With Increasing Length (Hard)
- 782. Transform to Chessboard (Hard)
- 420. Strong Password Checker (Hard)
- 2753. Count Houses in a Circular Street II (Hard) 👑
2740. Find the Value of the Partition¶
1033. Moving Stones Until Consecutive¶
1864. Minimum Number of Swaps to Make the Binary String Alternating¶
1899. Merge Triplets to Form Target Triplet¶
from typing import List
def mergeTriplets(triplets: List[List[int]], target: List[int]) -> bool:
can_form = [False, False, False]
for triplet in triplets:
if all(triplet[i] <= target[i] for i in range(3)):
for i in range(3):
if triplet[i] == target[i]:
can_form[i] = True
return all(can_form)
triplets = [[2, 5, 3], [1, 8, 4], [1, 7, 5]]
target = [2, 7, 5]
print(mergeTriplets(triplets, target)) # True
2498. Frog Jump II¶
134. Gas Station¶
from typing import List
# Greedy
def canCompleteCircuit(gas: List[int], cost: List[int]) -> int:
curSum = 0
totalSum = 0
start = 0
for i in range(len(gas)):
curSum += gas[i] - cost[i]
totalSum += gas[i] - cost[i]
if curSum < 0:
start = i + 1
curSum = 0
if totalSum < 0:
return -1
return start
gas = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
print(canCompleteCircuit(gas, cost)) # 3
#include <cassert>
#include <vector>
using namespace std;
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int totalTank = 0, currTank = 0;
int start = 0;
int n = gas.size();
for (int i = 0; i < n; i++) {
int diff = gas[i] - cost[i];
totalTank += diff;
currTank += diff;
if (currTank < 0) {
start = i + 1;
currTank = 0;
}
}
return (totalTank >= 0) ? start : -1;
}
};
int main() {
Solution obj;
vector<int> gas{1, 2, 3, 4, 5};
vector<int> cost{3, 4, 5, 1, 2};
int res = obj.canCompleteCircuit(gas, cost);
assert(res == 3);
return 0;
}