韩城网站建设韩城网站推广,Python做网站 性能,wordpress主题怎么写,简历制作官网1.贪心算法理论基础
贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。贪心算法并没有固定的套路#xff0c;唯一的难点就是如何通过局部最优#xff0c;推出整体最优。最好用的策略就是举反例#xff0c;如果想不到反例#xff0c;那么就试一试贪心吧 贪…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(vectorint g, vectorint 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(vectorint g, vectorint s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index 0,result 0;for(int i 0;i s.size();i){if(index g.size() g[index] s[i]){result;index;}}return result;}
};
时间复杂度O(nlogn)空间复杂度O(1)
3. 摆动序列376题
题目描述
如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。
例如 [1,7,4,9,2,5] 是一个摆动序列因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
给定一个整数序列返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些也可以不删除元素来获得子序列剩下的元素保持其原始顺序。
示例 1:
输入: [1,7,4,9,2,5]输出: 6解释: 整个序列均为摆动序列。
贪心算法
局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。
整体最优整个序列有最多的局部峰值从而达到最长摆动序列。
实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度
这就是贪心所贪的地方让峰值尽可能的保持峰值然后删除单一坡度上的节点
本题要考虑三种情况
情况一上下坡中有平坡情况二数组首尾两端情况三单调坡中有平坡 本题异常情况的本质就是要考虑平坡 平坡分两种一个是 上下中间有平坡一个是单调有平坡
class Solution {
public:int wiggleMaxLength(vectorint nums) {if(nums.size() 1)return nums.size();int prediff 0;//前一对差值int curdiff 0;//当前一对差值int result 1;//结果//这里注意i遍历到nums.size()-1,因为默认数组最右边一个序列有1for(int i 0;i nums.size()-1;i){curdiff nums[i1] - nums[i];//当前一对差值计算//出现波动就会记录if((prediff 0 curdiff 0)||(prediff 0 curdiff 0)){result;//结果改变prediff curdiff;//只有摆动变化记录更改prediff值}}return result;}
};
时间复杂度O(n)空间复杂度O(1)
动态规划
当前考虑的这个数要么是作为山峰即 nums[i] nums[i-1]要么是作为山谷即 nums[i] nums[i - 1]。
设 dp 状态dp[i][0]表示考虑前 i 个数第 i 个数作为山峰的摆动子序列的最长长度设 dp 状态dp[i][1]表示考虑前 i 个数第 i 个数作为山谷的摆动子序列的最长长度
则转移方程为
dp[i][0] max(dp[i][0], dp[j][1] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山谷后面作为山峰。dp[i][1] max(dp[i][1], dp[j][0] 1)其中0 j i且nums[j] nums[i]表示将 nums[i]接到前面某个山峰后面作为山谷。
初始状态
由于一个数可以接到前面的某个数后面也可以以自身为子序列的起点所以初始状态为dp[0][0] dp[0][1] 1。
class Solution {
public:int dp[1005][2];int wiggleMaxLength(vectorint nums) {memset(dp,0,sizeof dp);dp[0][0] dp[0][1] 1;for(int i 1;i nums.size();i){dp[i][0] dp[i][1] 1;for(int j 0;j i;j){if (nums[j] nums[i]) dp[i][1] max(dp[i][1], dp[j][0] 1);}for (int j 0; j i; j) {if (nums[j] nums[i]) dp[i][0] max(dp[i][0], dp[j][1] 1);}}return max(dp[nums.size() - 1][0],dp[nums.size() - 1][1]);}
};
时间复杂度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(vectorint nums) {int result INT32_MIN;int count 0;for(int i 0;i nums.size();i){count 0;for(int j i;j nums.size();j){count nums[j];result count result ? count : result;}}return result;}
};
时间复杂度O(n^2)空间复杂度O(1)
贪心算法
局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。
全局最优选取最大“连续和”
局部最优的情况下并记录最大的“连续和”可以推出全局最优。
区间的终止位置其实就是如果 count 取到最大值了及时记录下来了区间终止位置立刻记录
class Solution {
public://int maxSubArray(vectorint nums) {int result INT32_MIN;//定义一个最小值int count 0;//这个是总和for(int i 0;i nums.size();i){count nums[i];//计算总和if(count result){result count;//如果总和大于结果就去更新更新最大值}if(count 0){count 0;//重置最大子序列初始位置小于零就重新定位}}return result;}
};
时间复杂度O(n)空间复杂度O(1) 动态规划
class Solution {
public:int maxSubArray(vectorint nums) {if(nums.size() 0)return 0;vectorintdp(nums.size(),0);//dp[i]表示包括i之前的最大连续子序列和dp[0] nums[0];int result dp[0];for(int i 1;i nums.size();i){dp[i] max(dp[i-1]nums[i],nums[i]);//状态转移公式if(dp[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(vectorint prices) {int result 0;//这里注意i的取值从1开始取for(int i 1;i prices.size();i){result max(prices[i] - prices[i-1],0);//两个位置的价格差值和0对比求得正利润即可}return result;}
};
时间复杂度O(n)空间复杂度O(1)
动态规划
class Solution {
public:int maxProfit(vectorint prices) {// dp[i][1]第i天持有的最多现金// dp[i][0]第i天持有股票后的最多现金int n prices.size();vectorvectorintdp(n,vectorint(2,0));dp[0][0] - prices[0];// 持股票for(int i 1;i prices.size();i){dp[i][0] max(dp[i-1][1] - prices[i],dp[i-1][0]);// 第i天持股票所剩最多现金 max(第i-1天持股票所剩现金, 第i-1天持现金-买第i天的股票)dp[i][1] max(dp[i-1][1],dp[i-1][0] prices[i]);// 第i天持有最多现金 max(第i-1天持有的最多现金第i-1天持有股票的最多现金第i天卖出股票)}return max(dp[n-1][0],dp[n-1][1]);}
};
时间复杂度O(n)空间复杂度O(n) 总结
贪心算法理论基础每一阶段的局部最优得到全局最优的解决方法无固定套路
分发饼干大饼干喂胃口大的孩子全局最优就是需要喂饱更多的小孩先给饼干和小孩胃口排序然后从后向前遍历小孩数组用大饼干来喂饱大胃口小孩并且统计数量注意遍历饼干技巧可以采用下标来自减方式实现分发饼干这里的Index从后向前可以大饼干喂大胃口或者小饼干喂小胃口
摆动序列是指两个相邻的元素之差是正负交替的一组序列使用贪心算法来实现注意两端是需要算做一个我们需要记录前一个和当前的差值条件判断注意需要确保两个差值的正负不同号即可precur是关键进行一组就是关键
最大子序和贪心算法这里需要注意一个细节我们最开始需要定义一个最小值再定义每个数组和去思想逻辑是如果数组和是小于0我们抛弃这个数组和置为0还要更新最大数组和的一个操作
买卖股票的最佳时机II我们只要想到利润可以拆分成多个利润相加的模式就可以解决只要正利润就好得到最后想要的结果可以使用动态规划来实现。
