贪心算法详解（JavaScript）（局部最优->全局最优）
贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下的最优选择（局部最优）的算法设计方法。通过局部最优解的累积，试图最终达到全局最优解。尽管贪心算法并不总能保证得到最优解，但它对某些问题（如优化类问题）非常有效。
贪心算法的核心思想
- 问题分解：将问题分解成多个子问题。
- 贪心选择性质：对每个子问题，做出一个局部最优选择。
- 无后效性：当前的选择不会影响后续的决策，或者即使受到影响，也不会导致最优解的丢失。
- 重复上述步骤：直到所有子问题解决。
贪心算法的实现步骤
- 分析问题是否适合贪心：问题是否满足贪心选择性质和无后效性。
- 构造贪心策略：确定如何在每一步选择局部最优解。
- 验证贪心策略的正确性：证明或推导出贪心策略能够得到问题的最优解。
- 实现代码：利用循环、排序、优先队列等工具编写代码。
经典贪心算法案例及实现
案例 1：分发饼干
问题描述：
有两组数据，分别是孩子的胃口数组 g 和饼干大小数组 s。每个孩子只能吃一个饼干，只有当饼干的大小 ≥ 孩子的胃口时，该饼干才能满足该孩子。求最多有多少孩子可以满足。
贪心思路：
- 将孩子的胃口和饼干大小排序。
- 每次将最小的饼干分配给最小胃口的孩子（局部最优）。
- 如果当前饼干不能满足孩子，则尝试下一块饼干。
代码实现：
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：跳跃游戏
问题描述：
给定一个非负整数数组，每个元素表示你在该位置最多能跳多远。判断是否可以从数组的第一个位置跳到最后一个位置。
贪心思路：
- 维护一个变量
maxReach表示当前能够到达的最远位置。 - 遍历数组：
- 如果当前索引大于
maxReach，则无法跳到当前位置。 - 否则更新
maxReach为当前索引加上跳跃步数。
- 如果当前索引大于
- 如果遍历结束时
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：区间调度问题
问题描述：
给定多个区间，求最多能选择不重叠的区间数量。
贪心思路：
- 按照区间的结束时间升序排序（局部最优：优先选择结束时间最早的区间）。
- 遍历区间列表，每次选择当前区间与上一次选择的区间不重叠的区间。
代码实现：
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
贪心算法的优缺点
优点：
- 简单高效：解决问题的步骤清晰，易于实现。
- 局部最优：很多时候可以快速找到接近最优的解。
缺点：
- 适用性有限：不适用于所有问题，特别是需要全局视野的问题。
- 无法回溯：一旦做出选择，就不能回退检查其他可能性。
贪心算法适用场景
- 贪心选择性质：整体最优解可以通过一系列局部最优解构成。
- 无后效性：某一步的决策不会影响后续步骤的最优性。
常见的适用问题包括：最小生成树（Prim、Kruskal 算法）、最短路径问题（Dijkstra 算法）、区间调度、活动选择等。
希望这些内容对你理解和使用贪心算法有所帮助！ 😊
贪心算法vs动态规划算法
贪心算法与动态规划算法的比较详解
贪心算法和动态规划是两种常用的算法设计方法，它们各自适用于不同类型的问题，主要区别在于解决问题的思路和适用场景。以下是两者的详细比较：
1. 核心思想
| 方面 | 贪心算法 | 动态规划 |
|---|---|---|
| 基本思路 | 每一步都选择当前状态下的局部最优解。 | 将问题分解成多个子问题，利用子问题的解构造全局最优解。 |
| 全局性 | 通过局部最优推导全局最优解。 | 通过递推式逐步解决子问题以达到全局最优解。 |
2. 适用问题
| 方面 | 贪心算法 | 动态规划 |
|---|---|---|
| 问题类型 | 适用于具有贪心选择性质和无后效性的优化问题。 | 适用于有重叠子问题和最优子结构性质的问题。 |
| 典型问题 | 活动选择、最小生成树、最短路径（Dijkstra）。 | 背包问题、最长公共子序列、最长递增子序列。 |
3. 实现复杂度
| 方面 | 贪心算法 | 动态规划 |
|---|---|---|
| 实现难度 | 相对简单，直接选择当前最优解即可。 | 需要设计状态、递推关系和表格存储。 |
| 时间复杂度 | 通常为 ( O(n \log n) ) 或 ( O(n) )。 | 通常为 ( O(n^2) ) 或更高。 |
| 空间复杂度 | 一般为 ( O(1) )。 | 需要额外的存储空间（例如表格），通常为 ( O(n^2) )。 |
4. 解决过程
| 方面 | 贪心算法 | 动态规划 |
|---|---|---|
| 过程描述 | 通过排序、优先队列等工具选择局部最优。 | 使用状态转移方程递推计算，通常自底向上。 |
| 回溯性 | 无法回溯，一旦选择即固定。 | 可以通过存储子问题结果进行回溯。 |
5. 优势与局限性
| 方面 | 贪心算法 | 动态规划 |
|---|---|---|
| 优势 | 高效、简单，适用于实时计算。 | 可以保证得到全局最优解。 |
| 局限性 | 不保证全局最优解，适用问题较少。 | 复杂度较高，消耗更多的时间和空间资源。 |
贪心算法与动态规划的对比表格总结
| 属性 | 贪心算法 | 动态规划 |
|---|---|---|
| 选择方式 | 每一步选择局部最优解 | 依赖子问题结果，通过递推求解全局最优解 |
| 适用问题特性 | 贪心选择性质、无后效性 | 重叠子问题、最优子结构 |
| 时间复杂度 | 通常较低 | 通常较高 |
| 空间复杂度 | 通常为 ( O(1) ) | 需要额外存储，通常为 ( O(n^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;
};
