关于leetcode:JavaScript刷LeetCode拿offer贪心算法

52次阅读

共计 14863 个字符,预计需要花费 38 分钟才能阅读完成。

前言

学习算法的时候,总会有一些让人生畏的名词,比如 动静布局 贪婪算法 等,听着就很难;而这一 part 就是为了攻破之前始终没有零碎学习的 贪婪算法

有一说一,做了这些贪婪题,其实并没感觉发现了什么套路新大陆等,因为贪婪有的时候很奇妙,而且想到就是想到了,没想到可能就不必贪婪去做了,所以这属于做完只是刷了存在感的 part;

惟一的播种就是加重了对贪婪的恐怖,明确它也就是一种 部分贪婪导致全局贪婪失去最优解 的一种思路办法,所以当前遇到了,也就能平心静气的去学习应用它了;

下一 part 去做一下比拟难的 并查集

注释

455. 散发饼干

剖析 — 贪婪

  1. 用最大的饼干满足胃口最大的小孩,这样就能部分最优求出全局最优,能够满足最多的小孩
  2. 因为 g,s 都须要取最大,所以须要排序
  3. 最初用两个端套的遍历找出最优解
  4. 工夫复杂度 O(n+m)
var findContentChildren = function (g, s) {g.sort((a,b) => a-b)
    s.sort((a,b) => a-b)
    let ret = 0
    let sl = s.length-1; 
    let gl = g.length-1
    while(gl>=0){
        // 人没了,饼干能够还存在
        if(s[sl]>=g[gl] && sl>=0){
            // 最大的饼干是否满足最大胃口的孩子
            ret++
            sl--
        }
        gl--
    }
    return ret
}

376. 摆动序列

剖析 — 贪婪

  1. 间断数字之间差值是正负交替的,叫做摆动序列;
  2. 边缘状况,如果只有 1 个值,或者两个不相等的值,也是摆动序列
  3. 如果呈现 0,则间接不是摆动序列了
  4. 如果部分符合要求,依照条件部分删除不符合要求的值,就是贪婪的做法
  5. 工夫复杂度 O(n)
  6. 参考视频:传送门
var wiggleMaxLength = function(nums) {if(nums.length<2) return nums.length
    let ret = 1 // 从 1 开始是因为要求的是整个摆动序列的长度,所以先初始化 1,而后遇到极值递增即可
    let preDiff = 0 // 初始化第一个差值;设置为 0,则无论真正第一个差值是多少,失去的都是 0
    let curDiff = 0
    for(let i = 1;i<nums.length;i++){curDiff = nums[i]- nums[i-1]
        // 差值必须是正负数,如果是 0 则跳过
        if(curDiff === 0) continue
        if(preDiff * curDiff <= 0){
            ret++
            preDiff = curDiff
        }
    }
    return ret
};

53. 最大子序和

剖析 — 贪婪

  1. 求的是最大和的 间断子数组
  2. 用 sum 缓存后面和大于 0 的子数组之和,一旦小于 0,就不再累加,从新置 0, 放弃每一次迭代前 sum 的值都是 >=0
  3. 这样对于每一个部分子数组,它的累加值都是大于等于 0 的,这样每次累加一个新值,就进行最大值比拟,保障整体是一个最大子数组之和
  4. 工夫复杂度 O(n)
var maxSubArray = function (nums) {
  let max = -Infinity;
   let sum = 0
   for(let i = 0 ;i<nums.length;i++){sum+=nums[i]
       max = Math.max(sum,max)
       if(sum<=0){sum=0}
   }
   return max
};

55. 跳跃游戏

剖析 — 回溯 — 超时了

  1. 间接将所有可能性写进去,将对应不适合的移除
  2. 工夫复杂度 n∗m 其中 n 是 nums 的长度,m 是每一个值的大小
 var canJump = function (nums) {
    let ret = false;
    const dfs = (start) => {
      // 只有有一个胜利,就间接不做其余解决了
      if (start >= nums.length || ret) return;
      if (start+nums[start] >= nums.length-1) {
        ret = true;
        return;
      }
      for (let i = 1; i <= nums[start]; i++) {dfs(start + i); // 在以后这一个节点,能够跳的步数
      }
    };
    dfs(0)
    return ret;
  };

