网站建设工作整改报告,微网站模板制作,装修app排行榜前5名,注册科技公司流程和费用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] 。
解题思路
返回的数据是数组的和不是数组元素因此可以对输入的数组进行排序。按照贪心的思路排序后一直换小值即可这里需要注意的一点是数组有小于0的数如果想让和最大还需要尽可能的把负数都更换为正数这里给出的解题思路是将数组从达到小排序找到 数组中最大的小于0的数 的下标。然后依次把小于0的数组元素切换为正数。并K–如果替换到最后K还是大于0也即还有切换的次数那么若K为奇数则替换一次去反即可。若K为偶数那替换K次还是本身就不用再替换了。
那么本题的解题步骤为
第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小 第二步从前向后遍历遇到负数将其变为正数同时K– 第三步如果K还大于0那么反复转变数值最小的元素将K用完 第四步求和
代码
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;}
};135. 分发糖果
题目
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求给这些孩子分发糖果
每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
示例 1
输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例 2
输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、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;}
};
