Article directory
- 860. Change for Lemonade
-
- train of thought
- idea code
- 406. Rebuild the queue based on height
-
- train of thought
- idea code
- official solution
- the code
- difficulty
- 452. Detonate a balloon with the fewest number of arrows
-
- train of thought
- idea code
- official solution
- the code
- difficulty
- Harvest today
860. Change for lemonade
860. Change for Lemonade
Thoughts
Therefore, the local optimum: When encountering a bill of 20, spend 10 dollars first, and complete this change. Global Optimal: Complete the change of all bills.
idea code
func lemonadeChange(bills []int) bool {<!-- -->
cash:=[2]int{<!-- -->}
for _,n:=range bills{<!-- -->
if n==5{<!-- -->
cash[0]++
}else if n==10{<!-- -->
cash[0]--
cash[1] + +
}else{<!-- -->
if cash[1]>0{<!-- -->
cash[1]--
cash[0]--
}else{<!-- -->
cash[0]-=3
}
}
if cash[0]<0{<!-- -->
return false
}
}
return true
}
406. Rebuild the queue based on height
406. Rebuild the queue based on height
Thoughts
two greedy
1. The local optimal height is from high to low and the same height meets the requirements
2. Local optimum: priority is inserted according to the k of the tallest people. The people after the insert operation satisfies the queue property
Global optimal: insert operations are completed at the end, and the entire queue satisfies the property of the title queue
idea code
func reconstructQueue(people [][]int) [][]int {<!-- -->
sort.Slice(people, func(i, j int) bool {<!-- -->
if people[i][0] == people[j][0] {<!-- -->
return people[i][1] < people[j][1]
}
return people[i][0] > people[j][0]
})
res :=[][]int{<!-- -->}
for _,n:=range people{<!-- -->
if len(res)==0{<!-- -->
res=append(res,n)
continue
}
count:=n[1]
for i2,n2:=range res{<!-- -->
if n2[0]>=n[0]{<!-- -->
count--
}
if count<0{<!-- -->
res=append(res,[]int{<!-- -->})
copy(res[i2 + 1:],res[i2:])
res[i2]=n
break
}
if count==0{<!-- -->
if i2==len(res){<!-- -->
res=append(res,n)
}else{<!-- -->
res=append(res,[]int{<!-- -->})
copy(res[i2 + 2:],res[i2 + 1:])
res[i2 + 1]=n
}
break
}
}
}
return res
}
Official solution
optimized insertion
Code
func reconstructQueue(people [][]int) [][]int {<!-- -->
// First sort the heights from large to small to determine the relative position of the largest person
sort.Slice(people, func(i, j int) bool {<!-- -->
if people[i][0] == people[j][0] {<!-- -->
return people[i][1] < people[j][1] // When the heights are the same, sort K from small to large
}
return people[i][0] > people[j][0] // the heights are arranged in descending order
})
// Then perform insertion sort according to K, and insert the ones with small K first
for i, p := range people {<!-- -->
copy(people[p[1] + 1 : i + 1], people[p[1] : i + 1]) // free a place
people[p[1]] = p
}
return people
}
Difficult
This question has two dimensions, h and k. When you see this kind of question, you must think about how to determine one dimension, and then rearrange according to another dimension.
In fact, if you do 135. Distributing candy (opens new window) carefully, you will find that it is a bit similar to this question.
In 135. Distributing candy (opens new window), I emphasized once that when encountering a trade-off between two dimensions, one must first determine one dimension, and then determine the other.
If the two dimensions are considered together, one will lose sight of the other.
For this question, I believe everyone is confused whether to determine k or h first, that is, whether to sort by h or k first?
If you sort from small to large according to k, after sorting, you will find that the arrangement of k does not meet the conditions, and the height does not meet the conditions, and neither of the two dimensions has been determined.
Then sort by the height h, the height must be arranged from large to small (if the height is the same, the small k stands in front), so that the tall ones are in the front.
At this point, we can determine a dimension, which is height, and the previous nodes must be taller than this node!
Then you only need to reinsert the queue according to k as the subscript.
452. Detonate the balloon with the least number of arrows
452. Explode a balloon with the fewest number of arrows
Thoughts
Note that the balloons are sorted first
Local optima, shoot only from overlapping parts
idea code
func findMinArrowShots(points [][]int) int {<!-- -->
cross:=[][]int{<!-- -->}
sort.Slice(points, func (i,j int) bool {<!-- -->
return points[i][0] < points[j][0]
})
for _,ballon:=range points{<!-- -->
if len(cross)==0{<!-- -->
cross=append(cross,ballon)
}
notcross:=true
for _,xy:=range cross{<!-- -->
if ballon[0]<=xy[1] & amp; & amp;ballon[1]>=xy[0]{<!-- -->
xy[1]=min(ballon[1],xy[1])
xy[0]=max(ballon[0],xy[0])
notcross=false
}
}
if notcross{<!-- -->
cross=append(cross,ballon)
}
}
return len(cross)
}
func min(i,j int) int{<!-- -->
if i<j{<!-- -->
return i
}
return j
}
func max(i,j int) int{<!-- -->
if i>j{<!-- -->
return i
}
return j
}
Official solution
Intuitively, it seems that only the most overlapping balloons are shot, and the bows and arrows must be the least. So is there a situation where there are currently three overlapping balloons, I shoot two, and leave one to shoot with the latter so that the bow and arrow are used less? ?
Try to give a counterexample and find that this is not the case.
Then give greed a try! Local Optimum: When the balloons overlap, shoot together and use the least amount of bows and arrows. Global Optimum: The least amount of bows and arrows is used to burst all the balloons.
Code
func findMinArrowShots(points [][]int) int {<!-- -->
var res int = 1 //Number of bows and arrows
//sort first
sort.Slice(points, func (i,j int) bool {<!-- -->
return points[i][0] < points[j][0]
})
for i := 1; i < len(points); i ++ {<!-- -->
if points[i-1][1] < points[i][0] {<!-- --> //If the right boundary of the previous bit is smaller than the left boundary of the next bit, it must not overlap
res + +
} else {<!-- -->
points[i][1] = min(points[i - 1][1], points[i][1]); // Update the minimum right boundary of overlapping balloons, overwrite the value of this position, and save it for the next step
}
}
return res
}
func min(a, b int) int {<!-- -->
if a > b {<!-- -->
return b
}
return a
}
Difficult
Simulate the process of shooting a balloon
Harvest today
This question has two dimensions, h and k. When you see this kind of question, you must think about how to determine one dimension, and then rearrange it according to another dimension.
In fact, if you do 135. Distributing candy (opens new window) carefully, you will find that it is a bit similar to this question.
In 135. Distributing candy (opens new window), I emphasized once thatwhen encountering a trade-off between two dimensions, one must first determine one dimension, and then determine the other.
If you consider the two dimensions together, you will lose sight of the other.
For this question, I believe everyone is confused whether to determine k or h first, that is, whether to sort by h or k first?
If you sort from small to large according to k, after sorting, you will find that the arrangement of k does not meet the conditions, and the height does not meet the conditions, and neither of the two dimensions has been determined.
Then sort by the height h, the height must be arranged from large to small (if the height is the same, the small k stands in front), so that the tall ones are in the front.
At this point, we can determine a dimension, which is height, and the previous nodes must be taller than this node!