陇南市建设局网站公示,网站建设网站排行,IC 网站建设,郑州信息网首页1005 k次取反后最大化的数组和
题目描述
给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a;
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后#xff0c;返回…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--第三步如果K还大于0那么反复转变数值最小的元素将K用完第四步求和
acm模式代码
#include iostream
#include vector
#include algorithmclass Solution {
static bool cmp(int a, int b) {return abs(a) abs(b);
}public:int largestSumAfterKNegations(std::vectorint nums, int k) {//第一次贪心std::sort(nums.begin(), nums.end(), cmp);for (int i 0; i nums.size(); i) {if (nums[i] 0 k 0) {nums[i] * -1;k --;}}// 第二次贪心if (k % 2 1) {nums[nums.size() - 1] * -1;}int sum 0;for(int i 0; i nums.size(); i) {sum nums[i];}return sum;}
};int main() {std::vectorint nums {3,-1,0,2};int k 3;Solution sol;int result sol.largestSumAfterKNegations(nums, k);std::cout maxsum: result std::endl;return 0;
}
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 题目分析
首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]和记为curSum一旦curSum小于零说明[0, i]区间都不能作为起始位置因为这个区间选择任何一个位置作为起点到i这里都会断油那么起始位置从i1算起再从0计算curSum。
acm模式代码
#include iostream
#include vectorclass Solution {
public:int canCompleteCircuit(std::vectorint gas, std::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) {start i 1;cursum 0;}}if (totalsum 0) return -1;return start;}
};int main() {std::vectorint gas {1,2,3,4,5};std::vectorint cost {3,4,5,1,2};Solution sol;int start sol.canCompleteCircuit(gas, cost);std::cout start: start std::endl;return 0;
}
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
题目分析
其难点就在于贪心的策略如果在考虑局部的时候想两边兼顾就会顾此失彼。
那么本题我采用了两次贪心的策略
一次是从左到右遍历只比较右边孩子评分比左边大的情况。一次是从右到左遍历只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优即相邻的孩子中评分高的孩子获得更多的糖果。
acm模式代码
#include iostream
#include vector
#include algorithmclass Solution {
public:int candy(std::vectorint ratings) {std::vectorint result(ratings.size(), 1);for (int i 0; i ratings.size() - 1; i) {if (ratings[i] ratings[i 1]) {result[i 1] result[i] 1;}}for (int i ratings.size() - 1; i 0; i--) {if (ratings[i - 1] ratings[i]) {result[i - 1] std::max(result[i - 1],result[i] 1); }}int sum 0;for (int i: result) {sum i;}return sum;}
};int main() {std::vectorint ratings {1,2,2};Solution sol;int sum sol.candy(ratings);std::cout sum: sum std::endl;
}
