做网站销售需要注意的,wordpress和,wordpress免费商城模板下载地址,网络服务器分为哪几种2.贪心算法.基础 基础知识题目1.分发饼干2.摆动序列2.1.思路二#xff1a;动态规划法 3.最大子序和4.买股票的最佳时机24.1.思路二#xff1a;动态规划法4.2.买股票的最佳时机 5.跳跃游戏5.1.跳跃游戏2 6.K次取反后最大化的数组和7.加油站8.分发糖果 总结 基础知识
什么是贪… 2.贪心算法.基础 基础知识题目1.分发饼干2.摆动序列2.1.思路二动态规划法 3.最大子序和4.买股票的最佳时机24.1.思路二动态规划法4.2.买股票的最佳时机 5.跳跃游戏5.1.跳跃游戏2 6.K次取反后最大化的数组和7.加油站8.分发糖果 总结 基础知识
什么是贪心? 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 贪心的套路 贪心算法并没有固定的套路。不好意思也没有 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。那如何验证可不可用贪心算法最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。 一般的数学证明有如下两种方法 1.数学归纳法 2.反证法
面试中基本不会让面试者现场证明贪心的合理性代码写出来跑过测试用例即可或者自己能自圆其说理由就行了。 贪心一般解题步骤一般分为如下四步 1.将问题分解为若干个子问题 2.找出适合的贪心策略 3.求解每一个子问题的最优解 4.将局部最优解堆成全局最优解 做题的时候只要想清楚 局部最优 是什么如果推导出全局最优其实就够了。
贪心没有套路说白了就是常识性推导加上举反例。贪心的一般解题步骤大家可以发现这个解题步骤也是比较抽象的不像是二叉树回溯算法给出了那么具体的解题套路和模板。
题目
1.分发饼干
题目链接 对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]我们可以将这个饼干 j 分配给孩子 i 这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子并输出这个最大数值。 为了不浪费饼干的尺寸打算尽量用尺寸最大的饼去给胃口最大的孩子以此往下推每一步充分发挥这个当前饼尺寸的作用。 int findContentChildren(vectorint g, vectorint s) {std::sort(g.begin(), g.end());std::sort(s.begin(), s.end());int index0; // for personfor(int i0; is.size(); i){ // for cakeif(indexg.size() g[index]s[i]) index;}return index;}for循环可以从饼开始匹配从人开始匹配但要主要方向的不同 2.摆动序列
题目链接 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为摆动序列。第一个差如果存在的话可能是正数或负数。少于两个元素的序列也是摆动序列。例如 [1,7,4,9,2,5] 是一个摆动序列而[1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列。 因此题目要求是 给定一个整数序列返回作为摆动序列的最长子序列的长度 这是思路是局部最优——除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值整体最优——整个序列有最多的局部峰值从而达到最长摆动序列。 实际操作上其实连删除的操作都不用做因为题目要求的是最长摆动子序列的长度所以只需要统计数组的峰值数量就可以了相当于是删除单一坡度上的节点然后统计长度 要处理一下三种特殊情况结合题目要求情况一的结果应该是3情况二的结果应该是2情况三的结果应该是2因为单调种的平坡不能算是峰值。那如何如何消除这些平坡的影响呢因为摆动是通过prediff与curdiff的符号变化来添加峰值计数我们只要让prediff在发生摆动时才修改就行了对于平坡的情况pre的符号就维持不变。 int wiggleMaxLength(vectorint nums) {if(nums.size()1) return nums.size();int curdiff 0;int prediff 0;int res 1;for(int i0; inums.size()-1; i){curdiff nums[i1]-nums[i];if((prediff0 curdiff0) || (prediff0 curdiff0)){res;prediff curdiff;}}return res;}时间复杂度O(n^2)空间复杂度O(n)
2.1.思路二动态规划法 3.最大子序和
题目链接 给定一个整数数组 nums 找到一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。 暴力解法通过两层for循环完成整数数组的子集和的统计最后比较得出最大的值即可。 其时间复杂度O(n^2)空间复杂度O(1)
贪心解法局部最优——最大连续和的设置另外一个数组存放原本数组上从0开始连续和0的数值当连续和0时则从下一个数值开始计数。最后得到这个连续 int maxSubArray(vectorint nums) {int res INT_MIN;int count 0;for(int i0; inums.size(); i){count nums[i];if(countres) res count;if(count0) count0;}return res;}这里res初始化为INT_MIN是为了处理当数组首个字母是负数的情况 4.买股票的最佳时机2
题目链接 给定一个数组它的第 i 个元素是一支给定股票第 i 天的价格计算你所能获取的最大利润但注意你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。 例如输入: [7,1,5,3,6,4]在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5-1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6-3 3 。
思路1.想要获取利润至少两天为一个交易单元 2.初始想法是选择一个低价买入再高价卖出…一直这样循环 3. int maxProfit(vectorint prices) {int res 0;for(int i1; iprices.size(); i){res max(prices[i]-prices[i-1], 0);}return res;} 4.1.思路二动态规划法
4.2.买股票的最佳时机
题目链接 你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。只有一个购买-卖出的周期也就是一次获取利润的机会。 int maxProfit(vectorint prices) {int res 0;int min_pri INT_MAX;for(int i0; iprices.size(); i){min_pri prices[i]min_pri? prices[i]:min_pri;res resprices[i]-min_pri? prices[i]-min_pri: res;}return res;}5.跳跃游戏
题目链接 给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 bool canJump(vectorint nums) {int cover 0;if(nums.size()1) return true;for(int i0; icover; i){cover max(inums[i], cover);if(cover nums.size()-1) return true;}return false;}5.1.跳跃游戏2
题目链接 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处目标是使用最少的跳跃次数并返回该次数。 与上一题不同该题要求最小步数因此需要设置两个变量存储当前步可覆盖范围下一步可覆盖范围循环特点是 没进入一层cover时会更新precover值并与之前的precover比较覆盖当covercurcover时步数统计count1且将precover值赋给curcover最后当precover覆盖数组末尾时退出。 int jump(vectorint nums) {if(nums.size()1) return 0;// 两者初始化从0出发int curcover 0;int precovner 0;int count 0;for(int i0; inums.size(); i){//实时计算在下一步可到达的范围precovner max(i nums[i], precovner);if(icurcover){count;curcover precovner; //转化为当前步可到达的范围if(precovnernums.size()-1) break;}}return count;6.K次取反后最大化的数组和
题目链接 给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。重复这个过程恰好 k 次。可以多次选择同一个下标 i 。以这种方式修改数组后返回数组 可能的最大和 。 基本思路是1.将数组中的负数尽量反转为正数 2.若剩余数组均为正数此时所剩k值若为奇数则选择一个值最小的正数反转为负数 若剩余k值是偶数则无影响。 // 加了绝对值排序法int largestSumAfterKNegations(vectorint nums, int k) {std::sort(nums.begin(), nums.end(), cmp);for(int i0; inums.size(); i){if(nums[i]0 k0){nums[i] * -1;k--;}}if(k%2 1) nums[nums.size()-1] * -1;int res 0;for(int n:nums) res n;return res;}//正常递增序列排序法int largestSumAfterKNegations(vectorint nums, int k) {std::sort(nums.begin(), nums.end());int min_abs 0;for(int i0; inums.size(); i){if(nums[i]0 k0){nums[i] * -1;k--;}min_abs abs(nums[min_abs])abs(nums[i])? min_abs: i;}if(k%21) nums[min_abs] * -1;int res0;for(int n:nums) res n;return res;}7.加油站
题目链接 暴力的方法很明显就是O(n^2)的遍历每一个加油站为起点的情况模拟一圈。
贪心算法1情况一若gas总和小于cost总和则一定跑不完一圈情况二从0开始出发累计一圈下来若中途累加值0则说明从0出发不可行情况三此时京start后移即start从尾部朝头部移动若该节点和能使之前中途累加值的负值填平则可以从该节点出发。 贪心算法2当局部连续数组和0时说明在i步遇到较大的负值到时总和不满足此时可以判断从i之前开始一定不可行理解这个判断说明从start到i-1步及之前是满足0约束的若存在start~i之间的一个值index到i值的区间满足0则说明在start到index区间的值0这不符合假设。至少从i1开始。 // 贪心1最少满足start延后int canCompleteCircuit(vectorint gas, vectorint cost) {int cursum 0;int min INT_MAX;for(int i0; igas.size(); i){int res gas[i]-cost[i];cursum res;if(cursummin){min cursum;}}if(cursum0) return -1;if(min0) return 0;for(int igas.size()-1; i0; i--){int res gas[i]-cost[i];min res;if(min0) return i;}return -1;}// 贪心2最长局部累加和int canCompleteCircuit(vectorint gas, vectorint cost) {int cursum 0;int totalsum 0;int start 0;for(int i0; igas.size(); i){cursum gas[i] - cost[i];totalsum gas[i] - cost[i];if(cursum0){start i1;cursum 0;}}if (totalsum0) return -1;return start;}时间复杂度O(n)空间复杂度O(1) 8.分发糖果
题目链接 这道题目有点意思 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求给这些孩子分发糖果 1.每个孩子至少分配到 1 个糖果。 2.相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 确定左孩子比右孩子大的情况一定是从后面往前遍历否则不能利用右边孩子的candy的比较情况得到vec1确定右孩子比左孩子大的情况是从前往后遍历这样也是未来利用左孩子的candy的比较情况得到vec2最后取candy的vector时取vec1vec2各个索引位置上candy的max情况——这样即满足了右孩子比左孩子大左孩子比右孩子大的情况。 int candy(vectorint ratings) {std::vectorint candyvec(ratings.size(), 1);for(int i1; iratings.size(); i){if(ratings[i]ratings[i-1]) candyvec[i] candyvec[i-1]1;}for(int iratings.size()-2; i0; i--){if(ratings[i]ratings[i1]) candyvec[i] max(candyvec[i1]1, candyvec[i]);}int res 0;for(int n:candyvec) res n;return res;}总结
