中小企业网站建设济南兴田德润电话,wordpress版,人才网站建设标题,郑州建设厅网站第八章 贪心算法 860.柠檬水找零406.根据身高重建队列452.用最少数量的箭引爆气球代码随想录文章详解 860.柠檬水找零
定义five,ten为顾客付5元和10元的张数#xff0c;找零时首先找较大面额#xff0c;分情况讨论#xff1a; 如果顾客付5元#xff0c;直接five 如果顾客付… 第八章 贪心算法 860.柠檬水找零406.根据身高重建队列452.用最少数量的箭引爆气球代码随想录文章详解 860.柠檬水找零
定义five,ten为顾客付5元和10元的张数找零时首先找较大面额分情况讨论 如果顾客付5元直接five 如果顾客付10元自己至少有一张5元five–,ten;否则返回false 如果顾客付20元自己至少有一张5元和一张10元five–,ten–或者自己至少有3张5元five-3否则返回false
func lemonadeChange(bills []int) bool {five, ten : 0, 0for i : 0; i len(bills); i {if bills[i] 5 {five} else if bills[i] 10 {if five 0 {tenfive--} else {return false}} else {if ten 0 five 0 {ten--five--} else if five 2 {five - 3} else {return false}}}return true
}406.根据身高重建队列
先对数组中数对的第一个元素降序排序然后对数对的第二个元素插入升序排序
func reconstructQueue(people [][]int) [][]int {// 1.高个子对矮个子没影响先降序排序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]})// 2.然后把矮个子插入对应位置person[i][1]即可res : make([][]int, len(people))for i : 0; i len(people); i {if len(res) people[i][1] {res append(res, people[i])} else {// 在指定位置插入元素index : people[i][1]copy(res[index1:], res[index:])res[index] people[i]}}return res
}原地排序
for index, person : range people {copy(people[person[1]1:index1], people[person[1]:index1])people[person[1]] person
}452.用最少数量的箭引爆气球
贪心对气球右边界排序初始时最大右边界为points[0][1]后续遍历的气球右边界都比初始值大只要保证气球左边界小于maxRight就能被箭射穿否则更新最大右边界箭个数
func findMinArrowShots(points [][]int) int {sort.Slice(points, func(i, j int) bool {return points[i][1] points[j][1]})res : 1maxRight : points[0][1]for i : 1; i len(points); i {if points[i][0] maxRight {continue}maxRight points[i][1]res}return res
}代码随想录文章详解
860.柠檬水找零 406.根据身高重建队列 452.用最少数量的箭引爆气球
