【数据结构】常见的贪心算法使用场景

朴灿烈づ我的快乐病毒、 2022-05-16 06:27 158阅读 0赞

## 0、贪心算法引入 ##

详情请见：[贪心算法][Link 1]

## 一、摇摆序列 ##

**1.1题目：**  
==========author daiV  
一个整数序列，如果两个相邻元素的差正好正负交替出现，则称该序列为摇摆序列。  
一个小于两个元素的序列直接为摇摆序列；  
eg：\{1,7,4,9,2,5\}，相邻元素的差为\{6，-3,5，-7,3\}，该序列为摇摆序列  
eg: \{1,4,7,2,5\},相邻元素的差为\{3,3，-5,3\}；则不是摇摆序列

求：给定一个随机序列，求这个序列满足摇摆序列定义的最长序列的长度  
如：输入\{1,17,5,10,13,15,10,5,16,8\}结果为7（1,17,5,15,5,16,8）

**1.2思想实现**  
利用状态机思想来解决：  
begin

up              down

\*\*1.3程序实现 \*\*

#include<iostream>
    #include<vector>
    using namespace std;
    
    class solution 
    {
    public :
    	int wiggleMaxLength(std::vector<int> &nums)
    	{
    		if(nums.size()<2)
    		{
    			return nums.size();
    		}
    		static const int BEGIN = 0;
    		static const int UP = 1;
    		static const int DOWN = 2;
    		int STATE = BEGIN;
    		int max_length  = 1;
    
    		for(int  i = 1; i< nums.size();i++)
    		{
    			switch(STATE)
    			{
    			case BEGIN:
    				{
    					if(nums[i] > nums[i-1])
    					{
    						STATE = UP;
    						max_length++;
    					}
    					else if(nums[i]<nums[i-1])
    					{
    						STATE = DOWN;
    						max_length++;
    					}
    				}break;
    
    			case UP:if(nums[i] <nums[i-1])
    					{
    						STATE = DOWN;
    						max_length++;
    					}break;
    
    			case DOWN:if(nums[i] >nums[i-1])
    					{
    						STATE = UP;
    						max_length++;
    					}break;
    			}
    		}
    		return max_length;
    
    	}
    };
    int main()
    {
    	std::vector<int> nums;
    	nums.push_back(1);
    	nums.push_back(17);
    	nums.push_back(5);
    	nums.push_back(10);
    	nums.push_back(13);
    	nums.push_back(15);
    	nums.push_back(10);
    	nums.push_back(5);
    	nums.push_back(16);
    	nums.push_back(8);
    	solution solve;
    	int max_length = solve.wiggleMaxLength(nums);
    
    	printf("该序列的最大子序列长度为:%d \n",max_length);
    
    	return 0;
    }

\*\*1.4程序结果 \*\*  
![70][]

## 二、移除K个数字求最小值 ##

**2.1题目：**  
==author daiV=  
已知一个使用字符串表示的非负整数num，将num中的k个数字移除，  
求移除K个数字后，可以获得的最小的可能的新数字  
比如：  
输入num=“1432219”，k = 3 =======》1219

**2.2思想实现:**  
将字符串中的字符转换为数字，然后再顺序遍历这组数，将其放在栈中，每次遍历到一个数，将其与栈顶元素比较，如果小于栈顶元素，则将栈顶元素弹出，将该元素插入栈顶；  
\*\*2.3程序实现 \*\*

#include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    
    class solution
    {
    public:
    	std::string  removeKdigits(std::string num, int k)
    	{
    		std::vector<int> s;
    		std::string result = "";
    		for(int i = 0; i<num.length();i++)
    		{
    			int number = num[i]-'0';
    			while(s.size()!= 0 &&s[s.size()-1]>number&& k>0 )//注意：s[s.size()-1] > number,后一个数字比前一个数字小时
    			{
    				s.pop_back();
    				--k;
    			}
    
    			if(number!=0||s.size()!=0)
    			{
    				s.push_back(number);
    			}
    		}
    		while(s.size() != 0 && k > 0)
    		{
    			s.pop_back();
    			--k;
    		}
    		for(int i = 0;i<s.size();i++)
    		{
    			result.append(1,'0'+ s[i]);//注意append();是string中的函数，将数字转为字符
    		}
    		if(result == "")
    		{
    			result = "0";
    		}
    		return result;
    	}
    
    
    };
    int main()
    {
    	solution solve;
    	std::string result = solve.removeKdigits ("1432219",3);
    	printf("%s\n",result.c_str());//string中的c_str()是将字符串展示出来
    
    	std::string result1 = solve.removeKdigits ("122311",3);
    	printf("%s\n",result1.c_str());
    	return 0;
    }

\*\*2.4程序结果 \*\*  
![70 1][]

## 三、跳跃游戏01 ##

**3.1题目：**\*  
一个数组存储了非负整型数据，  
数组中的第i个元素a\[i\],代表了可以从数组第i个位置最多向前跳跃a\[i\]步，  
已知数组各元素的情况下，  
求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置？

