Greedy
Greedy for Beginners https://leetcode.com/discuss/general-discussion/669996/greedy-for-beginners-problems-sample-solutions
Add all slope of between the peeks and valleys when the second number is larger than the first one.
T: O(n) S: O(1)
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] - prices[i - 1] >= 0) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}// Peak/Valley solution
int maxProfit(vector<int>& prices) {
int peak = prices[0], valley = prices[0];
int i = 0;
int sum = 0;
while (i < prices.size() - 1) {
while (i < prices.size() - 1 && prices[i] >= prices[i + 1]) i++;
valley = prices[i];
while (i < prices.size() - 1 && prices[i] <= prices[i + 1]) i++;
peak = prices[i];
sum += peak - valley;
}
return sum;
}Maintain the farest point it can jump, if i is larger than farest it means it is not possible to jump to i.
T: O(n) S: O(1)
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) return true;
int farest = 0;
for (int i = 0; i < nums.length; i++) {
if (i > farest) return false;
farest = Math.max(farest, i + nums[i]);
}
return true;
}Initiate the maximum position that one could reach starting from the current index i or before: max_pos = nums[0]. Initiate number of steps: at least one, if array has more than 1 cell.
Iterate over number of elements in the input array:
If max_step < i, one needs one more jump:
jumps += 1. To minimize the number of jumps, choose the longest possible one: max_steps = max_pos.Update
max_pos = max(max_pos, i + nums[i]).
public int jump(int[] nums) {
if (nums.length < 2) return 0;
int maxPos = nums[0], maxSteps = nums[0];
int step = 1;
for (int i = 1; i < nums.length; i++) {
if (maxSteps < i) {
step++;
maxSteps = maxPos;
}
maxPos = Math.max(maxPos, i + nums[i]);
}
return step;
}"The algorithm is pretty easy to understand. Imagine we take a tour around this circle, the only condition that we can complete this trip is to have more fuel provided than costed in total. That's what the first loop does.
If we do have more fuel provided than costed, that means we can always find a start point around this circle that we could complete the journey with an empty tank. Hence, we check from the beginning of the array, if we can gain more fuel at the current station, we will maintain the start point, else, which means we will burn out of oil before reaching to the next station, we will start over at the next station." @pigwall
T: O(n) S: O(1)
public int canCompleteCircuit(int[] gas, int[] cost) {
int total = 0;
int n = gas.length;
for (int i = 0; i < n; i++) {
total += gas[i] - cost[i];
}
if (total < 0) return -1;
int startpos = 0, accumulate = 0;
for (int i = 0; i < n; i++) {
accumulate += gas[i] - cost[i];
if (accumulate < 0) {
accumulate = 0;
startpos = i + 1;
}
}
return startpos;
}Record all last indicies of each character. Consider the first label, say it's 'a'. The first partition must include the last occurrence of 'a'. However, before the last 'a' there might be a different label makes the partition bigger. For example, in "abccaddbeffe", the minimum first partition is "abccaddb". This gives us the idea for the algorithm: For each letter encountered, process the last occurrence of that letter, extending the current partition [anchor, j] appropriately.
public List<Integer> partitionLabels(String S) {
int[] last = new int[26];
for (int i = 0; i < S.length(); i++) {
last[S.charAt(i) - 'a'] = i;
}
List<Integer> res = new ArrayList<>();
int j = 0, anchor = 0;
for (int i = 0; i < S.length(); i++) {
j = Math.max(j, last[S.charAt(i) - 'a']);
if (i == j) {
res.add(i - anchor + 1);
anchor = i + 1;
}
}
return res;
}Narrow down the answer by guessing the score and update the list to ONLY keep the ones that have exact x matches with word. In this way, we narrow the candidates after we call master.guess(), and guarantee that secret is in candidates left. Full explanation.
T: O(n^2)
public void findSecretWord(String[] wordlist, Master master) {
Arrays.sort(wordlist);
List<String> list = new ArrayList<>(Arrays.asList(wordlist));
int score = -1;
for (int i = 0; i < 10; i++) {
score = master.guess(list.get(0));
if (score == 6) return;
list = updateList(list, list.get(0), score);
}
}
private List<String> updateList(List<String> list, String target, int score) {
List<String> res = new ArrayList<>();
for (String s : list) {
if (getSimilarityScore(s, target) == score) {
res.add(s);
}
}
return res;
}
private int getSimilarityScore(String s, String target) {
int count = 0;
for (int i = 0; i < Math.min(s.length(), target.length()); i++) {
if (s.charAt(i) == target.charAt(i)) count++;
}
return count;
}public String removeDuplicateLetters(String s) {
if (s.length() == 0) {
return "";
}
int[] count = new int[26];
for (char c : s.toCharArray()) {
count[c - 'a']++;
}
int pos = 0; // position of the smallest lex character
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) < s.charAt(pos)) {
pos = i;
}
if (--count[s.charAt(i) - 'a'] == 0) {
break;
}
}
char ch = s.charAt(pos);
String remaining = s.substring(pos + 1).replaceAll(String.valueOf(ch), "");
return ch + removeDuplicateLetters(remaining);
}int twoCitySchedCost(vector<vector<int>>& costs) {
vector<int> refund;
int N = costs.size()/2;
int minCost = 0;
for(vector<int> cost : costs){
minCost += cost[0];
refund.push_back(cost[1] - cost[0]);
}
sort(refund.begin(), refund.end());
for(int i = 0; i < N; i++){
minCost += refund[i];
}
return minCost;
}1419. Minimum Number of Frogs Croaking
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int[] count = new int[5]; // c, r, o, a, k
int frogs = 0;
int maxFrogs = 0;
for (char ch : croakOfFrogs.toCharArray()) {
if (ch == 'c') {
count[0]++;
frogs++;
maxFrogs = Math.max(maxFrogs, frogs);
} else if (ch == 'r') {
if (count[0] == 0) return -1;
count[0]--;
count[1]++;
} else if (ch == 'o') {
if (count[1] == 0) return -1;
count[1]--;
count[2]++;
} else if (ch == 'a') {
if (count[2] == 0) return -1;
count[2]--;
count[3]++;
} else if (ch == 'k') {
if (count[3] == 0) return -1;
count[3]--;
frogs--;
} else {
return -1; // invalid char
}
}
// All counts except 'k' should be zero at the end
if (frogs == 0) {
return maxFrogs;
} else {
return -1; // incomplete croak
}
}
}
Last updated
Was this helpful?