贪心算法03：1005 K次取反后最大化的数组和 、134 加油站、135 分发糖果 1、1005 K次取反后最大化的数组和 1005 给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。） 以这种方式修改数组后，返回数组可能的最大和。 示例 1：输入：A = [4,2,3], K = 1输出：5解释：选择索引 (1) ，然后 A 变为 [4,-2,3]。 示例 2：输入：A = [3,-1,0,2], K = 3输出：6解释：选择索引 (1, 2, 2) ，然后 A 变为 [3,1,0,2]。 思路： 1）将序列中负的数值都变成正的，如果K的值小于负数值的个数，就把绝对值大的负数给变了 2）如果序列中没有负的了而K!=0，（因为正的变化两次还是正的）。令k=K%2 ，k可能为0和1，k=0则直接输出sum(序列)，k=1则让现序列中最小的数值变化成负的，再输出sum(序列即可) 1）函数比较器： 问：为什么sort函数中的cmp要是static的？ sort中的比较函数compare要声明为静态成员函数或全局函数，不能作为普通成员函数，否则会报错。 因为：非静态成员（non-static）函数是依赖于具体对象的，而std::sort这类函数是全局的，因此无法再sort中调用非静态成员函数。静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问，无须创建任何对象实例就可以访问。 同时静态成员函数不可以调用类的非静态成员（因为非静态成员是依赖于对象的，有可能对象不存在，只有类存在，那就会出现错误）。 一般来说就声明为main函数外面的全局函数，在力扣中就声明为static，和对象无关的。 2）函数对象比较器： 所谓函数对象是指实现了 的类或者结构体。可以用这样的一个对象来代替函数作为比较器。 顺便来复习一下仿函数叭 以前的笔记
2、134 加油站 134
示例 1: 示例 2: 思路：gas[i]-cost[i]>=0的时候，从第i号加油站出发 暴力： 遍历每一个加油站为起点的情况 如果跑了一圈，中途没有断油，而且最后油量大于等于0，说明这个起点是ok的。 for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历 并且这里有一个小细节：为了实现环形，index=(i + 1) % cost.size();//用取余数实现环形 时间复杂度：n^2 贪心： 
很牛逼噻，看完视频瞪大了我的双眼。 局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。全局最优：找到可以跑一圈的起始位置。 首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。 每个加油站的剩余量rest[i]为gas[i] – cost[i]。 i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。 3、135 分发糖果 135 个孩子站成一排。给你一个整数数组 表示每个孩子的评分。 你需要按照以下要求，给这些孩子分发糖果：每个孩子至少分配到 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。 示例 1： 示例 2： 题目中没有说评分相同怎么办，由例子可以看出，相同的话就给一个 一定是要确定一边之后，再确定另一边，如果两边一起考虑一定会顾此失彼。 自己做的时候 就想着一遍循环结束，却越搞越乱
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/63992.html
