江门企业网站建设,wordpress金融主题,做淘宝要网站?,网站目录做别的内容1005.K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣#xff08;LeetCode#xff09;
代码随想录 (programmercarl.com)
贪心算法#xff0c;这不就是常识#xff1f;还能叫贪心#xff1f;LeetCode#xff1a;1005.K次取反后最大化的数组和_哔哩哔…1005.K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣LeetCode
代码随想录 (programmercarl.com)
贪心算法这不就是常识还能叫贪心LeetCode1005.K次取反后最大化的数组和_哔哩哔哩_bilibili 给你一个整数数组 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 第一次贪心局部最优绝对值最大的负数变成正数全局最优和最大
第二次贪心局部最优数值小的正数变成负数全局最优和最大
具体步骤
1、将数组按照绝对值大小从大到小排列
2、遍历数组
3、遇到负数就将负数变为正数同时k--
4、负数改完了k仍然不为0、
5、将数组末尾的最小的正数值反复变负数又变正数直到k0
class Solution {public int largestSumAfterKNegations(int[] nums, int K) {// 将数组按照绝对值大小从大到小排序注意要按照绝对值的大小nums IntStream.of(nums) // 将原始数组转换为 IntStream.boxed() // 装箱将基本数据类型转换为包装类型以便使用 sorted 方法.sorted((o1, o2) - Math.abs(o2) - Math.abs(o1)) // 按绝对值大小排序.mapToInt(Integer::intValue).toArray(); // 将排序后的 IntStream 转换为 int 数组int len nums.length; // 数组长度for (int i 0; i len; i) {// 从前向后遍历遇到负数将其变为正数同时 K--if (nums[i] 0 K 0) {nums[i] -nums[i]; // 将负数变为正数K--; // K 减一}}// 如果 K 还大于 0那么反复转变数值最小的元素直到 K 用完if (K % 2 1) nums[len - 1] -nums[len - 1]; // 如果 K 为奇数将最后一个元素变为负数return Arrays.stream(nums).sum(); // 返回数组元素的和}
} 134. 加油站 134. 加油站 - 力扣LeetCode 代码随想录 (programmercarl.com) 贪心算法得这么加油才能跑完全程LeetCode 134.加油站_哔哩哔哩_bilibili 在一条环路上有 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 假设有以下情况 当汽车从下标为0的位置开始走当走到下标为3的位置时 剩余的油不够在这里的消耗所以没有办法走到尾部此时从下标为4的位置重新开始走代码如下
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {// 初始化当前累计油量、总累计油量和起始加油站索引int curSum 0;int totalSum 0;int index 0;// 遍历每个加油站for (int i 0; i gas.length; i) {// 计算当前累计油量和总累计油量curSum gas[i] - cost[i];totalSum gas[i] - cost[i];// 如果当前累计油量为负则说明无法从当前加油站出发更新起始加油站索引并将当前累计油量重置为0if (curSum 0) {index (i 1);curSum 0;}}// 如果总累计油量为负则说明无法绕行一圈返回-1否则返回起始加油站索引if (totalSum 0) return -1;return index;}
}135. 分发糖果 135. 分发糖果 - 力扣LeetCode 代码随想录 (programmercarl.com) 贪心算法两者兼顾很容易顾此失彼LeetCode135.分发糖果_哔哩哔哩_bilibili 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 精髓在于不要同时比较左右。 先从前向后遍历确定右边评分大于左边的情况再从后往前遍历确定左边评分大于右边的情况。 从前向后遍历确定右边评分大于左边的情况 局部最优右边评分比左边大右边的孩子就多一颗糖果全局最优相邻孩子中评分高的右孩子比左孩子获得更多的糖果。 for (int i 1; i len; i) {candyVec[i] (ratings[i] ratings[i - 1]) ? candyVec[i - 1] 1 : 1;} 此时结果如图 再确定左孩子大于右孩子的情况从后向前遍历 // 第二次遍历从右往左分糖果只要左边的孩子评分比右边的大左边的孩子的糖果数应该取本身的糖果数和右边孩子糖果数 1 二者的最大值for (int i len - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}综合代码 class Solution {/*** 分两个阶段* 1、起点下标1 从左往右只要 右边 比 左边 大右边的糖果左边 1* 2、起点下标 ratings.length - 2 从右往左 只要左边 比 右边 大此时 左边的糖果应该 取本身的糖果数符合比它左边大 和 右边糖果数 1 二者的最大值这样才符合 它比它左边的大也比它右边大*/public int candy(int[] ratings) {int len ratings.length; // 计算评分数组的长度int[] candyVec new int[len]; // 创建一个与评分数组等长的数组用于存储每个孩子分到的糖果数量candyVec[0] 1; // 第一个孩子至少分到一个糖果// 第一次遍历从左往右分糖果只要右边的孩子评分比左边的大右边的孩子糖果数就比左边多1for (int i 1; i len; i) {candyVec[i] (ratings[i] ratings[i - 1]) ? candyVec[i - 1] 1 : 1;}// 第二次遍历从右往左分糖果只要左边的孩子评分比右边的大左边的孩子的糖果数应该取本身的糖果数和右边孩子糖果数 1 二者的最大值for (int i len - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}// 计算总共需要的糖果数int ans 0;for (int num : candyVec) {ans num;}return ans; // 返回总共需要的糖果数}
}