剖析

  1. 这里只有不遇到值为 0 就能够持续往后走,也就是部分贪婪就是要跳过值为 0 的步骤
  2. 当然如果 0 是在数组最初一位也是 ok 的
  3. 咱们能够判断一下是否存在一个值 nums[valIndex] > 0Index – valIndex, 这样只有达到 valIndex 就能够越过 0 这个点了
  4. 所以咱们须要遍历所有节点,找到值为 0 的节点,而后再进行跳跃判断;
  5. 因为咱们是要走到最初一个下标,所以最初一个下标是不必判断的,所以 i 最多走到 nums.length-1 的地位
  6. 工夫复杂度最小是 n,
 var canJump = function (nums) {for(let i=0;i<nums.length-1;i++){if(nums[i] === 0){
            // 开始寻找能够跳过以后 i 值的节点
            let valIndex = i-1
            while(nums[valIndex]<= i -valIndex && valIndex>=0){valIndex--}
            if(valIndex<0) return false
        }
    }
    return true
 }

45. 跳跃游戏 II

/** * @剖析 -- 已知能达到地位,求起码跳跃次数 * 1. 看到起码,想到用 dp 做;其中 dp[i] 就是达到 i 这个地位起码须要跳跃的次数, 然而管制以后状态的变量在上一个值,感觉 dp 不太适合 * 2. 感觉用贪婪 + 回溯会更好一点,每一次尽量远的跳,如果不行再跳回来 * 3. 而后失常超时了 */
var jump = function(nums) {if(nums.length < 2) return 0
    let ret = Infinity

    const dfs = (index,sum) => {if(index>=nums.length-1) {
            // 贪婪走进去的,必定是
            ret = Math.min(sum,ret)
            return 
        }
        if(sum>=ret || nums[index] === 0) return // 只有出了第一个,前面的全副不玩了

        for(let i = nums[index];i>0;i--){dfs(index+i,sum+1)
        }
    }
    dfs(0,0)
    return ret
};

/** * @剖析 * 1. 思考到跳跃范畴必须笼罩肯定范畴,求最小的目标,还是从后倒推后面会更难受一点,所以思考 dp;* 2. dp[i] 示意跳跃到 i 这个地位最小的次数 * 3. 状态转移方程: dp[i] = Math.min(dp[i-valid]+1) 这里的 valid 是值合乎 nums[j]+j >= i 的 dp[j], 这样在 j 这个地位能力一次跳到 i * 4. base case: dp[0] = 0 原地蹦跶 * 5. 工夫复杂度 ${O(n^2)}$ */
var jump = function(nums) {const dp = new Array(nums.length)
    dp[0] = 0 // 原地蹦跶
    for(let i=1;i<nums.length;i++){dp[i] = Infinity
        for(let j = i-1;j>=0;j--){if(nums[j]+j>=i){
                // 这样能力从 j 跳到 i
                dp[i] = Math.min(dp[i],dp[j]+1)
            }
        }
    }
    return dp[nums.length-1]
}

/** * @剖析 -- 贪婪 * 1. 每一次跳动都能够缓存最大跳跃范畴,这是一个范畴而不是一个值,所以下一跳的时候,须要从这个范畴内找到最最大跳跃的范畴 * 2. 所以只有迭代每一个值,就能够找到跑到这个值的时候,最大跳跃的覆盖范围 nextIndex 的地位, 同样的,咱们将上一轮的最大间隔设置为 curIndex * 3. 每当迭代到 curIndex, 表明上一次跳跃的覆盖范围都曾经遍历完,并且记录好了这个范畴内的最大值 nextIndex 了,这个时候更改 curIndex = nextIndex * 4. 其实整个过程就是在 [curIndex,nextIndex] 中找最大范畴,而后一直迭代;* 5. 只须要遍历一次就能找到后果了,所以工夫复杂度 ${O(n)}$ */
 var jump = function(nums) {
    let curIndex = nextIndex = 0
    let ret = 0
    for(let i =0;i<nums.length;i++){if(curIndex >=nums.length-1) return ret // 如果最大覆盖范围曾经找到了中央,那么就间接跳出遍历了
        nextIndex = Math.max(nextIndex,nums[i]+i) // 最远覆盖范围
        if(curIndex === i) {// 如果 i 达到上一次最远笼罩地位,那么 nextIndex 就是上一轮 [cur,next] 的最大间隔,当初须要更新一下
            curIndex = nextIndex
            // 所谓笼罩,就是 jump 一次
            ret++
        }
    }
}    