例如：  
nums = \{2,3,1,1,4\} 可以从nums\[0\] = 2跳至nums\[4\] = 4;  
nums = \{3,2,1,0,4\} 不能从nums\[0\] = 3跳跃至nums\[4\] = 4

**3.2思想实现**  
计算出每个元素可以跳至最远的位置。  
jump 0 1 2 3 4  
nums\[jump\] 2 3 1 1 4  
index 2 4 3 4 8

设置一个max\_index代表从第0个位置至第jump位置这个过程中，最远可以到达的位置，初始化为index\[0\]  
利用jump扫描index数组，  
直到jump达到index数组尾部或者jump超过max\_index，  
扫描过程中，更新max\_index  
\*\*3.3程序实现 \*\*

#include<iostream>
    #include<vector>
    using namespace std;
    
    class solution
    {
    public:
    	bool canJumpEnd(std::vector<int>&num)
    	{
    		std::vector<int> index;
    		for(int i = 0; i<num.size();i++)
    		{
    			index.push_back(i + num[i]);
    		}
    
    		int jump = 0;
    		int max_index = index[0];
    
    		while(jump<index.size() && jump <= max_index )
    		{
    			if(max_index < index[jump])
    			{
    				max_index = index[jump];
    			}
    			++jump;
    		}
    		if(jump == index.size())
    		{
    			return true;
    		}
    		return false;
    	}
    
    };
    
    int main()
    {
    	std::vector<int> num1;
    	num1.push_back(2);
    	num1.push_back(3);
    	num1.push_back(1);
    	num1.push_back(1);
    	num1.push_back(4);
    
    	std::vector<int> num;
    	num.push_back(3);
    	num.push_back(2);
    	num.push_back(1);
    	num.push_back(0);
    	num.push_back(4);
    
    	solution solve1;
    	solution solve2;
    
    	printf("num1  : %d\n",solve1.canJumpEnd (num1));
    	printf("num   :%d\n",solve1.canJumpEnd (num));
    
    	return 0;
    }

\*\*3.4程序结果 \*\*  
![70 2][]

## 四、跳跃游戏2改进版 ##

**4.1题目：**\*  
一个数组存储了非负整型数据，  
数组中的第i个元素a\[i\],代表了可以从数组第i个位置最多向前跳跃a\[i\]步，  
已知数组各元素的情况下，  
确认可以从第0个位置跳跃到数组最后一个位置，求至少跳跃几次？

例如：  
nums = \{2,3,1,1,4\} 可以从nums\[0\] = 2跳至nums\[4\] = 4;  
nums = \{3,2,1,0,4\} 不能从nums\[0\] = 3跳跃至nums\[4\] = 4

**4.2思想实现**

计算出每个元素可以跳至最远的位置。  
jump 0 1 2 3 4  
nums\[jump\] 2 3 1 1 4  
index 2 4 3 4 8

设置一个max\_index代表从第0个位置至第jump位置这个过程中，最远可以到达的位置，初始化为index\[0\]  
设置三个变量，一个为current\_max\_index,代表当前可以到达的最远位置；  
一个为pre\_max\_max\_index，代表在遍历各个位置的过程中，各个位置可达到的最远位置  
一个jump\_min为最少跳跃次数  
利用i遍历num数组，若超过current\_max\_index,jump\_min加1，current\_max\_index=pre\_max\_max\_index;  
遍历过程中，若nums\[i\]+1(index\[i\])更大，则更新pre\_max\_max\_index = nums\[i\]+i;  
\*\*4.3程序实现 \*\*

#include<iostream>
    #include<vector>
    using namespace std;
    
    
    class solution
    {
    public:
    	int jumpthelest(std::vector<int>& nums)
    	{
    		if(nums.size()<0)
    		{
    			return 0;
    		}
    		int current_max_index = nums[0];
    		int pre_max_max_index = nums[0];
    		int jump_min = 1;
    
    		for(int i = 0; i<nums.size();i++)
    		{
    			if(i>current_max_index)
    			{
    				jump_min++;
    				current_max_index = pre_max_max_index;
    			}
    
    			if(pre_max_max_index<nums[i]+1)
    			{
    				pre_max_max_index=nums[i]+i;
    			}
    		}
    		return jump_min;
    	}
    
    
    };
    
    int main()
    {
    	std::vector<int> num1;
    	num1.push_back(2);
    	num1.push_back(3);
    	num1.push_back(1);
    	num1.push_back(1);
    	num1.push_back(4);
    
    	solution solve1;
    
    	printf("num1  : %d\n",solve1.jumpthelest (num1));
    
    	return 0;
    }

\*\*4.4程序结果 \*\*  
![70 3][]

## 五、射击气球 ##

