This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

preface

Some simple examples of greedy algorithms: Leetcode 455, 860, 55, 45, 435, 452, 56

Leetcode 455 gives out cookies

Leetcode portal

This problem just needs to know that the minimum number of cookies to be sent is the minimum number of cookies that the child needs, and if the cookie doesn’t satisfy the mixer, then the cookie is really useless. So this is a very simple two-pointer problem for greedy algorithms. The first time may also need to think for a long time, the core of the breaking point found, is the second to kill.

var findContentChildren = function(g, s) { if(s.length===0){return 0} g.sort((a,b)=>a-b) s.sort((a,b)=>a-b) let min = Math.min(g.length,s.length) let i=0,j=0;  while(i<s.length&&j<min){ if(g[j]<=s[i]){ i++ j++ continue } i++ } return j };Copy the code

Leetcode 860. Lemonade change

Leetcode portal

A super simple change problem, usually how to write the code here how to write. And then you combine the same if else judgment, and you get the answer. Not exactly. If you try to figure out what the optimal solution is, you’re probably going to suffer.

var lemonadeChange = function(bills) {
    let five = 0
    let ten = 0
    for(item of bills){
        if(item===5){
            five+=1
        }else if(item===10){
            ten++
            five--
        }else if(ten>0){
            ten--
            five--
        }else{
            five-=3
        }
        if(five<0){
            return false
        }
    }
    return true
};
Copy the code

Leetcode 55 Jumping Games I

Leetcode portal

This problem is a prelude to 45, and it’s really hard to understand if you don’t understand 55 here.

To simplify things a little bit, keep going, keep updating the maximum value, the maximum value is greater than the last index, so return true.

var canJump = function(nums) { let max = 0 let l = nums.length for(let i=0; i<l; i++){ if(i<=max){ max = Math.max(max,i+nums[i]) if(max>=l-1){ return true } } } return false };Copy the code

Leetcode 45 Jumping Games II

Leetcode portal

An advanced version of problem 55. The core break point is how far the current index can go and how many steps it takes.

Specific code implementation points

  • Figure out how far you can go with each step (see question 55)
  • Figure out when count++ and what the whole process is
  • Figure out why only the second-to-last piece is ok, because this position is the maxPosition that is actually needed for the time being. True maxPosition is a bit larger out of bounds. This is actually optimizing redundant judgments.

This problem is still very difficult to think of, the entrance is narrow, greedy algorithm breakthrough has two layers, for beginners is also a more difficult topic, it is recommended to encounter such a topic do not think, first to ensure that their thinking is correct, such thinking is meaningful, the cost performance of time and energy will be higher.

Var jump = function(nums) {let count =0 let l = nums.length let end =0 let maxPosition =0 i<l-1; i++){ maxPosition= Math.max(maxPosition,i+nums[i]) if(i===end){ end = maxPosition count++ } } return count };Copy the code

Leetcode 56 merge interval

Leetcode portal

Merging intervals, the breaking point is sorted by the interval left value from the smallest to the largest

  • Push if the minimum value of the current range is greater than the maximum value of the RES array
  • If the minimum value of the current range is smaller than the maximum value of the RES array, it needs to be merged. If it is fully included, it is left alone.

If it is very confusing according to other ideas, here is essentially a code optimization discussion of whether there is an intersection of two sections, violence can also be done, the idea is similar, greedy algorithm code is a little more concise.

var merge = function(intervals) { intervals.sort((a,b)=>a[0]-b[0]) let res = [intervals[0]] for(let i=1; i<intervals.length; i++){ let temp = res[res.length-1][1] if(intervals[i][0]>temp){ res.push(intervals[i]) }else{ if(intervals[i][1]>temp){ res[res.length-1] = [res[res.length-1][0],intervals[i][1]] } } } return res };Copy the code

Leetcode 435 non-overlapping intervals

Leetcode portal

The breaking point here is sorting by the right boundary of the interval. So once you figure that out, the overlap interval is pretty easy to solve.

var eraseOverlapIntervals = function(intervals) { if (! intervals.length) { return 0; } intervals.sort((a, b) => a[1] - b[1]); const n = intervals.length; let right = intervals[0][1]; let ans = 1; for (let i = 1; i < n; ++i) { if (intervals[i][0] >= right) { ++ans; right = intervals[i][1]; } } return n - ans; };Copy the code

Leetcode 452 detonates the balloon with the minimum number of arrows

Leetcode portal

This is exactly the same break point as the last problem

var findMinArrowShots = function(points) { if (! points.length ) { return 0; } points.sort((a, b) => a[1] - b[1]); let pos = points[0][1] let ans = 1; for (let balloon of points) { if (balloon[0] > pos) { pos = balloon[1]; ans++; } } return ans; };Copy the code

summary

Although I have done everything, but the depth of the feeling is a little worse, and I do not know how to improve temporarily. First master the greedy algorithm only brush once, may be easy to forget, most ideas if it is the first time to meet, or too clever, worth brushing several times. The thinking behind the brush should be well summarized, why do you cut into it? At present, the number of brush questions did not rise, afraid of fitting, or play slowly and steadily.