初步了解贪心

初步了解贪心

什么是贪心？

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择，就能得到问题的答案。贪心算法需要充分挖掘题目中条件，没有固定的模式，解决有贪心算法需要一定的直觉和经验。

贪心算法不是对所有问题都能得到整体最优解。能使用贪心算法解决的问题具有「贪心选择性质」。「贪心选择性质」严格意义上需要数学证明。能使用贪心算法解决的问题必须具备「无后效性」，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

例一  种花问题（leetcode 605 题）

https://leetcode-cn.com/problems/can-place-flowers/https://leetcode-cn.com/problems/can-place-flowers/题目描述：

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true，不能则返回false。

示例1：

示例2：

题目分析：

 举一些例子来找规律

题解代码：

暴力思路：

class Solution {
public:
    bool canPlaceFlowers(vector& flowerbed, int n) {
        int sum=0,ju=0;
        int q,p;

        if(flowerbed.size()==1&&flowerbed[0]==0){
            return true;
        }

        for(int i=0;i=n){
            return true;
        }else{
            return false;
        }
    }
};

 优化后：

class Solution {
public:
    bool canPlaceFlowers(vector& flowerbed, int n) {
        int count = 0;
        int m = flowerbed.size();
        int prev = -1;

        for (int i = 0; i < m; ++i) {
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                    count += i / 2;
                } else {
                    count += (i - prev - 2) / 2;
                }
                prev = i;
            }
        }

        if (prev < 0) {
            count += (m + 1) / 2;
        } else {
            count += (m - prev - 1) / 2;
        }


        return count >= n;
    }
};

例二   跳跃游戏（leetcode 55 题）

https://leetcode-cn.com/problems/jump-game/https://leetcode-cn.com/problems/jump-game/题目描述：

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例1：

 示例2：

 题目分析：

1.如果某一个作为起跳点 的格子可以跳跃的距离是3，那么表示后面 3 个格子都可以作为起跳点。
2.可以对每一个能作为起跳点 的格子都尝试跳一次，把能跳到最远的距离不断更新。
3.如果可以一直跳到最后，就了。

题解代码：

class Solution {
public:
    bool canJump(vector& nums) {
        int n = nums.size();
        int lmax = 0;

        for (int i = 0; i < n; ++i) {
            if (i <= lmax) {
                lmax = max(lmax, i + nums[i]);
                if (lmax >= n - 1) {
                    return true;
                }
            }
        }

        return false;
    }
};

例三   跳跃游戏||  （leetcode 45 题）

https://leetcode-cn.com/problems/jump-game-ii/https://leetcode-cn.com/problems/jump-game-ii/题目描述：

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

假设你总是可以到达数组的最后一个位置。

示例1：

示例2：

题目分析：

维护一个max表示step步数下能够跳到的最远位置
每次遍历当前位置到max位置（拷贝），并更新max=fmax(max, i+nums[i])

也就是每次在上次能跳到的范围内选择一个能跳的最远的位置（也就是能跳到max_far位置的点）作为下次的起跳点 ！

题解代码：

int jump(vector &nums)
{
    int ans = 0;
    int start = 0;
    int end = 1;

    while (end < nums.size())
    {
        int maxPos = 0;

        for (int i = start; i < end; i++)
        {
            maxPos = max(maxPos, i + nums[i]);
        }


        start = end;      // 下一次起跳点范围开始的格子
        end = maxPos + 1; // 下一次起跳点范围结束的格子
        ans++;            // 跳跃次数
    }


    return ans;
}

小总结：

贪心算法在对问题求解时，总是做出再当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是某种意义上的局部最优解。

贪心算法的基本思路：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。