1306. 跳跃游戏 III

留神,这里并没有用到贪婪,然而这是一个主题的题目,所以也放在一起来学习了;比拟分块学习也是按组类学习,而咱们真正遇到问题的时候,是不会给你打 tag 说是用啥办法做的,所以相相似的题放一起做,即使因为题目扭转了,没有用到相应的技术,也值得放在一起学习一哈;
剖析 — BFS

  1. 终点扭转,跳跃也从单边转左右两边,目的地也从止境到跳跃到 0 的地位 — 留神,以前是能够跳任意地位,当初只能左右跳两个地位,而不是范畴跳跃
  2. 基于 BFS 将数组转成相似二叉树的 bfs 搜寻, 每一个节点都能够走左右两个节点 l,r, 如果符合条件,就退出到队列中持续走
  3. 应用的 useSet 缓存走过的节点,进行剪枝
var canReach = function (arr, start) {const queue = [];
  queue.push(start);
  const useSet = new Set();

  while (queue.length) {
    let len = queue.length;
    while (len--) {const node = queue.shift();
      const l = node - arr[node];
      const r = node + arr[node];
      if (l >= 0 && !useSet.has(l)) {if (arr[l] === 0) return true;
        queue.push(l);
        useSet.add(l);
      }
      if (r < arr.length && !useSet.has(r)) {if (arr[r] === 0) return true;
        queue.push(r);
        useSet.add(r);
      }
    }
  }
  return false;
};

剖析 — dfs

  1. 因为没一个点最多只能左右跳一次,所以和二叉树十分类似,能够用 bfs,当然也能够用到 dfs
  2. 然而判断条件不能简略的用 node 是否在 [0,arr.length-1], 因为在左右跳的过程中会有反复的点,如果不讲反复点剪掉,岂但反复计算,而且会导致死循环
  3. 所以用 set 缓存曾经走的 node,一旦再进入就移除,这样就能残缺遍历能够跳到的地位,并最终跳出 dfs 遍历,失去最终后果
  4. 工夫复杂度 O(n), 空间复杂度 O(n)
var canReach = function (arr, start) {
  let ret = false;
  const useSet = new Set(); // 剪枝用的
  const dfs = (node) => {if (useSet.has(node) || ret === true) return;
    if (arr[node] === 0) {
      ret = true;
      return;
    }
    useSet.add(node);
    if (node - arr[node] >= 0) {dfs(node - arr[node]);
    }
    if (node - arr[node] < arr.length) {dfs(node + arr[node]);
    }
  };
  dfs(start);
  return ret;
};

1005. K 次取反后最大化的数组和

剖析

  1. 咱们要转换,必定是要将正数转成负数,这样能达到最大,那么状况有两种,k 短缺将所有正数转换成负数,k 有余
  2. 第一次贪婪,如果 k 不短缺的时候,要先将最大的非正数,这种状况就须要排序了,所以一开始先排个序吧 — 优先给最大的正数进行转换
  3. 第二次贪婪,如果将所有非正数转成负数后,k 还有,那么这个时候只须要解决最小的那个值就好了;
  4. 咱们在第一次贪婪的时候是排好序去解决非正数的,所以当解决完非正数之后,index 所在的地位要不就是数组之外,要不就是原始数组第一个非正数,这个时候 index-1 就是转换后的最小非正数,他们之间的比照能够找出以后数组的最小值
  5. 须要留神两种非凡状况,如果入参 nums 全是非正数,则 index 不会挪动,那么 nums[index-1] 就取不到,同理,如果 nums 全是正数,则 index 在数组外了,所以要把两种状况思考进去
  6. 最初只须要对 min 进行重复转换,如果 k 是偶数,那么就间接不转了,如果是奇数,那么就减去 min*2
  7. 工夫复杂度 O(nlogn)
 var largestSumAfterKNegations = function(nums, k) {nums.sort((a,b)=>a-b)
     let index = 0
     while(k && nums[index] < 0){
        // 如果 k 还存在且以后值还是正数的时候,就转换
        nums[index] = - nums[index]
        k--
        index++
     }
    // 转换后 index 所在的地位就是最开始最小值非正数了,然而它有可能比转换后的最小负数小,所以要比照一下
    // 然而如果 index 是第一个值,也就是一开始全都是非正数的时候,这个时候就没有 index-1 了;// 同理,如果全是正数,那么 index 就不存在了

    let min = index=== 0 ? nums[index] : index=== nums.length?nums[index-1] :Math.min(nums[index], nums[index-1])
    // 先将所有正数都转成负数 -- 如果 k 还存在,那么就解决 nums[index] 就好了
    let sum  = nums.reduce((pre,cur)=>pre+cur,0)
    if(k % 2) sum -= min*2
    return sum
};

