算法：贪心算法的原理和基本思路_深度优先算法,广度优先算法,贪心算法的主要思路

写在前面

本篇开始总结贪心算法的原理和思路，本篇主要是对贪心有一个基本的认知和做题的逻辑思路，在理清逻辑的前提下进行解题会轻松许多，后续进行题量的累积以获得更多的算法思路和解题经验

贪心算法

什么是贪心算法？

贪心算法是很重要的一类算法，它解题的核心是找到一种贪心的策略，能够将解决问题的策略从局部最优转换成全局最优

如何解决贪心问题？

1. 把解决问题的步骤可以划分为若干步
2. 解决每一个步骤的时候，都选择看起来是一个最优的解法
3. 希望可以得到全局的最优解

贪心算法的特点？

1. 从贪心策略提出的角度来讲：

• 贪心策略的提出是没有固定的标准和模板
• 贪心策略每道题都可能会不一样

2. 从贪心策略正确性的角度来讲：

• 贪心策略并不一定是正确的
• 因此正确的贪心策略是需要被证明的

初步认知

下面从几个经典的问题，从贪心的角度来看题

找零问题

这是一类很经典的题目，例如现在去超市买东西，售货员收到了50元的纸币，物品是4元钱，售货员要找出46元，现在她有20,10,5,1元纸币若干张，现在要让找出的纸币数量是最少的，应该如何解决？

对待这个问题，如果直观去想其实是很简单的，只需要2张20，1张5元，1张1元即可凑够46元，但是这是直观去想的，如果转换成代码逻辑？

如果考虑的贪心策略是，将需要的钱数从面额大的情况开始找，每次都在大面额的纸币找不到的前提下再去找次大的纸币，根据这样的贪心策略的确可以找到一个方案，但是这个方案的正确性却有待考证，放在这个题当然正确，但如果是下面的题型：

给定某国家纸币面额有20元，18元，10元，5元，1元，现在要找够36元，如果再使用刚才的思路，那么就应该要找1张20元，1张10元，1张5元，1张1元，但是实际上，只需要2张18元的纸币就足够了，这说明上面的算法策略是有问题的，不可以使用这样的算法策略

最短路径问题

现在给定一个3x3的表格，其中每个格子的数据代表距离，现在要求从格子的左上角走到右下角最少需要走多少距离？

现在想一种贪心策略，每次比较格子四周的数值，选择最小的那个数值去寻路，那么对于上图来说可以寻路出这样的路

但是这样的路很明显不如走另外一个直角路，这说明贪心策略也是有问题的，这也进一步的说明了现在寻找出的贪心策略并不一定是正确的，还需要进行后续的步骤才能说明这个贪心策略是正确的

下面使用几个例题来解决上面的问题：

典型例题

柠檬水找零

贪心策略

对于这个题来说，贪心策略就是给五元就收下，给十元就找五元，给二十元就找十元和五元，这是正确的贪心策略，如果给二十元找三张五元这就是一个错误的贪心策略

代码解析

class Solution 
{
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        int five=0,ten=0;
        for(auto x : bills)
        {
            if(x==5)
            {
                five++;
            }
            else if(x==10)
            {
                if(five==0)
                {
                    return false;
                }
                else
                {
                    five--;
                    ten++;
                }
            }
            else
            {
                if(ten && five)
                {
                    ten--;
                    five--;
                }
                else if(five>=3)
                {
                    five-=3;
                }
                else
                {
                    return false;
                }
            }
        }
        return true;
    }
};
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

将数组减半的最少操作次数

本题的贪心策略也比较简单，直接找最大的数减半

唯一要注意的是，这里可以采用一个大根堆的数据结构来解决，代码实现也很容易

class Solution 
{
public:
    int halveArray(vector<int>& nums) 
    {
        priority_queue<double> heap;
        double sum=0.0;
        for(auto x : nums)
        {
            heap.push(x);
            sum+=x;
        }
        sum /= 2;
        int count=0;
        while(sum>0)
        {
            double t=heap.top()/2;
            heap.pop();
            sum-=t;
            count++;
            heap.push(t);
        }
        return count;
    }
};
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

最大数

此题的贪心策略是，使用一个比较函数进行比较，根据字符串中的先后大小顺序选出可以组成的最大的数，贪心的比较策略就是让字符串两两相加，谁大选谁即可

class Solution
{
public:
	string largestNumber(vector<int>& nums)
	{
		vector<string> v;
		for (auto x : nums)
		{
			v.push_back(to_string(x));
		}
		sort(v.begin(), v.end(), [](const string& s1, const string& s2)
			{
				return (s1 + s2) > (s2 + s1);
			});

		string res;
		for (auto x : v)
		{
			res += x;
		}
		if (res[0] == '0')
		{
			return "0";
		}
		return res;
	}
};
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

摆动序列

本题的贪心策略是找拐点，对于这个题来说，如果把数组中的元素放到一个折线图中，那么贪心策略就是找到每一次的拐点即可，那么根据这个原理只需要统计出每一次的拐点就可以

对于统计拐点的思路来说，定义一个left和right状态值，表示的是现在这个情况下下一个目标值的状态和现在是否一样，如果一样则说明不是拐点，如果不一样就说明状态由递增转换为递减或者是由递减转换为递增，基于这个原理就可以进行代码的编写解决问题了

class Solution 
{
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int left=0,right=0,count=0;
        if(nums.size()<2)
        {
            return nums.size();
        }
        for(int i=0;i<nums.size()-1;i++)
        {
            right=nums[i+1]-nums[i];
            if(right==0)
            {
                continue;
            }
            if(left*right<=0)
            {
                count++;
            }
            left=right;
        }
        return count+1;
    }
};
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