Leetcode question brushing (IV) -- greedy thought (go Implementation)

leetcode Question brushing and sorting series

leetcode Brush problem ( One ) — Two pointer thought
leetcode Brush problem ( Two ) — Sequencing ideas
leetcode Brush problem ( 3、 ... and ) — Dichotomous thinking
leetcode Brush problem ( Four ) — Greedy thoughts

 

leetcode Brush question type （ Four ）--- Greedy thoughts

Ensure that every operation is locally optimal , And the final result is globally optimal .

455 Distribute cookies

   Suppose you are a great parent , Want to give your kids some cookies . however , Each child can only give one biscuit at most .
   For every child i, All have an appetite value g[i], This is the smallest size of biscuit that can satisfy children's appetite ; And every cookie j, They all come in one size s[j] . If s[j] >= g[i], We can put this biscuit j Assign to children i , The child will be satisfied . Your goal is to meet as many children as possible , And output the maximum value .

Ideas ：

• Biscuits given to a child should be as small as possible and satisfy the child , In this way, big biscuits can be given to children who are more satisfied .
• Because the child with the least satisfaction is the easiest to be satisfied , So first satisfy the child with the least satisfaction .

func findContentChildren(g []int, s []int) int {
    
	if len(s)==0{
    
		return 0    // No cookies , No one can be satisfied 
	}
	sort.Ints(g)  // Sort in place first 
	sort.Ints(s)  // Sort in place first 
	i:=0
	j:=0
	for i<len(g) && j<len(s){
    
		if g[i] <= s[j] {
       // The first i A child is satisfied , Only the first one i A child is satisfied , Will try to meet the i+1 individual 
			i++
		}
		j++
	}
	return i
}

 

435 No overlap

   Given a set of intervals , Find the minimum number of intervals to remove , Keep the remaining intervals from overlapping .
Be careful :

• It can be said that the end of an interval is always greater than its starting point .
• Section [1,2] and [2,3] The boundaries of each other “ Contact ”, But there is no overlap .

Ideas ：

1. Find the minimum number of removed intervals , That means you need to keep as many intervals as possible ;
2. The smaller the range of each interval , The more intervals you need to leave ;
3. The beginning of the interval has been fixed by the previous interval , So the decision range is The end of the interval , The end of the interval is about small , The more intervals you need ;
4. So you can sort by the end of the interval , The end of each selection is the smallest , An interval that does not overlap the previous interval .

func eraseOverlapIntervals(intervals [][]int) int {
    
	if len(intervals) == 0 {
    
		return 0
	}
	sort.Slice(intervals, func(i, j int) bool {
     // Sort according to the end of the interval 
		return intervals[i][1] < intervals[j][1]
	})
	end := intervals[0][1] // The end of the first interval , That is, the second column of the first element after sorting 
	count := 1             //count Record the number of intervals reserved , The first interval is intervals[0]

	for i := 1; i < len(intervals); i++ {
     //i=0 Is the first interval ,count Has been counted 
		if intervals[i][0] < end {
     // The beginning of the next interval is less than the end of the interval , There's overlap 
			continue
		}
		end = intervals[i][1] // The beginning of the next interval is after the end of the interval , There's no overlap , Start from the end of the next interval and look back 
		count++
	}
	return len(intervals) - count
}

 

452 Detonate the balloon with a minimum number of arrows

   A bow and arrow can follow x The axis shoots out completely perpendicular from different points . In coordinates x Shoot an arrow at , If there is a balloon with a diameter starting and ending coordinates of xstart,xend, And meet xstart ≤ x ≤ xend, Then the balloon will explode . There is no limit to the number of bows and arrows that can be shot . Once the bow is shot , Can move forward indefinitely . We want to find out how to make all the balloons explode , The minimum number of bows required .
   Give you an array points , among points [i] = [xstart,xend] , Return to the minimum number of bows and arrows that must be fired to detonate all balloons .

Ideas ：
   Along the x Move the arrow axially to the right , Make the balloon that was detonated before moving still be detonated , Then we will shoot fewer arrows , That is, the shooting position of each arrow exactly corresponds to the right boundary of a balloon .

   Consider the one with the leftmost right boundary of all balloons , Then there must be an arrow whose shooting position is its right boundary （ Otherwise, no arrow can detonate it ）. When we identify an arrow , We can remove all the balloons detonated by this arrow , And from the remaining unexploded balloons , And then select the one on the left of the right boundary , Determine the next arrow , Until all the balloons were blown up .

   This is the question 435 Calculate the number of non overlapping intervals Deformation of , but [1, 2] and [2, 3] It's an overlapping interval , At this point, the arrow arrives x=2 when , Both balloons will explode

func findMinArrowShots(points [][]int) int {
    
	if len(points) == 0 {
    
		return 0
	}
	sort.Slice(points, func(i, j int) bool {
    
		return points[i][1] < points[j][1]
	})

	maxRight := points[0][1] // Of all balloons, the one whose right boundary is farthest to the left , An arrow must have hit its right border 
	count := 1               // The first arrow hit maxRight Location 

	//points[i][0]（ Left coordinate ） be equal to maxRight when , Be shot at maxRight The arrow of 
	// After ordering points[i][0]（ Left coordinate ） Less than maxRight when ,points[i][1] （ Right coordinate ） Greater than maxRight, Also shot at maxRight The arrow of 
	for i := 1; i < len(points); i++ {
    
		if points[i][0] > maxRight {
    
			maxRight = points[i][1]
			count++
		}
	}
	return count
}

 

121 The best time to buy and sell stocks

   Given an array prices , It's the first i Elements prices[i] Represents the number of shares in a given stock i Sky price .
   You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .
   Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

Ideas ：
   Just record the previous minimum price , Take this minimum price as the buying price , Then take the current price as the selling price , Check whether the current revenue is the maximum revenue .

func maxProfit(prices []int) int {
    
	if len(prices) == 0 {
    
		return 0
	}
	minPrice := prices[0] // Buying price （ The lowest price ）
	profit := 0
	for i := 1; i < len(prices); i++ {
    
		if prices[i] < minPrice {
     // If prices[i] It's cheaper , Then change it to i Buy when 
			minPrice = prices[i]
		} else {
    
			nowProfit := prices[i] - minPrice // You can sell at this time , The proceeds from the sale are prices[i]-minPrice
			if nowProfit > profit {
    
				profit = nowProfit // If you sell more at this time , Then change it to i Time to sell 
			}
		}
	}
	return profit
}

122 The best time to buy and sell stocks II

   about [a, b, c, d], If there is a <= b <= c <= d , Then the maximum benefit is d - a. and d - a = (d - c) + (c - b) + (b - a) , So when you visit a prices[i] And prices[i] - prices[i-1] > 0, Then put prices[i] - prices[i-1] Add to revenue .

   That is, once you can make money, you can buy , Once you lose money, sell , Don't sell as long as you don't lose money the next day .

func maxProfit(prices []int) int {
    
	if len(prices) == 0 {
    
		return 0
	}
	profit := 0
	for i := 1; i < len(prices); i++ {
    
		if prices[i]-prices[i-1] > 0 {
       
			profit = profit + prices[i] - prices[i-1]
		}
	}
	return profit
}

 
 
If there is any wrong , Please point out , thank ~
 
Reference from ：
http://www.cyc2018.xyz/
https://leetcode-cn.com/problems