122. 交易股票的最佳时机 II

剖析 — 贪婪

  1. 屡次交易,只有计算出每日的收益,而后将每日收益为正的收集起来就是最大收益
  2. 因为本题是屡次交易,不须要手续费和间隔时间,
  3. 所以如果有间断正收益的时候,相当于间断持有,如果距离收益,那就是在负收益第一天先卖出后,在负收益的后一天买进,一样能够失去断开的正收益,所以只有将所有正收益手机起来就好
  4. 这样部分收益就能够扩大成全局收益,而后就能够失去最终最大的收益了
var maxProfit = function(prices) {
    let ret = 0
    for(let i = 1;i<prices.length;i++){const temp = prices[i]-prices[i-1]
        if(temp>0){ret+=temp}
    }

    return ret
}

134. 加油站

剖析

  1. 咱们思考到每次加完油,就要跑路,有一些油站油充沛,那么跑完一段之后会有的剩,而有些油站油少,还得补贴一点,至于具体情况如何,咱们须要计算一下,所以用 leaves 来示意跑 [i,i-1] 的净油量
  2. 应用贪婪的思维,起始车是没油的,所以必须是 leaves[i]>=0 的时候,才有可能是起始地位,而后开始往后面走,每次判断一下是否足够下一段路的行走,如果不行,果决放弃上一次的起始点,找下一个起始点
  3. 如果在第一次遍历过程中,没找到一个点 ret 能够走完 [ret,len-1] 的途程,那么代表所有终点都生效了,间接返回 -1
  4. 如果存在,那么对于循环的车道,还得再走一遍 [0,ret-1],如果也胜利了,就返回 ret
  5. 在整个过程中,如果累计油量放弃为非负,那么就不要更改起始地位 ret, 因为你扭转了地位,状况不会更好,只会更坏,这也是贪婪的实质,每一次都做最好的抉择,那么在两头的时候要不放弃,要不就不要改了
  6. 工夫复杂度 O(n), 空间复杂度 O(n)
var canCompleteCircuit = function (gas, cost) {const leaves = gas.map((g, i) => g - cost[i]); // 每一个站台加油后跑路之后,残余值的数组,负数就是有残余,正数就是有余,须要在某些中央补充;let ret = -1;
  let sum = 0; // 缓存以后油量
  for (let i = 0; i < leaves.length; i++) {if (leaves[i] >= 0) {if (ret === -1) {ret = i;}
      sum += leaves[i];
      continue;
    }
    if (sum + leaves[i] < 0) {
      // 之前那个终点曾经失败了
      ret = -1; // 复原到 -1
      sum = 0;
    } else {sum += leaves[i]; // 持续走着
    }
  }
  if (ret === -1) return -1; 
  // 如果走完这一段,sum 还存在,证实在 [ret,leaves.length-1] 是合格的,那么持续走一下 [0,ret]
  for (let i = 0; i < ret; i++) {if (leaves[i] >= 0) {sum += leaves[i];
      continue;
    }
    if (sum + leaves[i] < 0) {
      // 在这个循环中一旦呈现不适合的,就不再走上来了,因为曾经走过一次了
      return -1;
    } else {sum += leaves[i]; // 持续走着
    }
  }
  return ret
};

剖析

  1. 基于下面那种贪婪,其实有更好的断定形式,就是只有 gasSum >= costSum , 那么必然存在一个终点,可能让车跑完一圈,因为那些差值很大的区间,都是最初积攒大量的残余油才会去跑的;
  2. 下面的第二次 [0,ret] 能够不必跑,只有判断出有一个值能够走完 [ret,len-1], 同时 gasSum >= costSum,那么这个 ret 的点就是终点了
