用最少的箭引爆箭头

https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/

思路

1、排序：将气球按照左边界升序排序

2、什么情况箭数量要增加：points[i][0] > points[i-1][1]

3、怎么判断多个气球是都重叠：更新当前气球有边界。
points[i] = min(points[i][1],points[i-1][1])

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var findMinArrowShots = function(points) {
  if( points.length === 0) return 0
  let result = 1
  points.sort((a,b)=>{
    return a[0] - b[0]
  })
  for(let i=1;i<points.length;i++){
    if (points[i][0]>points[i-1][1]){
      result++
    }
    else{
      points[i][1] = Math.min(points[i][1],points[i-1][1])
    }
  }
  return result
};

无重叠区间

https://leetcode.cn/problems/non-overlapping-intervals/description/

思路

基本思路和上一题一毛一样
1、排序
2、result = 重叠区间数

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var eraseOverlapIntervals = function(intervals) {
  if (intervals.length === 0) return 0
  let count = 0
  intervals.sort((a,b)=>{
    return a[0] - b[0]
  })
  for(let i=1;i<intervals.length;i++){
    if(intervals[i][0] < intervals[i-1][1]) {
      count++
      intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1])
    }
  }
  return count
};

合并区间

https://leetcode.cn/problems/merge-intervals/description/

思路

判断 当前区间与前一个区间是否重叠，如果不重叠，将前一个区间加入结果中。如果重叠，修改当前区间的左（最小）右（最大）值。

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

var merge = function(intervals) {
  if(intervals.length === 0) return []
  let result = []
  intervals.sort((a,b)=>{
    return a[0]-b[0]
  })
  for(let i=1;i<intervals.length;i++){
    if(intervals[i][0] > intervals[i-1][1]){
      result.push(intervals[i-1])
    }
    else{
      intervals[i][1] = Math.max(intervals[i][1],intervals[i-1][1])
      intervals[i][0] = intervals[i-1][0]
    }
  }
  result.push(intervals[intervals.length-1])
  return result
};

监控二叉树

https://leetcode.cn/problems/binary-tree-cameras/description/

思路

此时这道题目还有两个难点：

• 二叉树的遍历
  前：根左右
  中：左根右
  后：左右根
• 如何隔两个节点放一个摄像头
  • 1、根据当前节点的左右节点的状态来确定，是否安装摄像头
    0：无覆盖
    1：有摄像头
    2：有覆盖
  • 2、具体的左右节点状态对应的行动
    1、左右节点都有一个没有覆盖：安装摄像头，result++，return 1
    2、左右节点有一个安装了摄像头，说明当前节点有覆盖，return 2
    3、左右节点都有覆盖，当前节点不安装摄像头，return 0
    4、最优如果根节点状态为0，为根节点安装摄像头。

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

var minCameraCover = function(root) {
  let result = 0
  //递归后序遍历
  const dfs = (node)=>{
    if(!node) return 2
    let left = dfs(node.left)
    let right = dfs(node.right)
    if(left === 0 || right === 0){
      result++
      return 1
    }
    if(left === 1 || right === 1){
      return 2
    }
    if(left === 2 && right === 2){
      return 0
    }
  }
  if(dfs(root) === 0){
    result++
  }
  return result
};

分发糖果

https://leetcode.cn/problems/candy/description/

思路

题目要求和相邻的孩子比较，相邻的孩子有两个，左边的和右边的。

一次遍历解决两边的孩子，容易顾此失彼，所以可以分两次遍历。

正序遍历时考虑左边的孩子（当前节点左边的），如果ratings[i]>ratings[i-1]，那么candys[i] = candys[i-1]+1。

逆序遍历考虑右边的孩子（当前节点右边的），如果ratings[i] > ratings[i+1]，那么
candys[i] = Math.max(candys[i], candys[i+1]+1)。

正序遍历做的事儿和反序遍历做的事儿不能对调，因为正序时，当前元素的左边元素一定时都处理过的，这样不会出错。反之逆序时，当前节点的右边节点也都处理过，不会出错。

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14

var candy = function(ratings) {
  let candys = new Array(ratings.length).fill(1);
  for(let i=1;i<ratings.length;i++){
    if(ratings[i]>ratings[i-1]){
      candys[i] = candys[i-1]+1;
    }
  }
  for(let i=ratings.length-2;i>=0;i--){
    if(ratings[i]>ratings[i+1]){
      candys[i] = Math.max(candys[i],candys[i+1]+1)
    }
  }
  return candys.reduce((a,b)=>a+b,0)
};

加油站

https://leetcode.cn/problems/gas-station/description/

思路

1、首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。

2、每一站的剩余油量rest[i] = gas[i]-cost[i]

3、i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。

4、那么为什么一旦[0，i] 区间和为负数，起始位置就可以是i+1呢，i+1后面就不会出现更大的负数？如果出现更大的负数，就是更新i，那么起始位置又变成新的i+1了。

