临沂网站建设选盛誉,威海住房和城乡建设厅网站,俄文企业网站建设,怎样做网站的优化排名leetcode 1005. K 次取反后最大化的数组和
1005. K 次取反后最大化的数组和
给你一个整数数组 nums 和一个整数 k #xff0c;按以下方法修改该数组#xff1a;
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以…leetcode 1005. K 次取反后最大化的数组和
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] 。 代码
// leetcode 1005. K 次取反后最大化的数组和
// 先排序把负数取反
// 如果负数全部取反之后还没到k次 就重新排序只取反最小值
class Solution {
public:int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end());for (int i 0; i nums.size() k 0; i){if (nums[i] 0){break;}nums[i] * -1;k--;}sort(nums.begin(), nums.end());int result 0;if (k 0 || k % 2 0){result nums[0];}else{result -1 * nums[0];}for (int i 1; i nums.size(); i){result nums[i];}return result;}
};// 代码随想录的版本比我的轻量的多我这边有两次排序卡尔的只需要第一次按绝对值排序即可
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;}
};
leetcode 134. 加油站
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 升汽油。
因此无论怎样你都不可能绕环路行驶一周。 代码
// leetcode 134. 加油站// 暴力解法 但是暴力是超时的
// 遍历找到第一个cost[i] gas[i]的索引然后遍历
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int size cost.size();for (int i 0; i size; i){int rest gas[i] - cost[i];int index (i 1) % size;while (rest 0 index ! i){rest gas[index] - cost[index];index (index 1) % size;}if (rest 0 index i){return i;}}return -1;}
};// 贪心算法
// 保存 gas - cost
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int totalSum 0;int result 0;for (int i 0; i gas.size(); i){int rest gas[i] - cost[i];curSum rest;totalSum rest;if (curSum 0){result i 1;curSum 0;}}if (totalSum 0){return -1;}return result;}
};
