C++算法学习心得七.贪心算法(1)
1.贪心算法理论基础
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。贪心算法并没有固定的套路,唯一的难点就是如何通过局部最优,推出整体最优。最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了
2.分发饼干(455题)
题目描述:
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
示例 1:
(图片来源网络,侵删)- 输入: g = [1,2,3], s = [1,1]
- 输出: 1 解释:你有三个孩子和两块小饼干,3 个孩子的胃口值分别是:1,2,3。虽然你有两块小饼干,由于他们的尺寸都是 1,你只能让胃口值是 1 的孩子满足。所以你应该输出 1。
这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略,先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组,用大饼干优先满足胃口大的,并统计满足小孩数量。
一个 index 来控制饼干数组的遍历,遍历饼干并没有再起一个 for 循环,而是采用自减的方式
一定要 for 控制 胃口,里面的 if 控制饼干
class Solution { public: //贪心算法,使用大饼干先满足大胃口的原则来实现 int findContentChildren(vector& g, vector& s) { sort(g.begin(),g.end());//对胃口和饼干都进行排序 sort(s.begin(),s.end()); int index = s.size() - 1;//这里采用下标的形式来实现 int result = 0;//定义结果 //我们从后向前遍历,实现大饼干满足大胃口的原则 for(int i = g.size() - 1;i >= 0;i--){ //如果满足了条件,饼干下标减一,结果收集 if(index >= 0 && s[index] >= g[i]){ result++; index--; } } return result; } };
- 时间复杂度:O(nlogn)
- 空间复杂度:O(1)
class Solution { public: //贪心算法实现,小饼干喂小胃口的人,注意下标的选取就好 int findContentChildren(vector& g, vector& s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int index = 0,result = 0; for(int i = 0;i
- 设 dp 状态dp[i][0],表示考虑前 i 个数,第 i 个数作为山峰的摆动子序列的最长长度
- 设 dp 状态dp[i][1],表示考虑前 i 个数,第 i 个数作为山谷的摆动子序列的最长长度
则转移方程为:
- dp[i][0] = max(dp[i][0], dp[j][1] + 1),其中0
- dp[i][1] = max(dp[i][1], dp[j][0] + 1),其中0 nums[i],表示将 nums[i]接到前面某个山峰后面,作为山谷。
初始状态:
由于一个数可以接到前面的某个数后面,也可以以自身为子序列的起点,所以初始状态为:dp[0][0] = dp[0][1] = 1。
class Solution { public: int dp[1005][2]; int wiggleMaxLength(vector& nums) { memset(dp,0,sizeof dp); dp[0][0] = dp[0][1] = 1; for(int i = 1;i nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1); } for (int j = 0; j
- 时间复杂度:O(n^2)
- 空间复杂度:O(n)
4.最大子序和(53题)
题目描述:
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
暴力解法:第一层 for 就是设置起始位置,第二层 for 循环遍历数组寻找最大值
class Solution { public: int maxSubArray(vector& nums) { int result = INT32_MIN; int count = 0; for(int i = 0;i result ? count : result; } } return result; } };
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
贪心算法:
局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。
全局最优:选取最大“连续和”
局部最优的情况下,并记录最大的“连续和”,可以推出全局最优。
区间的终止位置,其实就是如果 count 取到最大值了,及时记录下来了,区间终止位置立刻记录
class Solution { public: // int maxSubArray(vector& nums) { int result = INT32_MIN;//定义一个最小值 int count = 0;//这个是总和 for(int i = 0;i result){ result = count;//如果总和大于结果就去更新,更新最大值 } if(count
- 时间复杂度:O(n)
- 空间复杂度:O(1)
动态规划:
class Solution { public: int maxSubArray(vector& nums) { if(nums.size() == 0)return 0; vectordp(nums.size(),0);//dp[i]表示包括i之前的最大连续子序列和 dp[0] = nums[0]; int result = dp[0]; for(int i = 1;i result)result = dp[i];//result 保存dp[i]的最大值 } return result; } };
- 时间复杂度:O(n)
- 空间复杂度:O(n)
5.买卖股票的最佳时机 II(122题)
题目描述:
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
- 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
贪心算法:
假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度,而不是从 0 天到第 3 天整体去考虑,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间
class Solution { public: //把整个利润去拆分成每一个利润的和形式,取最大利润就是求所有正利润就好 int maxProfit(vector& prices) { int result = 0; //这里注意i的取值从1开始取 for(int i = 1;i
- 时间复杂度:O(n)
- 空间复杂度:O(1)
动态规划:
class Solution { public: int maxProfit(vector& prices) { // dp[i][1]第i天持有的最多现金 // dp[i][0]第i天持有股票后的最多现金 int n = prices.size(); vectordp(n,vector(2,0)); dp[0][0] -= prices[0];// 持股票 for(int i = 1;i
- 时间复杂度:O(n)
- 空间复杂度:O(n)
总结:
贪心算法理论基础:每一阶段的局部最优,得到全局最优的解决方法,无固定套路
分发饼干:大饼干喂胃口大的孩子,全局最优就是需要喂饱更多的小孩,先给饼干和小孩胃口排序,然后从后向前遍历小孩数组,用大饼干来喂饱大胃口小孩,并且统计数量,注意遍历饼干技巧,可以采用下标来自减方式实现分发饼干,这里的Index从后向前,可以大饼干喂大胃口或者小饼干喂小胃口
摆动序列:是指两个相邻的元素之差是正负交替的一组序列,使用贪心算法来实现,注意两端是需要算做一个,我们需要记录前一个和当前的差值,条件判断注意需要确保两个差值的正负不同号即可,pre=cur是关键,进行一组就是关键,
最大子序和:贪心算法这里需要注意一个细节我们最开始需要定义一个最小值,再定义每个数组和去,思想逻辑是如果数组和是小于0我们抛弃这个数组和置为0,还要更新最大数组和的一个操作
买卖股票的最佳时机II:我们只要想到利润可以拆分成多个利润相加的模式就可以解决,只要正利润就好,得到最后想要的结果,可以使用动态规划来实现。
还没有评论,来说两句吧...