那有没有可能 [0，i] 区间 选某一个作为起点，累加到 i这里 curSum是不会小于零呢？ 如图：

如果 curSum<0 说明 区间和1 + 区间和2 < 0， 那么 假设从上图中的位置开始计数curSum不会小于0的话，就是 区间和2>0。

区间和1 + 区间和2 < 0 同时 区间和2>0，只能说明区间和1 < 0， 那么就会从假设的箭头初就开始从新选择其实位置了。

那么局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。

局部最优可以推出全局最优，找不出反例，试试贪心！

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

var canCompleteCircuit = function(gas, cost) {
  let rem = []
  for(let i=0;i<gas.length;i++){
    rem.push(gas[i]-cost[i])
  }
  let sum = rem.reduce((a,b)=>a+b,0)
  if (sum<0) return -1
  let cursum = 0
  let start = 0
  for(let i=0;i<rem.length;i++){
    cursum += rem[i]
    if (cursum<0){
      start = i+1
      cursum = 0
      continue
    }
  }
  return start
};

1
2
3
4
5
6
7
8
9
10
11
12
13

// 更优解，ai根据我上面的代码做的简化，只需一层for循环
var canCompleteCircuit = function(gas, cost) {
  let total = 0, sum = 0, start = 0;
  for(let i = 0; i < gas.length; i++){
    total += gas[i] - cost[i];
    sum += gas[i] - cost[i];
    if(sum < 0){
      start = i + 1;
      sum = 0;
    }
  }
  return total < 0 ? -1 : start;
};

sort()

ES6 中的 Array.prototype.sort() 方法有以下几个特点：

1、原地排序：sort() 方法会在原数组上进行排序，而不是创建一个新的排序后的数组。

2、默认的排序顺序是按照字符串的 Unicode 码点顺序：如果在 sort() 方法中没有提供比较函数，那么数组元素会先被转换为字符串，然后再按照字符的 Unicode 码点顺序进行排序。例如，数字数组 [10, 2, 11] 会被排序为 [10, 11, 2]。

3、可以接受一个比较函数作为参数：你可以提供一个比较函数来自定义排序顺序。比较函数应该接受两个参数，返回一个负数、零或正数，来表示第一个参数应该排在第二个参数的前面、与第二个参数相等或后面。

4、稳定排序：从 ES2019 开始，Array.prototype.sort() 是稳定的。这意味着如果两个元素相等，它们的原始顺序会被保留

结论是:b-a降序, a-b升序
a-b时，if a-b>0, b排前面，升序；if a-b<0, a排在前面，升序。
b-a时，if b-a>0, b排前面,降序；if b-a<0, a排在前面，降序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

let arr2 = [8,1,5,9,3,4,2,6,7]
console.log(arr2.sort((a,b)=>b-a))
// [9, 8, 7, 6, 5, 4, 3, 2, 1]

let arr2 = [1,8,5,9,3,4,2,6,7]
console.log(arr2.sort((a,b)=>b-a))
// [9, 8, 7, 6, 5, 4, 3, 2, 1]


let arr2 = [8,1,5,9,3,4,2,6,7]
console.log(arr2.sort((a,b)=>a-b))
//[1,2,3,4,5,6,7,8,9]

let arr3 = [1, 8, 5, 9, 3, 4, 2, 6, 7]
console.log(arr3.sort((a, b) => a - b))
//[1,2,3,4,5,6,7,8,9]

买卖股票的最佳时机II

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

思路

这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入…..循环反复。

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。

如图：

求解

1
2
3
4
5
6
7
8
9

var maxProfit = function(prices) {
  let result = 0;
  for(let i=0;i<prices.length-1;i++){
    if(prices[i+1]>prices[i]){
      result += prices[i+1] - prices[i]
    }
  }
  return result
};

最大子数组和

https://leetcode.cn/problems/maximum-subarray/description/

思路

贪心的思路是，如果+nums[i]后子数组和为负数，那么以nums[i+1]为起始点进行遍历

卡哥说初始result要是计算机能表示的最小的整数，刚开始我不理解。现总结这样做的目的。

首先我们有两个变量result和count，result负责保存最终的结果，count保存遍历过程中子数组的和。

如果数组中有正整数，那么其实没必要result为最小整数。但我们不能保证数组中一定有正整数。 想一个极端的例子，数组中全是负数的情况。

在遍历到第1个负数的时候，result就被赋值为当前这个负数，此时count为负数，那么放弃这个起点，以第2个数为起点。如果第二个数大于第一个数，那么result被赋值为第2个负数。以此类推，result会是数组中最大的负数。

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var maxSubArray = function(nums) {
  //是为了解决数组中全是负数的情况。
  result = Number.MIN_SAFE_INTEGER
  sum = 0
  for(let i=0;i<nums.length;i++){
   sum += nums[i]
   if(sum>result){
     result = sum
   }
   if(sum<0){
    sum = 0
   }
  }
  return result
};

