Javascript算法——贪心算法（一）

贪心算法详解（JavaScript）（局部最优->全局最优）

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下的最优选择（局部最优）的算法设计方法。通过局部最优解的累积，试图最终达到全局最优解。尽管贪心算法并不总能保证得到最优解，但它对某些问题（如优化类问题）非常有效。

贪心算法的核心思想

1. 问题分解：将问题分解成多个子问题。
2. 贪心选择性质：对每个子问题，做出一个局部最优选择。
3. 无后效性：当前的选择不会影响后续的决策，或者即使受到影响，也不会导致最优解的丢失。
4. 重复上述步骤：直到所有子问题解决。

贪心算法的实现步骤

1. 分析问题是否适合贪心：问题是否满足贪心选择性质和无后效性。
2. 构造贪心策略：确定如何在每一步选择局部最优解。
3. 验证贪心策略的正确性：证明或推导出贪心策略能够得到问题的最优解。
4. 实现代码：利用循环、排序、优先队列等工具编写代码。

经典贪心算法案例及实现

案例 1：分发饼干

问题描述：
有两组数据，分别是孩子的胃口数组 g 和饼干大小数组 s。每个孩子只能吃一个饼干，只有当饼干的大小 ≥ 孩子的胃口时，该饼干才能满足该孩子。求最多有多少孩子可以满足。

贪心思路：

1. 将孩子的胃口和饼干大小排序。
2. 每次将最小的饼干分配给最小胃口的孩子（局部最优）。
3. 如果当前饼干不能满足孩子，则尝试下一块饼干。

代码实现：

function findContentChildren(g, s) {
    // 排序胃口和饼干大小
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);

    let child = 0;
    let cookie = 0;

    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) {
            // 当前饼干可以满足当前孩子
            child++;
        }
        // 尝试分配下一块饼干
        cookie++;
    }

    return child;
}

// 示例
console.log(findContentChildren([1, 2, 3], [1, 1])); // 输出: 1
console.log(findContentChildren([1, 2], [1, 2, 3])); // 输出: 2

案例 2：跳跃游戏

问题描述：
给定一个非负整数数组，每个元素表示你在该位置最多能跳多远。判断是否可以从数组的第一个位置跳到最后一个位置。

贪心思路：

1. 维护一个变量 maxReach 表示当前能够到达的最远位置。
2. 遍历数组：
   • 如果当前索引大于 maxReach，则无法跳到当前位置。
   • 否则更新 maxReach 为当前索引加上跳跃步数。
3. 如果遍历结束时 maxReach 大于等于数组最后一个位置，则说明可以到达。

代码实现：

function canJump(nums) {
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        if (i > maxReach) {
            // 当前索引无法到达
            return false;
        }
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    return true;
}

// 示例
console.log(canJump([2, 3, 1, 1, 4])); // 输出: true
console.log(canJump([3, 2, 1, 0, 4])); // 输出: false

案例 3：区间调度问题

问题描述：
给定多个区间，求最多能选择不重叠的区间数量。

贪心思路：

1. 按照区间的结束时间升序排序（局部最优：优先选择结束时间最早的区间）。
2. 遍历区间列表，每次选择当前区间与上一次选择的区间不重叠的区间。

代码实现：

function intervalSchedule(intervals) {
    if (intervals.length === 0) return 0;

    // 按结束时间升序排序
    intervals.sort((a, b) => a[1] - b[1]);

    let count = 1; // 至少有一个区间被选中
    let end = intervals[0][1];

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            // 当前区间与上一个区间不重叠
            count++;
            end = intervals[i][1];
        }
    }

    return count;
}

// 示例
console.log(intervalSchedule([[1, 3], [2, 4], [3, 5]])); // 输出: 2
console.log(intervalSchedule([[1, 2], [2, 3], [3, 4], [1, 3]])); // 输出: 3

贪心算法的优缺点

优点：

• 简单高效：解决问题的步骤清晰，易于实现。
• 局部最优：很多时候可以快速找到接近最优的解。