var canCompleteCircuit = function (gas, cost) {const leaves = gas.map((g, i) => g - cost[i]); // 每一个站台加油后跑路之后,残余值的数组,负数就是有残余,正数就是有余,须要在某些中央补充;let ret = -1;
  let sum = 0; // 缓存以后油量
  let gasSum = 0
  let costSum = 0
  for (let i = 0; i < leaves.length; i++) {costSum+=cost[i]
    gasSum+=gas[i]
    if (leaves[i] >= 0) {if (ret === -1) {ret = i;}
      sum += leaves[i];
      continue;
    }
    if (sum + leaves[i] < 0) {
      // 之前那个终点曾经失败了
      ret = -1; // 复原到 -1
      sum = 0;
    } else {sum += leaves[i]; // 持续走着
    }
  }
  if (gasSum<costSum) return -1; 
  return ret
};

135. 散发糖果

剖析 — 题目形容有问题

  1. 第二个条件应该是,只有你比邻近地位的评分大,那么你就必然比邻近的人分得的糖果多
  2. 先初始所有 candies 的值为 1
  3. 而后分两局部解决,先和左侧分数值比拟,只有比左侧大,那么 candies[i] ++
  4. 而后再从右往左遍历,只有比左侧的分数高,那么就进行比拟,取最大值 Math.max(candies[i],cadies[i+1]+1)
  5. 最初失去的数组 candies 就能保障,分数更高小孩,必定比邻近分数更低的小孩的 candies 更多
  6. 工夫复杂度 O(n)
  7. 这里起码的发糖就用到了贪婪的思维,尽可能少的给糖,先右边部分起码给糖,而后左边部分起码给糖,而后就能够影响最终给糖的数量
var candy = function (ratings) {
  const len = ratings.length;
  const candies = new Array(len).fill(1); // 发糖果的数组
  for (let i = 1; i < len; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;
    }
  }
  for (let i = len - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {candies[i] = Math.max(candies[i + 1] + 1,candies[i]); // 从左边数的时候,就要判断哪边更大了
    }
  }
  return candies.reduce((pre, cur) => pre + cur, 0);
};

860. 柠檬水找零

剖析

  1. 如果能思考到部分贪婪,根本就是一道遍历题
  2. 因为 5 元属于更小粒度的单位,在数量足够的时候能够组合成 10 元,所以咱们在给 20 元找零的时候,部分贪婪的保留 5 元,这样能保障出力后续的时候更可能实现工作
  3. 所以剩下的就是将状况排列进去了
  4. 工夫复杂度 O(n)
var lemonadeChange = function(bills) {
    let fives = 0
    let tens = 0

     for(let i =0;i<bills.length;i++){const b = bills[i] 
         if(b === 5){fives++}
         if(b === 10) {if(fives>0){
                 fives--
                 tens++
             }else {return false}
         }
         if(b === 20){
             // 当初用贪婪,先尽可能的用 10 块去找零,因为 5 块是粒度更小的零钱,它通用性更强,所以尽可能贪婪的保留 5 块
             if(tens>0 && fives>0){
                tens--
                fives--
             }else if (tens === 0 && fives>=3){fives -=3}else{return false}
         }
     }
     return true

 };

406. 依据身高重建队列

剖析

  1. 先分类,将身高一样的先缓存在一起
  2. 而后依据 key 从高到低开始贪婪的排列,因为每一次咱们都取 最高且后面人数起码 的 item,这个时候队列的两个条件曾经一起限度好,只须要依照 item[i] 插入到 ret 上就足够了 — 后续的插入是不会影响到以后插入的,因为后续的值必定会贴合现有排好的 ret;
  3. 咱们能够先取出身高更高的值,因为这个时候,排在它后面的,就只有它本人和曾经排好的数组 — 这就是部分贪婪
  4. 这个时候在雷同身高的数组里,还要依据后面的人数进行一次排序,保障少的在后面 — 这样以后 item 插入到最终 ret 的时候,它就能够依据 item[1] 直接插入到 ret 对应的地位了
  5. 工夫复杂度 O(n), 空间复杂度 O(n)
var reconstructQueue = function(people) {const map = new Map(); // 先将身高一眼给的缓存起来
    for(let i = 0;i<people.length;i++){const key = people[i][0]
        map.set(key,map.get(key)?[...map.get(key),people[i]]:[people[i]])
    }
    const arr = [...map.keys()].sort((a,b)=>b-a) // 从大到小
    const ret = []
    for(let i = 0;i<arr.length;i++){const tempArr = map.get(arr[i]) // 取出数组
        tempArr.sort((a,b)=>a[1]-b[1]) // 身高雷同的数组,要依据在他们后面的人的数量进行排序,这样能力保障后面人少的在后面
        // 这个时候须要只须要按找数组的第二个值,插入到最终数组即可
        for(let temp of tempArr){ret.splice(temp[1],0,temp) // 在 temp[1] 的地位插入 temp
        }
    }
    return ret
};