跳跃游戏

https://leetcode.cn/problems/jump-game/description/

思路

刚看到本题一开始可能想：当前位置元素如果是 3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？

其实跳几步无所谓，关键在于可跳的覆盖范围！

不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。

这个范围内，别管是怎么跳的，反正一定可以跳过来。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

局部最优推出全局最优，找不出反例，试试贪心！

如图：

求解

1
2
3
4
5
6
7
8

var canJump = function(nums) {
  let max = 0;
  for(let i=0;i<=max;i++){
    if (i+nums[i]>max) max = i+nums[i]
    if(max>=nums.length-1) return true
  }
  return false
};

求解过程中，写过一个错误版本，就是给max赋值之前没有判断。有一部分例子没法通过。

当时没通过的案例是[3,0,8,0,0,2],在这个案例中，如果不做判断那么覆盖范围max会卡在 1+0

跳跃游戏II

https://leetcode.cn/problems/jump-game-ii/description/

思路

本题相对于55.跳跃游戏 (opens new window)还是难了不少。

但思路是相似的，还是要看最大覆盖范围。

本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？

贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。

思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

如图：

图中覆盖范围的意义在于，只要红色的区域，最多两步一定可以到！（不用管具体怎么跳，反正一定可以跳到）

求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

var jump = function(nums) {
  let cover = 0
  let step = 0
  let last = 0
  for(let i=0;i<nums.length-1;i++){
    cover = Math.max(cover,i+nums[i])
    // 走了step步还没到终点，说明步数需要+1，
    // last记录的是当前覆盖范围的最后一个位置
    if(i === last){
      last = cover
      step++
    }
  }
  return step
};

摆动序列

https://leetcode.cn/problems/wiggle-subsequence/description/

贪心算法思路：
1、找到峰值，prediff和currdiff一正一负。prediff = nums[i] - nums[i-1],currdiff = nums[i+1] - nums[i]。

(prediff > 0 && currdiff < 0) || (prediff < 0 && currdiff > 0)

2、特殊情况，遇到平坡的情况
这种坡的特点是坡是峰位。那么我们可以把相同的数字删除到只剩一个，即可得到正确答案，这里选择只保留平坡最右边的元素。也就是说prediff可以等于0。

(prediff >= 0 && currdiff < 0) || (prediff <= 0 && currdiff > 0)

3、首尾元素
题目中说了，如果只有两个不同的元素，那摆动序列也是 2。如果只有两个元素，但元素是相同的，那么摆动序列只有一个。
因此可以简单的做判断，确定result。

当然可以想的更正规一点，更科学一点。

可以假设，数组最前面还有一个数字，那这个数字应该是什么呢？

之前我们在 讨论 情况一：相同数字连续 的时候， prediff = 0 ，curdiff < 0 或者 >0 也记为波谷。

那么为了规则统一，针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，如图：

4、情况四单调坡度有平坡
只考虑上述的三种特殊情况的话，我们忽略了一种情况，即 如果在一个单调坡度上有平坡，例如[1,2,2,2,3,4]，如图：

图中，我们可以看出，版本一的代码在三个地方记录峰值，但其实结果因为是 2，因为 单调中的平坡 不能算峰值（即摆动）。

之所以会出问题，是因为我们实时更新了 prediff。那么我们应该什么时候更新 prediff 呢？

我们只需要在 这个坡度 摆动变化的时候，更新 prediff 就行，这样 prediff 在 单调区间有平坡的时候 就不会发生变化，造成我们的误判。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var wiggleMaxLength = function(nums) {
  if (nums.length < 2) {
    return 1;
  }
  result = 1
  prediff = 0
  currdiff = 0
  for(let i=0;i<nums.length-1;i++){
    currdiff = nums[i + 1] - nums[i]
    if((prediff<=0 && currdiff>0) || (prediff>=0 && currdiff<0)){
      result++
      prediff = currdiff
    }
  }
  return result
};

分发饼干

https://leetcode.cn/problems/assign-cookies/

策略：size大的饼干给胃口大的小孩。

步骤：
1、两个数组进行排序
2、外循环遍历小孩胃口
3、内循环遍历饼干

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

var findContentChildren = function(g, s) {
  s.sort((a,b)=>a-b);
  g.sort((a,b)=>a-b);
  let count = 0;
  //遍历小孩胃口
  let j = s.length-1;
  for(let i=g.length-1;i>=0;i--){
    //遍历饼干，如果饼干满足要求，count+1，然后跳出while循环，考虑下一个小孩
    while(s[j]>=g[i]){
      count++;
      j--
      break;
    }
  }
  return count;
};