\*\*5.1题目：\*\*已知在一个平面上有一定数量气球，平面可以看作一个坐标系，  
在平面的x轴的不同位置安排弓箭手向y轴方向射箭，弓箭可以向y轴走无穷远，给定气球的宽度xstart<=x<=xend(),问至少需要多少弓箭手，将全部气球打爆  
**5.2思想实现**  
将气球的左右端点存在一个键值对中，将相邻节点的左端点相比较，取较大的，将右端点先那个比较，取较小的具体如下：  
\*\*5.3程序实现 \*\*

#include<iostream>
    #include<vector>
    #include<algorithm>
    using namespace std;
    	bool cmp(const std::pair<int,int>&a,const std::pair<int,int>&b)
    	{
    		return a.first<b.first ;
    	}
    class solution
    {
    public:
    
    	int findMinArrowShots(std::vector<std::pair<int,int> >& points)
    	{
    		if(points.size() == 0)
    		{
    			return 0;
    		}
    		std::sort(points.begin(),points.end(),cmp);
    		int shoot_num = 1;
    		int shoot_begin = points[0].first;
    		int shoot_end = points[0].second;
    
    		for(int i = 1;i<points.size();i++)
    		{
    			if(points[i].first<=shoot_end)
    			{
    				shoot_begin = points[i].first;
    			
    
    			if(shoot_end > points[i].second )
    			{
    				shoot_end = points[i].second;
    			}
    		}
    		else{
    			shoot_num++;
    			shoot_begin = points[i].first;
    			shoot_end = points[i].second;
    		}
    	}
    	return shoot_num;
    }
    
    };
    
    int main()
    {
    	std::vector<std::pair<int,int>> points;
    	points.push_back(std::make_pair(10,16));
    	points.push_back(std::make_pair(2,8));
    	points.push_back(std::make_pair(1,6));
    	points.push_back(std::make_pair(7,12));
    	solution solve;
    	printf("%d\n",solve.findMinArrowShots(points));
    	return 0;
    }

\*\*5.4程序结果 \*\*  
![70 4][]

## 六、最优加油站 ##

\*\*6.1题目：\*\*已知一条公路上，有一个起点与一个终点，这之间有n个加油站；  
已知从这n个加油站到终点的距离d；  
与各个加油站可以加油的量为L，  
起点位置至终点的距离L  
与起始时刻油箱中汽油量P  
假设使用1个单位的汽油即走1个单位的距离，邮箱没有上限，  
最少加几次油，可以从起点开至终点？（如果无法到达终点，返回-1）  
**6.2思想实现**  
算法思想：（1）油用光的时候加油最合适  
（2）在油量最多的加油站加油最合适

利用最大堆实现，在堆中保留加油站油量，
    	  当油箱汽油不足以到达下一个加油站时，则加油

\*\*6.3程序实现 \*\*

#include<iostream>
    #include<queue>
    #include<vector>
    using namespace std;
    bool cmp(const std::pair<int ,int>&a,const std::pair<int ,int>&b)
    {
    	return a.first > b.first ;
    }
    class solution
    {
    public://L为起点到终点的距离 P为起点初始汽油量，pair<加油站指终点的距离，加油站汽油量>
    	int get_minimum_stop(int L,int P,std::vector<std::pair<int,int>> &stop)
    	{
    		std::priority_queue<int,std::vector<int>,std::less<int>> Q;
    		int result = 0;
    		stop.push_back(std::make_pair(0,0));
    		std::sort(stop.begin(),stop.end(),cmp);
    
    		for(int i = 0; i<stop.size();i++)
    		{
    			int dis = L - stop[i].first;
    			while(!Q.empty())
    			{
    				P  = P + Q.top();
    				Q.pop();
    				result++;
    			}
    			if(Q.empty()&&P<dis)
    			{
    				return -1;
    			}
    			P = P -dis;
    			L = stop[i].first;
    			Q.push(stop[i].second);
    
    		}
    		return result;
    	}
    
    };
    int main()
    {
    	std::vector<std::pair<int ,int>> stop;
    	int N;
    	int L;
    	int P;
    	int dis;
    	int fuel;
    	scanf("%d",&N);
    
    	for(int i = 0; i<N; i++)
    	{
    		scanf("%d %d",&dis,&fuel);
    		stop.push_back(std::make_pair(dis,fuel));
    	}
    
    	scanf("%d %d",&L,&P);
    	solution solve;
    	printf("%d\n",solve.get_minimum_stop (L,P,stop));
    	return 0;
    }

\*\*6.4程序结果 \*\*  
![70 5][]

[Link 1]: https://blog.csdn.net/dai_wen/article/details/81631704
[70]: /images/20220516/6d947150a52742a6b3e2fb2fe33205f8.png
[70 1]: /images/20220516/2b1faf02d5f343daa9ca43f47ce18d73.png
[70 2]: /images/20220516/3a8b80f60d9a47ebbf25623a4da33942.png
[70 3]: /images/20220516/0603bf6efe4e433bbe843b91bfe28918.png
[70 4]: /images/20220516/b7a11841a51f49f5b5f18dbbcc0cab7e.png
[70 5]: /images/20220516/8a89283eb97f4b3888d803dbcdf2eed6.png