缺点：

• 适用性有限：不适用于所有问题，特别是需要全局视野的问题。
• 无法回溯：一旦做出选择，就不能回退检查其他可能性。

贪心算法适用场景

1. 贪心选择性质：整体最优解可以通过一系列局部最优解构成。
2. 无后效性：某一步的决策不会影响后续步骤的最优性。

常见的适用问题包括：最小生成树（Prim、Kruskal 算法）、最短路径问题（Dijkstra 算法）、区间调度、活动选择等。

希望这些内容对你理解和使用贪心算法有所帮助！ 😊

贪心算法vs动态规划算法

贪心算法与动态规划算法的比较详解

贪心算法和动态规划是两种常用的算法设计方法，它们各自适用于不同类型的问题，主要区别在于解决问题的思路和适用场景。以下是两者的详细比较：

1. 核心思想

2. 适用问题

3. 实现复杂度

4. 解决过程

5. 优势与局限性

贪心算法与动态规划的对比表格总结

两种算法的使用场景总结

1. 贪心算法：

   • 问题适合贪心选择，且有无后效性。
   • 需要快速计算的近似解或简单解。
   • 例子：找零问题、最小生成树、区间调度。

2. 动态规划：

   • 问题有重叠子问题和最优子结构。
   • 不确定贪心是否适用，但需要保证最优解。
   • 例子：背包问题、最长公共子序列、股票买卖问题。

总结：贪心算法和动态规划在解决问题时各有侧重。对于简单、高效的场景可以优先考虑贪心算法，而对于复杂、全局优化的问题则更适合动态规划。

摆动序列

核心：考虑这三种情况！！！

/**
 * @param {number[]} nums
 * @return {number}
 */
var wiggleMaxLength = function(nums) {
    // let len=nums.length;
    // let strLen=0;
    // let preDiff=0,curDiff=0,count=0;
    // //判断字符序列是否为长度,是偶数的话
    // //还需比较最后两个数组的大小是否大于0
    // let flag=nums.length%2;
    // for(let i=0,j=1;j<nums.length;i++,j++){
    //     curDiff=nums[j]-nums[i];
    //     if(preDiff>0&&curDiff<0){
    //         count++;
    //     }
    //     if(j===nums.length-1&&!flag&&curDiff>0){
    //         strLen=count>=1?2*count+2:2;
    //     }else{
    //         strLen=count>=1?2*count+1:2;
    //     }
    //     preDiff=curDiff;
    // }
    // return  strLen;

    //考虑平坡、单调平坡和收尾元素
    //默认尾部元素有个坡
    //preDiff=0可起到前方有个和开始元素值一样的虚拟元素
    if(nums.length<=1)return nums.length;
    let preDiff=0,curDiff=0,res=1;
    //i<nums.length-1  默认尾部元素有个坡
    for(let i=0;i<nums.length-1;i++){
        curDiff=nums[i+1]-nums[i];
        if((curDiff>0&&preDiff<=0)||(curDiff<0&&preDiff>=0)){
            res++;
            //在这赋值curDiff，表示只有坡度方向变化时才更新preDiff
            //防止在单调平坡上出现error
            preDiff=curDiff;
        }
    }
    return res;
};

最大子序列和

核心：怎样用代码重新开始位置，其实此题返回值，直接将前面累加和赋值0就行！ if(curSum<0)curSum=0;

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // let res=-Infinity;
    let res=[];
    for(let i=0;i<nums.length;i++){
        curSum+=nums[i];
        if(curSum>res)res=curSum;
        //!!!核心，更换起始位置就是把当前curSum赋值为0就行！
        if(curSum<0)curSum=0;
    }
    return res; 

    // for(let i=0;i<nums.length;i++){
    //     let curSum=0;
    //     for(let j=i;j<nums.length;j++){
    //         curSum+=nums[j];
    //         res.push(curSum);
    //     }
    // }
    // let maxArr=res.sort((a,b)=>b-a)[0];
    // return maxArr;
        
};