景洪市新农村建设网站,企业域名如何申请,企业网站策划书下载,网站建设程序员做什么本文章代码以c为例#xff01;
一、力扣第1005题#xff1a;K 次取反后最大化的数组和
题目:
给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a;
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择…本文章代码以c为例
一、力扣第1005题K 次取反后最大化的数组和
题目:
给你一个整数数组 nums 和一个整数 k 按以下方法修改该数组
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后返回数组 可能的最大和 。 示例 1
输入nums [4,2,3], k 1
输出5
解释选择下标 1 nums 变为 [4,-2,3] 。示例 2
输入nums [3,-1,0,2], k 3
输出6
解释选择下标 (1, 2, 2) nums 变为 [3,1,0,2] 。示例 3
输入nums [2,-3,-1,5,-4], k 2
输出13
解释选择下标 (1, 4) nums 变为 [2,3,-1,5,4] 。提示
1 nums.length 104-100 nums[i] 1001 k 104
思路
本题思路其实比较好想了如何可以让数组和最大呢
贪心的思路局部最优让绝对值大的负数变为正数当前数值达到最大整体最优整个数组和达到最大。
局部最优可以推出全局最优。
那么如果将负数都转变为正数了K依然大于0此时的问题是一个有序正整数序列如何转变K次正负让 数组和 达到最大。
那么又是一个贪心局部最优只找数值最小的正整数进行反转当前数值和可以达到最大例如正整数数组{5, 3, 1}反转1 得到-1 比 反转5得到的-5 大多了全局最优整个 数组和 达到最大。
虽然这道题目大家做的时候可能都不会去想什么贪心算法一鼓作气就AC了。
我这里其实是为了给大家展现出来 经常被大家忽略的贪心思路这么一道简单题就用了两次贪心
那么本题的解题步骤为
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小第二步从前向后遍历遇到负数将其变为正数同时K--第三步如果K还大于0那么反复转变数值最小的元素将K用完第四步求和
对应C代码如下
class Solution {
static bool cmp(int a, int b) {return abs(a) abs(b);
}
public:int largestSumAfterKNegations(vectorint A, int K) {sort(A.begin(), A.end(), cmp); // 第一步for (int i 0; i A.size(); i) { // 第二步if (A[i] 0 K 0) {A[i] * -1;K--;}}if (K % 2 1) A[A.size() - 1] * -1; // 第三步int result 0;for (int a : A) result a; // 第四步return result;}
};时间复杂度: O(nlogn)空间复杂度: O(1)
# 总结
贪心的题目如果简单起来会让人简单到开始怀疑本来不就应该这么做么这也算是算法我认为这不是贪心
本题其实很简单不会贪心算法的同学都可以做出来但是我还是全程用贪心的思路来讲解。
因为贪心的思考方式一定要有
如果没有贪心的思考方式局部最优全局最优很容易陷入贪心简单题凭感觉做贪心难题直接不会做其实这样就锻炼不了贪心的思考方式了。
所以明知道是贪心简单题也要靠贪心的思考方式来解题这样对培养解题感觉很有帮助。
二、力扣第134题加油站
题目
在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发开始时油箱为空。
给定两个整数数组 gas 和 cost 如果你可以按顺序绕环路行驶一周则返回出发时加油站的编号否则返回 -1 。如果存在解则 保证 它是 唯一 的。 示例 1:
输入: gas [1,2,3,4,5], cost [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发可获得 4 升汽油。此时油箱有 0 4 4 升汽油
开往 4 号加油站此时油箱有 4 - 1 5 8 升汽油
开往 0 号加油站此时油箱有 8 - 2 1 7 升汽油
开往 1 号加油站此时油箱有 7 - 3 2 6 升汽油
开往 2 号加油站此时油箱有 6 - 4 3 5 升汽油
开往 3 号加油站你需要消耗 5 升汽油正好足够你返回到 3 号加油站。
因此3 可为起始索引。
示例 2:
输入: gas [2,3,4], cost [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发可以获得 4 升汽油。 此时油箱有 0 4 4 升汽油
开往 0 号加油站此时油箱有 4 - 3 2 3 升汽油
开往 1 号加油站此时油箱有 3 - 3 3 3 升汽油
你无法返回 2 号加油站因为返程需要消耗 4 升汽油但是你的油箱只有 3 升汽油。
因此无论怎样你都不可能绕环路行驶一周。 提示:
gas.length ncost.length n1 n 1050 gas[i], cost[i] 104
思路
# 暴力方法
暴力的方法很明显就是O(n^2)的遍历每一个加油站为起点的情况模拟一圈。
如果跑了一圈中途没有断油而且最后油量大于等于0说明这个起点是ok的。
暴力的方法思路比较简单但代码写起来也不是很容易关键是要模拟跑一圈的过程。
for循环适合模拟从头到尾的遍历而while循环适合模拟环形遍历要善于使用while
C代码如下
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {for (int i 0; i cost.size(); i) {int rest gas[i] - cost[i]; // 记录剩余油量int index (i 1) % cost.size();while (rest 0 index ! i) { // 模拟以i为起点行驶一圈如果有rest0那么答案就不唯一了rest gas[index] - cost[index];index (index 1) % cost.size();}// 如果以i为起点跑一圈剩余油量0返回该起始位置if (rest 0 index i) return i;}return -1;}
};问题是有多个加油站形成一个环形路线每个加油站都有一个固定的油量gas数组和从当前加油站开到下一个加油站所需要的油量cost数组。问从哪个加油站出发可以走完整个环形路线。如果不能从任何一个加油站出发走完整个环形返回-1。
代码解析 外层循环for (int i 0; i cost.size(); i) - 遍历所有加油站考虑每一个加油站作为起点。 int rest gas[i] - cost[i]; - rest 记录从当前加油站出发后的剩余油量。初始值是当前加油站的油量减去开到下一个加油站所需的油量。 int index (i 1) % cost.size(); - 初始化一个index它表示从第i个加油站出发后下一个要到达的加油站的位置。这里使用了取模操作确保index在数组的范围内。 内层循环while (rest 0 index ! i) - 当剩余的油量为正且没有回到起点时继续模拟行驶。 rest gas[index] - cost[index]; - 更新剩余油量加上在下一个加油站获得的油量并减去开往再下一个加油站所需的油量。 index (index 1) % cost.size(); - 移动到下一个加油站。 判断条件if (rest 0 index i) - 如果剩余油量不为负且回到了出发的加油站则找到了一个满足条件的起始位置。 如果所有的加油站都作为起点尝试过后都不能满足条件返回-1。
这个算法的基本思想是对于每一个加油站都尝试从它开始走一圈看是否可行。如果某个加油站作为起点走不通则说明它到下一个加油站之间的任何一个加油站都不能作为起点。因为如果其中一个可以作为起点则前一个加油站也可以。所以当找到一个加油站不能作为起点时可以直接跳过它到下一个加油站之间的所有加油站继续尝试下一个。
时间复杂度O(n^2)空间复杂度O(1)
# 贪心算法方法一
直接从全局进行贪心选择情况如下 情况一如果gas的总和小于cost总和那么无论从哪里出发一定是跑不了一圈的 情况二rest[i] gas[i]-cost[i]为一天剩下的油i从0开始计算累加到最后一站如果累加没有出现负数说明从0出发油就没有断过那么0就是起点。 情况三如果累加的最小值是负数汽车就要从非0节点出发从后向前看哪个节点能把这个负数填平能把这个负数填平的节点就是出发节点。
C代码如下
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int min INT_MAX; // 从起点出发油箱里的油量最小值for (int i 0; i gas.size(); i) {int rest gas[i] - cost[i];curSum rest;if (curSum min) {min curSum;}}if (curSum 0) return -1; // 情况1if (min 0) return 0; // 情况2// 情况3for (int i gas.size() - 1; i 0; i--) {int rest gas[i] - cost[i];min rest;if (min 0) {return i;}}return -1;}
};这是一个优化版本的解决方案用于解决同样的「加油站环形路线」问题。这个版本的算法使用了贪心的思想通过一次遍历来确定从哪个加油站出发可以完成整个环形路线。
代码解析 初始化两个变量 curSum用于记录从起点出发油箱里的油量累计值。min用于记录从起点出发油箱里的油量最小值。 第一个循环for (int i 0; i gas.size(); i) - 遍历所有加油站计算从起点出发到每个加油站的油量累计值并更新curSum和min。 if (curSum 0) return -1; - 如果curSum为负说明油的总量不足以支撑整个环形路线直接返回-1。 if (min 0) return 0; - 如果min为非负说明从第0个加油站出发油箱里的油量始终为非负因此可以从第0个加油站出发完成整个环形路线。 第二个循环for (int i gas.size() - 1; i 0; i--) - 如果上述两种情况都不满足从最后一个加油站开始反向遍历。这是因为如果从第0个加油站出发在某个加油站油量最少即min那么从这个加油站的下一个加油站出发可能是一个合适的起点。 在第二个循环中每次都更新min的值并检查min是否为非负。如果为非负说明从当前加油站出发可以完成整个环形路线。 如果所有的加油站都尝试过后都不满足条件返回-1。
这个算法的基本思想是首先检查总的油量是否足够支撑整个环形路线然后找到从哪个加油站出发油箱里的油量最少。如果这个最小值为非负说明可以从第0个加油站出发否则从这个最小值对应的加油站的下一个加油站开始尝试直到找到一个合适的起点或者遍历完所有的加油站。
时间复杂度O(n)空间复杂度O(1)
其实我不认为这种方式是贪心算法因为没有找出局部最优而是直接从全局最优的角度上思考问题。
但这种解法又说不出是什么方法这就是一个从全局角度选取最优解的模拟操作。
所以对于本解法是贪心我持保留意见
但不管怎么说解法毕竟还是巧妙的不用过于执着于其名字称呼。
# 贪心算法方法二
可以换一个思路首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
如图 那么为什么一旦[0i] 区间和为负数起始位置就可以是i1呢i1后面就不会出现更大的负数
如果出现更大的负数就是更新i那么起始位置又变成新的i1了。
那有没有可能 [0i] 区间 选某一个作为起点累加到 i这里 curSum是不会小于零呢 如图 如果 curSum0 说明 区间和1 区间和2 0 那么 假设从上图中的位置开始计数curSum不会小于0的话就是 区间和20。
区间和1 区间和2 0 同时 区间和20只能说明区间和1 0 那么就会从假设的箭头初就开始从新选择其实位置了。
那么局部最优当前累加rest[i]的和curSum一旦小于0起始位置至少要是i1因为从i之前开始一定不行。全局最优找到可以跑一圈的起始位置。
局部最优可以推出全局最优找不出反例试试贪心
C代码如下
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int totalSum 0;int start 0;for (int i 0; i gas.size(); i) {curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if (curSum 0) { // 当前累加rest[i]和 curSum一旦小于0start i 1; // 起始位置更新为i1curSum 0; // curSum从0开始}}if (totalSum 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
};时间复杂度O(n)空间复杂度O(1)
说这种解法为贪心算法才是有理有据的因为全局最优解是根据局部最优推导出来的。
# 总结
对于本题首先给出了暴力解法暴力解法模拟跑一圈的过程其实比较考验代码技巧的要对while使用的很熟练。
然后给出了两种贪心算法对于第一种贪心方法其实我认为就是一种直接从全局选取最优的模拟操作思路还是很巧妙的值得学习一下。
对于第二种贪心方法才真正体现出贪心的精髓用局部最优可以推出全局最优进而求得起始位置。
三、力扣第135题分发糖果
题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。 提示
n ratings.length1 n 2 * 1040 ratings[i] 2 * 104
思路
这道题目一定是要确定一边之后再确定另一边例如比较每一个孩子的左边然后再比较右边如果两边一起考虑一定会顾此失彼。
先确定右边评分大于左边的情况也就是从前向后遍历
此时局部最优只要右边评分比左边大右边的孩子就多一个糖果全局最优相邻的孩子中评分高的右孩子获得比左边孩子更多的糖果
局部最优可以推出全局最优。
如果ratings[i] ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个所以贪心candyVec[i] candyVec[i - 1] 1
代码如下
// 从前向后
for (int i 1; i ratings.size(); i) {if (ratings[i] ratings[i - 1]) candyVec[i] candyVec[i - 1] 1;
}如图 再确定左孩子大于右孩子的情况从后向前遍历
遍历顺序这里有同学可能会有疑问为什么不能从前向后遍历呢
因为 rating[5]与rating[4]的比较 要利用上 rating[5]与rating[6]的比较结果所以 要从后向前遍历。
如果从前向后遍历rating[5]与rating[4]的比较 就不能用上 rating[5]与rating[6]的比较结果了 。如图 所以确定左孩子大于右孩子的情况一定要从后向前遍历
如果 ratings[i] ratings[i 1]此时candyVec[i]第i个小孩的糖果数量就有两个选择了一个是candyVec[i 1] 1从右边这个加1得到的糖果数量一个是candyVec[i]之前比较右孩子大于左孩子得到的糖果数量。
那么又要贪心了局部最优取candyVec[i 1] 1 和 candyVec[i] 最大的糖果数量保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优相邻的孩子中评分高的孩子获得更多的糖果。
局部最优可以推出全局最优。
所以就取candyVec[i 1] 1 和 candyVec[i] 最大的糖果数量candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多也比右边candyVec[i 1]的糖果多。
如图 所以该过程代码如下
// 从后向前
for (int i ratings.size() - 2; i 0; i--) {if (ratings[i] ratings[i 1] ) {candyVec[i] max(candyVec[i], candyVec[i 1] 1);}
}整体代码如下
class Solution {
public:int candy(vectorint ratings) {vectorint candyVec(ratings.size(), 1);// 从前向后for (int i 1; i ratings.size(); i) {if (ratings[i] ratings[i - 1]) candyVec[i] candyVec[i - 1] 1;}// 从后向前for (int i ratings.size() - 2; i 0; i--) {if (ratings[i] ratings[i 1] ) {candyVec[i] max(candyVec[i], candyVec[i 1] 1);}}// 统计结果int result 0;for (int i 0; i candyVec.size(); i) result candyVec[i];return result;}
};时间复杂度: O(n)空间复杂度: O(n)
# 总结
这在leetcode上是一道困难的题目其难点就在于贪心的策略如果在考虑局部的时候想两边兼顾就会顾此失彼。
那么本题我采用了两次贪心的策略
一次是从左到右遍历只比较右边孩子评分比左边大的情况。一次是从右到左遍历只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优即相邻的孩子中评分高的孩子获得更多的糖果。 day34补
