Leetcode 860.柠檬水找零

题目：860.柠檬水找零

初始思路

思路很简单，5不用找零，10用5找零，20用10+5或者三个5找零

代码

  1. var lemonadeChange = function (bills) {
  2.     let five = 0
  3.     let ten = 0
  4.     for (let bill of bills) {
  5.         if (bill === 5) {
  6.             // 如果支付5的话，正好
  7.             five++
  8.         } else if (bill === 10) {
  9.             // 如果支付10的话，先用5找零，没有5就直接失败
  10.             if (five > 0) {
  11.                 five--
  12.                 ten++
  13.             } else {
  14.                 return false
  15.             }
  16.         } else {
  17.             // 如果支付20的话，优先使用10+5，或者三个5
  18.             if (ten > 0 && five > 0) {
  19.                 ten--
  20.                 five--
  21.             } else if (five >= 3) {
  22.                 five -= 3
  23.             } else {
  24.                 return false
  25.             }
  26.         }
  27.     }
  28.     return true
  29. };

感想

  1. 思路不难，可以简单写出来。

Leetcode 406.根据身高重建队列

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

初始思路

代码

  1. var reconstructQueue = function (people) {
  2.     let queue = []
  3.     people.sort((a, b) => {
  4.         if (b[0] !== a[0]) {
  5.             // 如果身高不等的话，身高大的在前面
  6.             return b[0] - a[0]
  7.         } else {
  8.             // 如果身高相等的话，编号小的在前面
  9.             return a[1] - b[1]
  10.         }
  11.     })
  12.     for (let i = 0; i < people.length; i++){
  13.         // 插入位置
  14.         // 第一个参数：规定从何处添加元素（下标），是数字
  15.         // 第二个参数：规定要添加多少元素，是数字
  16.         // 第三个数字：添加到数组的新元素
  17.         queue.splice(people[i][1], 0, people[i])
  18.     }
  19.     return queue
  20. };

感想

  1. 首先按照身高排序，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
  2. 按照身高排序之后，优先按身高高的people的k来插入，后序插入节点也不会影响前面已经插入的节点，最终按照k的规则完成了队列。
  3. image.png

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

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

初始思路

区间重叠的话，在重叠部分发射一根箭可以同时击穿气球。

代码

  1. var findMinArrowShots = function (points) {
  2.     // 按照起始坐标从小到大排序
  3.     points.sort((a, b) => {
  4.         return a[0] - b[0]
  5.     })
  6.     // points不为空至少需要一根箭
  7.     let res = 1
  8.     for (let i = 1; i < points.length; i++){
  9.         if (points[i][0] > points[i - 1][1]) {
  10.             // 如果下一个气球的起始位置够不到前一个气球的末尾，也就是不重合
  11.             // 需要一支箭
  12.             res++
  13.         } else {
  14.             // 更新重叠气球最小右边界,覆盖该位置的值，留到下一步使用
  15.             points[i][1] = Math.min(points[i - 1][1], points[i][1])
  16.         }
  17.     }
  18.     return res
  19. };

感想

  1. 如果气球重叠了，重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。image.png
  2. 注意题目中说的是：满足 xstart ≤ x ≤ xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