贪心/分治算法

题目一览图

零、贪心/分治算法概述

**

一、贪心算法

类型概述

【贪心算法】本质是**选择每一阶段的局部最优，从而达到全局最优。
该算法的使用前提很明确：判断【局部最优】能否推出【整体最优】**。但是目前没有一个固定的套路判断这一点，所以很多时候需要先尝试一下，看看能不能使用贪心算法，如果不行尝试【动态规划】。

如果判断一道题可以用贪心算法后，采用以下步骤求解贪心问题：

1. 将问题分解成若干子问题，用贪心策略求解每一个【子问题最优解】。
2. 将【局部最优解】累计成【全局最优解】。

由于【贪心算法】没有固定的模板，所以给出几道常见的【贪心问题】，进而体会其中的感觉。

题型一 | 区间调度

题型串联

1 跳跃游戏

【概述】贪心算法
【题目描述**】
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
【题目示例**】

输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

【题目分析**】**
本题要求判断是否能达到最后一个位置。由于最终的目的是跳到终点，我们不用【递归】详细计算出所有选择的具体结果，只需要选择跳的最远的方式即可。所以可以使用【贪心算法】解决该问题，具体思路为：

• 设置变量 maxPosition ，记录当前可以跳到的最大范围。
• 设置索引 i 遍历数组，不停更新能跳到的最大距离，Math.max( maxPosition,i + nums[i])。
• 如果有一时刻 i>maxPosition 说明中间有一段禁跳区，连中间都跳不到，更别说到尾部。

• 当数组 nums 变量完全，判断 maxPosition 是否大于 nums.length - 1 ，如果能则能达到最后的位置。

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

  2 跳跃游戏 II

  【概述】贪心算法
  【题目描述**】
  给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
  【题目示例**】

  输入: [2,3,1,1,4]
  输出: 2
  解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
  

  【题目分析**】**
  本题要求计算达到最后一个位置最少跳几次。和【跳跃游戏】一样，可以使用【贪心算法】解决该问题，只是要计算跳跃次数。
  具体思路为：

• 设置变量 maxPosition ，记录当前可以跳到的最大范围。

• 设置索引 i 遍历数组，不停更新能跳到的最大距离，Math.max( maxPosition,i + nums[i])。

• 设置变量 end ，记录当前跳跃区间的结尾。也就是当前的 maxPosition 标记了 nums[0...end] 能跳的最远距离，中间没有办法再跳出 maxPosition ，所以每次达到这个 end ，跳跃次数加一，然后更新 end = maxPosition 。

  var jump = function(nums) {
  let maxPosition = 0 , end = 0 , count = 0;
  for( let i = 0 ; i < nums.length - 1 ; i++){
     maxP = Math.max(maxPosition, i + nums[i] );
     if( i === end ) end = maxPosition , count ++;
  }
  return count;
  };
  

  3 加油站

  【概述】贪心算法
  【题目描述**】
  在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
  【题目示例**】

  输入: [2,3,1,1,4]
  输出: 2
  解释: 跳到最后一个位置的最小跳跃数是 2。
  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
  

  【题目分析**】**
  本题要求汽车是否能跑完一周。和【跳跃游戏】一样，可以使用【贪心算法】解决该问题，只是要计算跳跃次数。
  具体思路为：

• 设置变量 maxPosition ，记录当前可以跳到的最大范围。

• 设置索引 i 遍历数组，不停更新能跳到的最大距离，Math.max( maxPosition,i + nums[i])。
• 设置变量 end ，记录当前跳跃区间的结尾。也就是当前的 maxPosition 标记了 nums[0...end] 能跳的最远距离，中间没有办法再跳出 maxPosition ，所以每次达到这个 end ，跳跃次数加一，然后更新 end = maxPosition 。

  var canCompleteCircuit = function(gas, cost) {
  let left = 0 , start = 0 , tGas = 0 , tCost = 0 ;
  for(let i = 0 ; i < gas.length ; i++){
     tGas += gas[i],tCost += cost[i];
     left += gas[i]-cost[i];
     if(left<0) left=0,start=i+1;
  }
  return tGas < tCost ? -1 : start;
  };
  

  二、分治算法

类型概述

**

题型串联

2 最长有效括号

【概述】栈问题
【题目描述**】
给你一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
【题目示例**】

输入: "()"
输出: true输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

【题目分析**】
本题要求得到有效的括号的最大长度。遇到这种问法，就知道要用一些算法了。本题可用动态规划或者贪心算法，为了利用栈的特性，我们采用贪心算法来处理问题。
【贪心算法】**的基本思路是：

• 设置栈 stk 用于存储【左括号】，res 记录最大长度。
• 设置索引 i 和 start ，前者用于遍历字符串，后者用于记录【合法串的初始位置】。
• 【合法串的初始位置】更新条件是当前元素破坏了括号的有效性，即【右括号】多于【左括号】，栈为空。
• 【最大长度】更新有两种情况：
  • 弹出一个【左括号】后，栈为空。说明从 start 到当前已经没有可匹配的【左括号】了，所以从start 到当前都合法，更新最大长度 Math.max(res,i-start) 。
  • 弹出一个【左括号】后，栈不为空。说明从 start 到当前还有可匹配的【左括号】，但是我们并不能确定它们真的可以被匹配，所以更新最大长度 Math.max(res,i-stk[stk.length-1]) 。

    var isScramble = function(s1, s2) {
    if( s1 === s2 ) return true;
    let bs1 = s1 , bs2 = s2;
    bs1 = bs1.split('').sort((a,b)=>a.localeCompare(b)).join('');
    bs2 = bs2.split('').sort((a,b)=>a.localeCompare(b)).join('');
    if( bs1 !== bs2 ) return false;
    const n = s1.length;
    for( let i = 1 ; i <= n - 1 ; i++){
    if( isScramble(s1.substr(0,i),s2.substr(0,i))&&
    isScramble(s1.substr(i),s2.substr(i))) return true;
    if( isScramble(s1.substr(0,i),s2.substr(n-i))&&
    isScramble(s1.substr(i),s2.substr(0,n-i))) return true;
    }
    return false;
    };