这些力扣 题目来源：AI推荐+karshey博主

目录

455. 分发饼干（通过）

56 合并区间（通过）

435. 无重叠区间（通过）

122. 买卖股票的最佳时机 II（通过）

605. 种花问题（通过）

---

455. 分发饼干（通过）

455. 分发饼干

关键是先从小到大排序

两个指针分别指向当前的儿童胃口和饼干大小：分为两种情况

1.儿童胃口<饼干大小：满足，比较下一个儿童和下一块饼干

2. 儿童胃口>饼干大小：不满足，这块饼干没用了（不能满足其他儿童，因为升序）。所以比较这个儿童和下一个饼干

/**
 * @param {number[]} g
 * @param {number[]} s
 * @return {number}
 */
var findContentChildren = function(g, s) {
    
    if(s.length==0) return 0;
    g.sort((a,b)=>a-b);
    s.sort((a,b)=>a-b);
    let count=0;
    let g_pointer =0;
    let s_pointer =0;
    while(g_pointer<g.length && s_pointer<s.length){
        if(g[g_pointer]<=s[s_pointer]){
            count++;
            s_pointer++;
            g_pointer++;
        } else {
            s_pointer++;
        }
    }
    return count;

};

56 合并区间（通过）

56 合并区间

排序很重要：先比左区间（左区间从小到大排序），然后比右区间（在左区间相同的情况下）

temp是当前和数组里面区间比较的临时区间

两种情况：

1. 如果临时区间可以和比较区间合并，临时区间更新为合并后的区间

2. 如果临时区间不可以和比较区间合并，该临时区间可以加到答案里面去。临时区间变成比较区间，继续循环

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */

intervals = [[2,3],[4,5],[6,7],[8,9],[1,10]];

var merge = function(intervals) {
    function overlap(arr1, arr2){
        let min = Math.min(arr1[0],arr2[0]);
        let max = Math.max(arr1[1],arr2[1]);
        let ans=[];
        ans.push(min);
        ans.push(max);
        return ans;
    }

    function isOverlap(arr1,arr2){
        if(arr1[0]<=arr2[0] && arr1[1]>=arr2[0] ) return true;
        if(arr1[0]>=arr2[0] && arr1[1]<=arr2[1] ) return true;
        if(arr1[0]<=arr2[1] && arr1[1]>=arr2[1] ) return true;

        if(arr2[0]<=arr1[0] && arr2[1]>=arr1[0] ) return true;
        if(arr2[0]>=arr1[0] && arr2[1]<=arr1[1] ) return true;
        if(arr2[0]<=arr1[1] && arr2[1]>=arr1[1] ) return true;

        return false;
    }
    //排序重要，决定第一个数组必定是下标最小的
    intervals.sort((a,b)=>{return a[0]-b[0]==0?a[1]-b[1]:a[0]-b[0]})

    // for(let i=0;i<intervals.length;i++){
    //     console.log(intervals[i]);
    // }

    let ans = [];
    let temp = intervals.shift();
    for(let i=0;i<intervals.length;i++){
        if(isOverlap(temp,intervals[i])) {
            temp = overlap(temp, intervals[i]);
        } else {
            ans.push(temp);
            temp = intervals[i];
        }
    }
    ans.push(temp);
    return ans;
};

console.log(merge(intervals));

435. 无重叠区间（通过）

435. 无重叠区间

首先排序：区间左开口越小越在前面，区间左开口相同的时候，右开口越大越在前面

分为三种情况：（区间A和区间B：1.区间A覆盖区间B，2.区间A和区间B部分相交，3.区间A和区间B完全不相交  ）

用count表示最少需要删除的区间

1. 区间A覆盖区间B：此时应该删除区间A。这样可以最大程度的避免它与其他区间相交。下一个用来比较的区间是B。

2. 区间A和区间B部分相交：此时应该删除区间B，这样可以避免区间B与其他区间相交。下一个用来比较的区间是A。

3. 区间A和区间B完全不相交：区间A再无和其他区间相交的可能，下一个用来比较的区间转移到区间B。

/**
 * @param {number[][]} intervals
 * @return {number}
 */

intervals = [
  [1, 2],
  [2, 3],
  [3, 4],
  [1, 3],
];
var eraseOverlapIntervals = function (intervals) {
  intervals.sort((a, b) => {
    return a[0] - b[0] == 0 ? b[1] - a[1] : a[0] - b[0];
  });

  let count = 0;
  let temp = intervals[0];
  for(let i=1;i<intervals.length;i++){
    if(temp[1]<=intervals[i][0]){
        temp=intervals[i];
        continue;
    }
    if(temp[1]>=intervals[i][1]){
        count++;
        temp=intervals[i];
        continue;
    } 
    if(temp[1]>intervals[i][0]){
        count++;
        continue;
    }
  }

  return count;

  for (let i = 0; i < intervals.length; i++) {
    console.log(intervals[i]);
  }
};

eraseOverlapIntervals(intervals);

122. 买卖股票的最佳时机 II（通过）

122. 买卖股票的最佳时机 II

相对低点和当前股价比较分为两种情况：

1. 相对低点小于当前股价：可以卖股票。更新相对低点为当前股价

2. 党对低点高于当前股价：不买股票。更新相对低点为当前股价

/**
 * @param {number[]} prices
 * @return {number}
 */

// prices = [7,1,5,3,6,4]
// prices = [1,2,3,4,5]
prices = [7,6,4,3,1]

var maxProfit = function(prices) {
    let profit = 0;
    if(prices.length<=1) return profit;

    let low = prices[0];
    for(let i=1;i<prices.length;i++){
        if(low<prices[i]) {
            profit+=prices[i]-low;
            low=prices[i];
        } else {
            low=prices[i]
        }
    }
    return profit
};
console.log(maxProfit(prices));

605. 种花问题（通过）

605. 种花问题

影响能否种花的因素有三个：1.前面是否有花、2.后面是否有花、3.默认序列是否有花

从起点开始遍历

1. 先判断后面是否有花：后面如果是数组尽头。需要处理边界问题

2. 然后判断当前位置是否有花：（又分为两种小情况）

a. 当前位置有花：不能种植，而且还需要更新前面是否有花的标记

b. 当前没有花：（判断前面和否面是否有花：符合条件则种植，并且标记前一个位置有花为以后做好准备。如果因为前面后面有花没办法种植，在进入下一轮前标记前一个位置有花）

/**
 * @param {number[]} flowerbed
 * @param {number} n
 * @return {boolean}
 */
var canPlaceFlowers = function(flowerbed, n) {
    let count=0;
    let prevIsNotAFlower = true;
    let afterIsNotAFlower = true;
    for(let i=0;i<flowerbed.length;i++){
        if(i+1<flowerbed.length){
            if(flowerbed[i+1]==1) afterIsNotAFlower=false;
            else afterIsNotAFlower=true;
        } else {
            afterIsNotAFlower=true; //后面没有树了
        }

        if(flowerbed[i]==1) {
            prevIsNotAFlower =false;
            continue;
        } else {
            if(afterIsNotAFlower&&prevIsNotAFlower) {
                count++;
                prevIsNotAFlower = false;
            } else {
                prevIsNotAFlower=true;
            }
        }
    }
    return count>=n?true:false;
};