JavaScript 刷 LeetCode 拿 offer- 贪心算法

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}

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};

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};

 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;  };

 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 }

/** * @分析 -- 已知能到达位置，求最少跳跃次数 * 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++        }    }}    

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;};

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;};

 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};

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}

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};

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};

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);};

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
 };

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)

 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};

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]])

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}

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}

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'))

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]]  ));

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(''))};

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 };