• 【LeetCode与《代码随想录》】贪心算法篇：做题笔记与总结-JavaScript版

    代码随想录

    贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

    文章目录

    455. 分发饼干

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

    大饼干可以满足大孩子也可以满足小孩子，在这里显然是满足大孩子最划算。因此饼干从大到小，如果饼干可以满足该孩子，ans++，否则，尝试是否可以满足小孩子。

    注意跳出循环的条件，当i<0||j<0

    var findContentChildren = function (g, s) {
    g.sort((a, b) => (a - b))
    s.sort((a, b) => (a - b))

    let ans = 0;
    for (let i = g.length - 1, j = s.length - 1; i >= 0, j >= 0;) {
        // g[i] 人 s[j]饼干
        if (s[j] >= g[i]) {
            ans++;
            i--, j--;
        } else {
            i--;
        }
        if (i < 0 || j < 0) break;
    }
    return ans;
};

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

    376. 摆动序列

    376. 摆动序列

    想要得到最长的摆动数组，需要保留一个上/下坡的头和尾，如：

    1，2，5，7，5，2，1

    • 1

    这里1，2，5，7都是上坡，但1，7的上坡比其他的好，因为7可以与后面组成更好的下坡——若是1，7，则后面想要下坡<7即可；若1，2，后面想要下坡则需要<2，条件比<7要小。反之亦然。

    但是，选择1，7还是1，2本质都是上坡，且长度都为2。因此，我们可以把问题简化为数组有多少个上下坡的变化。

    上面的样例就是一上一下，不管怎么选摆动数组都是3.

    我们用一个flag来记录前面是上坡还是下坡：前面是上坡且当前数组是下坡则ans++，反之亦然。

    注意要判断平坡，且从第一个上/下坡之后开始（flag值就记录第一个上/下坡）。

    var wiggleMaxLength = function(nums) {
    // flag表示是上行1还是下行0，-1表示一直平坡
    let ans=1,flag=-1;

    // 要找到第一次上行或下行
    let index=1;
    for(;index<nums.length;index++){
        if(nums[index]===nums[index-1]) continue;
        if(nums[index]>nums[index-1]) {
            flag=1;ans=2;
            break;
        }else{
            flag=0;ans=2;
            break;
        }
    }

    for(let i=index+1;i<nums.length;i++){
        // 上行
        if(nums[i]>nums[i-1]){
            if(!flag){
                ans++;flag=1;
            }
        }
        // 下行
        else if(nums[i]<nums[i-1]){
            if(flag){
                ans++;flag=0;
            }
        }
    }

    return ans;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34

    53. 最大子数组和

    53. 最大子数组和

    分为两种情况：数组全负和数组非全负。

    数组全负则选元素最大的那一个。
    数组非全负则一直累加并存最大值，若出现cnt<0则令cnt=0，相当于前面部分都不选。

    var maxSubArray = function (nums) {
    let ans = -10001;

    // 数组全为负数
    let flag = 0;
    nums.forEach(item => {
        if (item > 0) {
            flag = 1; return;
        }
    })

    if (!flag) {
        nums.forEach(item => {
            ans = Math.max(ans, item);
        })
        return ans;
    }

    let cnt = 0;

    // 贪心：如果一块连续部分是负数则舍去
    nums.forEach(item => {
        cnt += item;
        if (item >= 0) ans = Math.max(ans, cnt);
        else {
            if (cnt < 0) cnt = 0;
        }
    })
    return ans;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

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

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

    有prices数组：1,2,3,5,8

    最低买入最高卖出肯定是答案，即8-1=7

    注意，8-1=（2-1）+（3-2）+（5-3）+（8-5）。即前缀差中正值的和。

    若数组为：2,0,1,4，前缀差为-2,1,3，说明要在0时买入，在4时卖出。

    var maxProfit = function (prices) {
    // 前缀差 差值为正表示利润
    let ans = 0;
    for (let i = 1; i < prices.length; i++) {
        let temp = prices[i] - prices[i - 1]
        if (temp > 0) ans += temp;
    }
    return ans;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    55. 跳跃游戏

    55. 跳跃游戏

    var canJump = function (nums) {
    // cover表示可以覆盖的范围，也就是下标
    let cover = 0;
    if (nums.length === 1) return true;
    for (let i = 0; i <= cover; i++) {
        cover = Math.max(cover, i + nums[i]);
        if (cover >= nums.length - 1) return true;
    }
    return false;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    45. 跳跃游戏 II

    45. 跳跃游戏 II

    var jump = function (nums) {
    if (nums.length === 1) return 0;

    // ans步数,next本次可以到达的最大范围,max下一次可以到达的最大范围
    let ans = 0, next = 0, max = 0;
    for (let i = 0; i < nums.length; i++) {
        max = Math.max(max, i + nums[i]);
        // 当前已经达到本次可以达到的最大范围,到下一范围需要一步
        if (i === next) {
            ans++;
            next = max;
            if (max >= nums.length - 1) break;
        }
    }
    return ans;
};

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

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

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

    var largestSumAfterKNegations = function (nums, k) {
    // k是偶数可以相当于不变

    let f = [], z = []
    nums.forEach(item => {
        if (item < 0) f.push(item);
        else z.push(item);
    })

    f.sort((a, b) => (a - b));
    z.sort((a, b) => (a - b));

    if (k >= f.length) {
        k -= f.length;
        f = f.map(item => {
            return -item;
        })
        z.push(...f);
        f = []
    } else {
        for (let i = 0; i < k; i++) {
            let temp = -f[i];
            z.push(temp);
        }
        f = f.slice(k);
        k = 0;
    }

    f.sort((a, b) => (a - b));
    z.sort((a, b) => (a - b));

    if (k && k % 2) {
        // k是奇数
        z[0] = -z[0];
    }

    let ans = 0;
    if (f.length) {
        ans += f.reduce((pre, val) => {
            return pre + val;
        })
    }


    if (z.length) {
        ans += z.reduce((pre, val) => {
            return pre + val;
        })
    }

    return ans;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    134. 加油站

    134. 加油站

    n是1e5，暴力双层循环会超出时间限制。

    获得数组arr=gas-cost，arr[i]表示离开i地点剩余的油。
    遍历arr，计算区间和，但凡出现区间和<0，说明不能从这个区间的开头开始走（没油了），可能从此区间的下一个地方j开始走。于是从j开始计算区间和。维护这个j值：是可能的答案。

    计算arr的和，若arr的和>0，说明存在一个地方开始走能顺时针跑完。由题知，这个答案是唯一的。因此就是上面维护的j值。

    若arr<0，说明不存在答案。

    var canCompleteCircuit = function (gas, cost) {
    // 遍历 找gas-cost的区间和<0 答案就是此区间的下一个
    let curSum = 0, allSum = 0, ans = 0;

    for (let i = 0; i < gas.length; i++) {
        let temp = gas[i] - cost[i];
        curSum += temp
        allSum += temp
        // 此区间和为负，不能从这个区间和的头开始
        if (curSum < 0) {
            curSum = 0;
            ans = i + 1;//从此区间的下一个下标开始尝试
        }
    }

    if (allSum < 0) return -1;
    return ans;
};

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

    135. 分发糖果（困难）

    135. 分发糖果

    思路：这个讲得好

    省流：从左到右遍历一次，从右到左遍历一次。

    var candy = function (ratings) {
    let arr = new Array(ratings.length).fill(1)

    // 右边大于左边，即从左到右:右边大的糖果+1
    for (let i = 1; i < ratings.length; i++) {
        if (ratings[i] > ratings[i - 1]) {
            arr[i] = arr[i - 1] + 1;
        }
    }

    // 左边大于右边，即从右到左（右边最小）
    for (let i = ratings.length - 1; i >= 0; i--) {
        if (ratings[i - 1] > ratings[i]) {
            arr[i - 1] = Math.max(arr[i - 1], arr[i] + 1);
        }
    }

    let ans = arr.reduce((pre, val) => {
        return pre + val;
    })

    return ans;
};

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

    860. 柠檬水找零

    860. 柠檬水找零

    forEach中的return是跳出循环而不是函数的return。

    var lemonadeChange = function (bills) {
    let cnt5 = 0, cnt10 = 0;
    let flag = true;

    bills.forEach(item => {
        console.log(item, cnt5, cnt10)
        if (item === 5) {
            cnt5++;
        } else if (item === 10) {
            cnt10++;
            if (cnt5 > 0) cnt5--;
            else {
                flag = false; return;//这里的return是跳出bills的循环 而不是函数的return
            }
        } else if (item === 20) {
            if (cnt5 > 0 && cnt10 > 0) {
                cnt5--; cnt10--;
            } else if (cnt5 >= 3) {
                cnt5 -= 3;
            } else {
                flag = false; return;
            }
        }
    })

    return flag;
};

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

    406.根据身高重建队列

    406.根据身高重建队列

    想要队列queue中的内容满足：第 i 个人的身高为 hi ，前面 正好 有 ki 个身高大于或等于 hi 的人，只需要构造：

    • 前面的人都比第i个人高
    • 前面的人的个数是k[i]

    因此，需要先对身高从大到小排列，若身高相同，则对k从小到大排列。（如，[5,0]一定在[5,1]前）

    以[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]为例，排序后为：

    [ [ 7, 0 ], [ 7, 1 ], [ 6, 1 ], [ 5, 0 ], [ 5, 2 ], [ 4, 4 ] ]

    • 1

    开始构造：

    1. 对[ 7, 0 ]，前面有0个比它高的，因此他在第0个，这里的0即people[0][0]
    2. 对[ 7, 1 ]，前面有1个比它高的，因此他在第1个，这里的0即people[1][1]
    3. 对[ 6, 1 ]，前面有1个比它高的，因此他在第1个，这里的1即people[2][1]
    4. 对[ 5, 0 ]，前面有0个比它高的，因此他在第0个，这里的0即people[3][1]

    以此类推。

    每次的queue为：

    i为 0 , [ [ 7, 0 ] ]
i为 1 , [ [ 7, 0 ], [ 7, 1 ] ]
i为 2 , [ [ 7, 0 ], [ 6, 1 ], [ 7, 1 ] ]
i为 3 , [ [ 5, 0 ], [ 7, 0 ], [ 6, 1 ], [ 7, 1 ] ]
i为 4 , [ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 7, 1 ] ]
i为 5 , [ [ 5, 0 ], [ 7, 0 ], [ 5, 2 ], [ 6, 1 ], [ 4, 4 ], [ 7, 1 ] ]

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    总体代码：

    var reconstructQueue = function (people) {
    // 先看h,h从大到小,若h一样看k，从小到大
    people.sort((a, b) => {
        if (a[0] != b[0]) return b[0] - a[0];
        else return a[1] - b[1];
    })

    let queue = []

    for (let i = 0; i < people.length; i++) {
        queue.splice(people[i][1], 0, people[i]);
    }

    return queue;
};

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

    452. 用最少数量的箭引爆气球

    452. 用最少数量的箭引爆气球

    var findMinArrowShots = function (points) {
    let ans = 1;
    // 都从小到大排
    points.sort((a, b) => {
        if (a[0] != b[0]) return a[0] - b[0];
        else return a[1] - b[1];
    })

    let min = points[0][0], max = points[0][1];
    for (let i = 1; i < points.length; i++) {
        let a = points[i][0], b = points[i][1];
        if (a >= min && b <= max) {
            min = a
            max = b
        } else {
            if (a >= min && a <= max) min = a
            else if (b >= min && b <= max) max = b
            else {
                ans++;
                min = a, max = b;
            }
        }
    }
    return ans;
};

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

    435. 无重叠区间

    435. 无重叠区间

    var eraseOverlapIntervals = function (intervals) {
    intervals.sort((a, b) => {
        if (a[0] != b[0]) return a[0] - b[0]
        else return a[1] - b[1]
    })

    let ans = 0

    let min = intervals[0][0], max = intervals[0][1]
    for (let i = 1; i < intervals.length; i++) {
        let a = intervals[i][0], b = intervals[i][1]
        if (a >= max) {
            min = a, max = b
        } else {
            ans++;
            if (a >= min && b <= max) {
                min = a, max = b;
            }
        }
    }
    return ans;
};

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

    763.划分字母区间

    763.划分字母区间

    var partitionLabels = function (s) {
    let start = new Map(), end = new Map()

    for (let i = 0; i < s.length; i++) {
        // 注意：只有一个的情况
        end.set(s[i], i);
        if (!start.has(s[i])) start.set(s[i], i);
    }

    let arr = [...start.keys()], nums = []

    arr.forEach(item => {
        nums.push([start.get(item), end.get(item)])
    })

    // 从小到大
    nums.sort((a, b) => {
        if (a[0] != b[0]) return a[0] - b[0]
        else return a[1] - b[1]
    })

    let min = nums[0][0], max = nums[0][1], ans = []

    for (let i = 1; i < nums.length; i++) {
        let a = nums[i][0], b = nums[i][1]
        if (a > max) {
            ans.push(max - min + 1)
            min = a, max = b
        } else max = Math.max(max, b);
    }
    ans.push(max - min + 1)
    return ans;
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    56. 合并区间

    56. 合并区间

    var merge = function (intervals) {
    // 从小到大
    intervals.sort((a, b) => {
        if (a[0] != b[0]) return a[0] - b[0]
        else return a[1] - b[1]
    })

    let min = intervals[0][0], max = intervals[0][1], ans = []
    for (let i = 1; i < intervals.length; i++) {
        let a = intervals[i][0], b = intervals[i][1];
        if (a >= min && b <= max) continue;
        if (a > max) {
            ans.push([min, max])
            min = a, max = b;
        } else max = b;
    }

    ans.push([min, max])

    return ans;
};

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

    738.单调递增的数字

    738.单调递增的数字

    var monotoneIncreasingDigits = function (n) {
    let str = n.toString()
    str = str.split('').map(item => {
        return Number(item)
    });

    // 找到第一个不是递增的位置
    let flag;
    for (let i = str.length - 1; i >= 0; i--) {
        if (str[i - 1] > str[i]) {
            flag = i
            str[i - 1]--;
            str[i] = 9
        }
    }

    for (let i = flag; i < str.length; i++) str[i] = 9

    return Number(str.join(''))
};

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

    968.监控二叉树

    968. 监控二叉树

    困难先跳了。

  • 相关阅读:
    【LeetCode-中等题】513. 找树左下角的值
    C++符号
    vue开发网站--对文章详情页的接口内容进行处理
    PPOCR车牌定位模型推理后处理优化研究
    Data Catalog3.0:Modern Metadata for the Modern Data Stack
    1058 A+B in Hogwarts
    Python - GFPGAN + MoviePy 提高人物视频画质
    Java-JDBC快速上手
    java使用ws.schild.jave将视频转成mp4
    Vector底层源码
  • 原文地址：https://blog.csdn.net/karshey/article/details/132720260