860.柠檬酸找零

文章：13. 柠檬水找零

题目：860. 柠檬水找零

【思路】

有三种情况：

1.账单是5，直接收下

2.账单是10，消耗一个5，增加一个10

3.账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5

分析得出：只有10和5是可以被交易出去的，而10的使用频率比5低。

局部最优：遇到账单20，优先消耗10，完成本次找零。

全局最优：完成全部账单的找零。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for(int i : bills){
            if(i == 5){
                five++;
            }else if(i == 10){
                five--;
                ten++;
            }else if(i == 20){
                if(ten >0){
                    ten--;
                    five--;
                }else{
                    five -= 3;
                }
            }
            if (ten < 0 || five <0){
                return false;
            }
        }
        return true;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func lemonadeChange(bills []int) bool {
    ten,five :=0,0
    for _,i:=range bills{
        if i == 5{
            five++
        }else if i == 10{
            ten++
            five--
        }else if i == 20{
            if ten >0 &&five >0{
                ten--
                five--
            }else{
                five -=3
            }
        }
        if ten <0 || five <0{
            return false
        }

    }
    return true

}

406.根据身高重建队列

文章：14. 根据身高重建队列

题目：406. 根据身高重建队列

【思路】

题目给出了两个维度：h身高、k属性

那么我们就需要在这两个维度上面选一个优先进行排序。

k属性的话，会有很多问题，因此我们确定以h属性为维度。

h属性：身高一定是按照大到小来排的，身高相同的话k小的在前面。

局部优先：优先按身高高的people的k来插入，插入操作后的people满足队列属性。

全局最优：最后都做完插入操作，整个队列满足题目队列属性。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{
            if(a[0] == b[0])return a[1] - b[1];//a-b是升序，小到大
            return b[0]-a[0];//b-a是降序，大到小
        });
        LinkedList<int[]> que = new LinkedList<>();
        for(int[] p: people){
            que.add(p[1],p);//linkedlist.add(index,value)将value插入到指定的index里面
        }
        return que.toArray(new int[people.length][]);

    }
}
  • Go实现

没看懂这里：

1
2
3
4
for i,p:=range people{
    copy(people[p[1]+1:i+1],people[p[1]:i+1])
    people[p[1]] =p
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]//从小到大排
        }else{
            return people[i][0] > people[j][0]//从大到小排
        }
    })
    for i,p:=range people{
        copy(people[p[1]+1:i+1],people[p[1]:i+1])
        people[p[1]] =p
    }
    return people
}

452.用最少数量的箭引爆气球

文章：17. 用最少数量的箭引爆气球

题目：452. 用最少数量的箭引爆气球

【思路】

贪心

局部最优：当气球出现重叠，一起射的时候所用的弓箭最少。全局最优：把所有气球射爆所用的弓箭最少。

排序+检查区间是否重叠，重叠的话更新最右边界，不重叠的话count+1

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        int count = 1;
        for(int i=1;i < points.length;i++){
            if(points[i][0] > points[i-1][1]){
                count++;
            }else{
                points[i][1] = Math.min(points[i-1][1],points[i][1]);
            }
        }
        return count;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func findMinArrowShots(points [][]int) int {
  sort.Slice(points,func(i,j int)bool{
    return points[i][0]<points[j][0]
  })
    count:= 1
    for i:=1;i < len(points);i++{
      if points[i][0] > points[i-1][1]{
        count++
      }else{
        points[i][1] = min(points[i-1][1],points[i][1])
      }
    }
    return count
}
func min(a,b int)int{
  if a>b {
    return b
  }
    return a
}

【算法总结】

  • 柠檬水找零：贪心，优先消耗使用频率最低的零钱
  • 根据身高重建队列：贪心，先按其中一个属性排序，然后再通过另一个属性插入队列。
  • 最小数量的箭射击气球：贪心，排序，查询重叠区间并更新最右区间（会出现气球最右范围变小的情况。

【语言总结】

  • Java

老生常谈的不懂自定义排序：

1
2
3
4
Arrays.sort(people,(a,b)->{
    if(a[0] == b[0])return a[1] - b[1];//a-b是升序，小到大
            return b[0]-a[0];//b-a是降序，大到小
        });
1
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
  • Go
1
2
3
4
5
6
7
sort.Slice(people,func(i,j int)bool{
       if people[i][0] == people[j][0]{
           return people[i][1] < people[j][1]//从小到大排
       }else{
           return people[i][0] > people[j][0]//从大到小排
       }
   })
1
2
3
sort.Slice(points,func(i,j int)bool{
  return points[i][0]<points[j][0]
})