【算法系列】贪心策略详解（附LeetCode例题）_贪心算法 原理

一、贪心算法原理

1.贪心选择性质

第一个关键要素就是贪心选择性质：我们可以做出局部最优选择来构造全局最优解。也就是说，我们在做出选择时，总是以当前的情况为基础做出最优选择的，而不用考虑子问题的解。

这也是和动态规划最大的不同之处。在动态规划中，在每次做出一个选择的时候总是要将所有选择进行比较才能确定到底采用哪一种选择，而这种选择的参考依据是以子问题的解为基础的，所以动态规划总是采用自底向上的方法，先得到子问题的解，再通过子问题的解构造原问题的解。就算是自顶而下的算法也是先求出子问题的解。在贪心算法中，我们总是在原问题的基础上做出一个选择，然后求解剩下的唯一子问题，贪心算法从来都不依赖子问题的解，不过有可能会依赖上一次做出的选择，所以贪心算法是自顶而下的。

2.最优子结构

如果一个问题的最优解包含其子问题的最优解，那么就称这个问题具有最优子结构性质。

将子问题的最优解与贪心选择组合在一起就能生成原问题的最优解。

二、LeetCode例题

1、jump-game

（1）题目描述

给出一个非负整数数组，你最初在数组第一个元素的位置 ，数组中的元素代表你在这个位置可以跳跃的最大长度 判断你是否能到达数组最后一个元素的位置
例如

• A =[2,3,1,1,4], 返回 true.
• A =[3,2,1,0,4], 返回 false.

Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A =[2,3,1,1,4], returntrue.

A =[3,2,1,0,4], returnfalse.

（2）思路分析
本题需要处理好两个点：

• 第一是临界条件，在数组为空或者数组长度为1时，是直接满足题目为true的情况的；并且注意题目的要求是能够到达最后一个元素而不是刚好到达最后一个元素。
• 第二是要注意跳跃过程中经过0元素的情况，如果该元素不是位于数组末尾，那么跳跃就停止了，需要返回false，防止死循环。

（3）牛客网源代码

class Solution {
public:
    //n是数组长度
    bool canJump(int A[], int n) {
        //当数组为空时
        if(n==0)
            return false;
        //只有一个元素时直接符合要求
        if(n==1)
            return true;
        //多个元素的情况
        int i=0;
        while(i<n){
            //若跳跃过程中某个元素恰好是0则无法再继续移动
            if (!A[i])
				return false;
            //判定是否越界
            if(A[i]+i<n-1)
                i+=A[i];
            else if(A[i]+i>=n-1)
                return true;
            else
                return false;
        }
        
    }
};
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

（4）相关知识补充

• 数组函数传值问题：

数组传值传的是地址而不是整个数组；

• 数组大小确定问题：

尽量在数组外确定数组的大小，然后传入调用函数，

int arr[5]={1,2,3,4,5};
int size = sizeof(arr)/sizeof(arr[0]);
1
2

2、maximum-subarray

（1）问题描述：
请计算给出的数组（至少含有一个数字）中具有最大和的子数组（子数组要求在原数组中连续）

例如：给出的数组为[−2,1,−3,4,−1,2,1,−5,4], 子数组[−2,1,−3,4,−1,2,1,−5,4],具有最大的和:6.

Find the contiguous subarray within an array (containing at least one
number) which has the largest sum. For example, given the
array[−2,1,−3,4,−1,2,1,−5,4], the contiguous subarray[4,−1,2,1]has the
largest sum =6.

（2）思路分析

• 根据贪心策略的原则，要取得最大值就需要正值相加得到，任何负数或者和为负数的子数组段都是debuff。
• 基于这个原则我们设置最大值max和累加值sum，

if (max < sum) max = sum;
if (sum < 0) sum = 0;

max的值始终是最大的那一段子数组的和。

（3）牛客网源代码

class Solution {
public:
	int maxSubArray(int A[], int n) {//传入数组地址和大小
        //空数组处理
		if (n == 0)
			return 0;
        //最大值max和子数组值sum
		int sum = 0, max = A[0];
		for (int i = 0; i < n; i++) {
			sum += A[i];
			if (max < sum)
				max = sum;
			if (sum < 0)
				sum = 0;
		}
		return max;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3、minimum-window-substring

（1）题目描述
给出两个字符串S和T，要求在O（n）的时间复杂度内在S中找出最短的包含T中所有字符的子串。
例如：
S =“ADOBECODEBANC”
T =“ABC”
找出的最短子串为"BANC".

注： 如果S中没有包含T中所有字符的子串，返回空字符串 “”； 满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。

（2）思路分析
滑动窗口：

• 步骤一：先统计出子串T各字符的个数，一般输入字母串的字符只有 128 个，可以用大小为128的数组存储；
• 步骤二：初始化begin=end=0，end后移遍历s串，对于S中的每个遍历到的字母，都在数组中的映射值减1，如果减1后的映射值仍大于等于0，说明当前遍历到的字母是T串中的字母。使用一个计数器
  count，使其自减1，当计数为0时，说明begin到end之间已包含T中所有字符，记录窗口长度w； 步
• 骤三：begin开始后移移除元素，直到移除的字符是T中的字符则停止，此时T中有一个字符没被包含在窗口；
• 步骤四：重复步骤二，循环直到end到S中的最后一个字符；
• 步骤五：返回子串substr(head,minleng)。

（3）牛客网源代码

class Solution {
public:
	string minWindow(string S, string T) {
		//特殊情况处理
		if (S.length() < T.length() || S.length() == 0 || T.length() == 0)
			return "";

		int a[128] = {0};
		//统计T中各字符的个数
		for (int i = 0; i < T.length(); i++)
			a[T.at(i)]++;
		//注意S中未必包含T中所有字符，所以最小长度是S的长度加1
		int start = 0, end = 0, minLen = S.length() + 1, head = 0;
		int count = T.length();//计数器，标记窗口中还缺失的字符个数

		while (end < S.length()) {
			if (a[S.at(end)] > 0)
				count--;

			a[S.at(end)]--;
			end++;

			while (count == 0) {
				if (minLen > end - start) {//更新窗口最小值
					head = start;
					minLen = end - start;
				}
				if (a[S.at(start)] == 0)//窗口左边开始移除元素
					count++;

				a[S.at(start)]++;
				start++;
			}

		}
		if (minLen == S.length() + 1)
			return "";
		return S.substr(head, minLen);
	}
};

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

-----------------------------------------------------------------------------------------------------------------------------------------------------
如果本文对你有所帮助，请不要忘了点赞、收藏哦！！！
-----------------------------------------------------------------------------------------------------------------------------------------------------

三、相关参考

https://blog.csdn.net/qq_37098526/article/details/89360602
https://blog.csdn.net/Nibaby9/article/details/105054895