const ret = reconstructQueue([[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]);
console.log(ret)

452. 用起码数量的箭引爆气球

剖析 — 失败

  1. 首先要审题并了解题目,尽管说的是二维空间的气球,然而理论排列的时候在一个坐标 x 上可能会存在气球的重叠;所以当箭从 x 射进去,就能够一次突破 n>1 个气球
  2. 所以题目就转换成 — 每次找到 重叠最多 的地位进行射击,当气球射完须要多少箭;– 也就是找到交加的数量
  3. 这里能够和并查集进行比照,并查集遇到交加后,会扩大汇合为并集,而这里是膨胀到交加,所以刚好是相同的概念
  4. 这里用到的贪婪思维就是,一旦有交加,咱们就把两个气球膨胀为一个更小的气球,部分贪婪的将有交加的气球压缩到一个更小的气球中,这样最初剩下的气球就是互相隔离的,达到全局的贪婪 — 尽可能少的射击
  5. 工夫复杂度 O(n), 空间复杂度 O(n)
  6. 这种写法失败的起因在于,随机找进去一个区间值,这个区间值的膨胀是随机的,所以就会呈现一个很小的区间 A 将原本能够包容更多气球的某一个区间 B 膨胀的很小区间 C,使得最初的后果不够贪婪,而最优的状况是将区间 A 放在另外的一个区间 A1 上,而后让 B 区间包容更多的气球 B1,B2;
  7. 所以须要将无序的气球按排好序,这样按程序在部分范畴内最贪婪的重叠气球,就能够保障在部分范畴内,尽可能小的放大取值区间,包容更多的气球 — 具体看 剖析 2
 var findMinArrowShots = function(points) {
    const len =  points.length 
    let ret = [] // 缓存没有交加的数组
    for(let i =0;i<len;i++){const pp  = points[i]
        let isMerge = false
        for(let i = 0;i<ret.length;i++){const rr = ret[i]
            // 如果起始地位都超过了终止地位,那么就没有交加了
            if(pp[0]>rr[1] || pp[1]< rr [0]) continue
            // 否则就是有交加了,那么只有保留交加就好,因为射中交加的时候,一次性就实现所有的气球爆炸
            ret[i] =  pp[0]<=rr[0]?[rr[0],Math.min(pp[1],rr[1])]:[pp[0],Math.min(pp[1],rr[1])]
            isMerge = true // 如果合并了
            break
        }
        if(!isMerge){ret.push(pp)
        }
    }
    return ret.length
};

剖析 2

  1. 基于下面那种两边同时限度,会呈现分组限度更多的状况,咱们限度其中一边进行排序,尽可能应用其中一边作为限度条件,在这里咱们依据 left 作为排序根据进行排序
  2. 排序之后,咱们只须要判断新的气球的最右边是否来到了以后气球的最左边,就能够判断是否是同一组;
  3. 如果属于同一组,那么须要当初这一组最 right 的地位,这个地位也是射击的最右地位,保障往这个点射进去,这一组的气球全爆,所以须要找的是交加最小值
  4. 工夫复杂度 O(nlogn), 空间复杂度 O(1)
  5. 这里用到的贪婪思维就是尽可能部分最多重叠的气球,而上题也是因为没法保障会让最多重叠气球放在一起
var findMinArrowShots = function(points) {
    const len =  points.length 
    points.sort((a,b)=>a[0]-b[0])
    let cur = -Infinity;
    let ret = 0
    for(let i = 0 ;i<len;i++){const pp  = points[i]
        if(pp[0]>cur) {
            // 超出范围了
            ret++
            cur = pp[1] // 批改
        }else{cur = Math.min(cur,pp[1])
        }
    }
    return ret
}

findMinArrowShots([[10,16],[2,8],[1,6],[7,12]])
findMinArrowShots([[1,2]])
findMinArrowShots([[3,9],[7,12],[3,8],[6,8],[9,10],[2,9],[0,9],[3,9],[0,6],[2,8]])

剖析 3 — 右侧节点排序

  1. 应用左侧节点排序,在重合区域要保障 right 节点最小,这个能力保障下一个值能够落到汇合的交汇处
  2. 然而应用右侧排序的时候,自身 right 节点就比 left 节点要大,所以右侧排序后,其余的节点对于以后节点 [l1,r1] 而言,只有 l2 < r1, 那么必然是存在于区间内的,而且只有存在于区间内,那么 right 值都不须要变,因为第一个取值就是最小了,所以有上面的写法
  3. 这种排序更直观一点,画图会更好看清楚
var findMinArrowShots = function(points) {
    const len =  points.length 
    points.sort((a,b)=>a[1]-b[1]) // 右侧排序
    let right = -Infinity;
    let ret = 0
    for(let i = 0 ;i<len;i++){const pp  = points[i]
        if(pp[0]>right) {
            // 超出范围了
            ret++
            right = pp[1] // 批改
        }
    }
    return ret
}

435. 无重叠区间

剖析

  1. 和 452. 用起码数量的箭引爆气球 相似,只是那边尽可能汇合在一起,这里是要离开
  2. 所以这里以区间的右侧值做排序,这样 的益处就是,一旦某个值的 left 大于以后的 right 值,那么就呈现齐全隔离的区间了;
  3. 最初的答案就是长度减去能够齐全隔离的区间
var eraseOverlapIntervals = function(intervals) {
    const length = intervals.length
    intervals.sort((a,b) => a[1]-b[1]) // 按右侧大小排列好
    let  right = -Infinity
    let ret = 0 // 汇合数量
    for(let i = 0;i<length;i++){const ii = intervals[i]
        if(ii[0]>=right) {
            ret++ 
            right = ii[1]
        }
    }
    return length-ret
}

763. 划分字母区间

剖析

  1. 题目限度条件 1:雷同的字符只能存在于同一个字符串片段;限度条件 2:尽可能多的切分字符串片段
  2. 所以咱们先用 map 缓存每个字符最初呈现的下标值,那么当我的字符串中存在这个字符,那么起码要走到它的止境下标
  3. 相当于开启了一个不定长窗口,而后在这个窗口遍历过程,判断窗口的最长值是否须要扩大,当窗口遍历实现后,记录窗口的长度,而后执行下一个窗口
  4. 工夫复杂度 O(n), 空间复杂度 O(n)
  5. 这里没看出部分贪婪导向全局贪婪,可能是保障所有雷同字符都要在一起算是部分贪婪吧
var partitionLabels = function(s) {const map = new Map() // 记录字符和最初一个字符对应的下标
    for(let i = 0;i<s.length;i++){const ss = s[i]
        map.set(ss,i)
    }
    console.log(map)
    let ret = []
    let start = 0
    // 当初尽可能短的获取片段
    while(start<s.length){
        let temp = start // 起始值
        let end = map.get(s[start]) // 第一个字母的最初一个下标

        while(start<=end){if(map.get(s[start])>end){end = map.get(s[start]) // 将 end 变长
            }
            start++
        }
        // 抛出一轮了
        ret.push(start-temp)
    }
    return ret
};

console.log(partitionLabels('ababcbacadefegdehijhklij'))

56. 合并区间

剖析

  1. 这里是合并所有重叠的区间,不是两两重叠的区间,所以还是得排个序,这样只需哟啊判断一遍即可,不然间接写个 ret,原来不连贯的区间,可能加了一个新的 item 就连接起来了,更麻烦
  2. left 节点排序是比拟适合的, 因为这里须要在某个节点隔断之后,往后的节点不会再影响到 ret 数组里的区间
  3. 如果用 right 节点排序,就会呈现 [k,r],[k-1,r+1] 的状况,那么曾经放入到独自区域的区间还要拿进去用
  4. 最初遍历一遍完结,工夫复杂度 O(n)
var merge = function (intervals) {intervals.sort((a, b) => a[0] - b[0]);
  let ret = [];
  let cur = intervals[0];
  for (let i = 1; i < intervals.length; i++) {const temp = intervals[i];
    if (temp[0] > cur[1]) {
      // 当取出的空间的起始值曾经比以后值要大的时候,那么剩下的其余值,也会齐全和以后的 cur 隔离开,所以将以后 cur 推入 ret 中
      ret.push(cur);
      cur = temp; // 替换 cur
    }
    if (cur[1] < temp[1]) {cur[1] = temp[1];
    }
  }
  return [...ret, cur];
};

console.log(
  merge([[1,4],[2,3]]
  )
);

738. 枯燥递增的数字

剖析

  1. 审题,这里是要找一个最大的数 num,num 的位须要单增, 也就是 1234, 这样的,同时 num <= n
  2. 这题数字转字符串转数组,将每个值转成单个数值来计算了,这样更不便点
  3. 这里最初要求的是递增的数组,所以咱们能够依据 i-1 和 i 之间的值进行替换,当 arr[i-1]>arr[i] 的时候,arr[i-1] 减一,设置锚点 flag
  4. 从后往前遍历完之后,找到左侧第一个须要设置为 9 的点,而后把前面的值全设置为 9,达到最大值
var monotoneIncreasingDigits = function (n) {if(n<10) return n // 如果是个位数,间接返回 n
  const str = String(n)
  const len = str.length
  const arr = str.split('')
  let  flag = Infinity // 标记最初一个设置为 9 的下标,从这个下标之后的值,都得换成 9
  for(let i =len-1;i>=0;i--){if(arr[i-1]>arr[i]){
        // 如果前一位大于后一位,那么为了当增,须要将以后位减一,后一位换成 9
        flag = i
        arr[i-1] = arr[i-1] -1 
    }
  }

  for (let i = flag; i < len; i++) {arr[i] = 9
  }
  return Number(arr.join(''))
};

968. 监控二叉树

剖析

  1. 这里要求尽可能少的装置摄像头,然而改装的还是得装上,须要全笼罩,那么最好的方法必定是自底向上的装,因为层数越深,节点越多,所以自顶向上能缩小摄像头的装置
  2. 那么当初要尽可能让摄像头笼罩到每一个节点,这里节点 val 作为状态值,0 就是没有笼罩,1 就是装置摄像头笼罩,2 是没有装置然而在覆盖范围内
  3. 咱们晓得要尽可能的在有状态为 0 的叶子节点的 父节点 下来装置,这样就能够一次性笼罩到叶子节点,同时因为是自底向上的遍历,那么不须要思考更底层的笼罩,只须要思考以后节点和它的叶子节点即可
  4. 所以咱们用后续遍历的形式进行后续遍历,当咱们达到叶子节点时返回;
  5. 当咱们遇到叶子节点都为不为 0,也就是都在覆盖范围内的时候,如果存在叶子节点状态为 1,即以后节点也属于覆盖范围,须要更改状态为 2,而后 return 回去 — 这里用到了贪婪,也就是必须要有状态为 0 的叶子节点,才会去装置摄像头,保障摄像头的覆盖范围,进而保障数量最小
  6. 如果存在叶子节点的状态为 0,那么就必须在以后节点设置摄像头,也就将状态 root.val 设置为 1
  7. 当咱们自低向上遍历到了根节点,而后中断遍历的时候,还须要思考最初 root 节点
  8. 因为咱们之前的逻辑是依据叶子节点状态来判断以后节点的更改的,所以 root 节点很可能会因为叶子节点是笼罩值而没有进行任何的设置,这个时候 root 就可能是 0,所以如果 root 是 0 的话,还得再安一个摄像头
  9. 咱们最终的后果就是要保障整棵树的节点状态都不为 0 即可
  10. 工夫复杂度 O(n)
var minCameraCover = function (root) {if (!root) return 0;
  let ret = 0; // 装了多少摄像头
  const dfs = (root) => {if (!root.left && !root.right) return; // 达到叶子节点,间接返回,不加摄像头
    if (root.left) dfs(root.left);
    if (root.right) dfs(root.right);
    // 后序遍历,遇到父子节点存在摄像头,那就不须要加了
    if ((root.left && root.left.val !== 0  || !root.left) && (root.right && root.right.val !== 0 || !root.right)){if((root.left && root.left.val === 1) || (root.right && root.right.val === 1)){
            // 存在摄像头能力波及
            root.val = 2 // 波及到的
        }
        return 
    }
    // 必须要保障存在的子节点都曾经是 1 的时候,才能够释怀持续往上走
    root.val = 1; // 如果大家伙都没有装,那就我来装吧
    ret++;
  };
  dfs(root);
  return root.val === 0  ? ret+1 : ret 
};

正文完
 0