K次取反后最大化的数组和
1005. K 次取反后最大化的数组和 - 力扣(LeetCode)
贪心算法,将所有的负值取反后,若剩余k为偶数,则不变,得到的为最大值,若为奇数,则将取反后数组中最小的元素取反,计算得到最大值。
这里使用了两次排序,第一次排序后将小于等于k次数的负数取反,得到数组中所有值求绝对值的和,之后再排一次序,则数组第一个元素为最小的元素,此时若剩余的k为奇数,则和减去2倍该元素,并返回和,否则直接返回和。
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
// 首先,对数组进行排序,以便于从最大的负数开始进行处理。
sort(nums.begin(), nums.end());
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
// 如果当前数字是负数,且我们还有可用的反转次数(k>0),
// 那么将这个负数变为正数,并更新总和和反转次数。
if (nums[i] < 0 && k > 0) {
nums[i] *= -1;
sum += nums[i];
k--;
} else {
// 如果当前数字是非负数,或者没有剩余的反转次数,
// 直接将这个数字加到总和上。
sum += nums[i];
}
}
// 再次对数组进行排序,方便找到最小的数
sort(nums.begin(), nums.end());
// 如果剩余的反转次数是偶数,那么可以忽略不计,因为偶数次反转不会改变数组的和。
// 如果剩余的反转次数是奇数,那么需要将最小的数字(现在是正数)变为负数,
// 因为这将是最小的损失。由于之前已经对数组进行了排序,最小的数字是nums[0]。
if (k % 2 == 0) {
return sum;
} else {
// 由于最小的数字被反转了一次,所以需要从总和中减去两倍的这个最小数字。
return sum - 2 * nums[0];
}
}
};
算法的时间复杂度为O(nlogn),遍历一次数组,两次排序,综合为O(nlogn)。
空间复杂度为O(1)。
加油站
暴力法
对每个站点,都模拟一次,是否能跑回初始点,算法的时间复杂度为O(n^2)。模拟转圈的过程用while比较好,但暴力解法会超时,具体代码如下。
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int count = gas.size(); // 获取加油站的数量
for(int i = 0; i < count; i++){ // 遍历每个加油站作为起始点
int start = i; // 起始加油站
int cur = i; // 当前加油站
int cur_gas = gas[start]; // 当前油箱中的汽油量
while(cur_gas!=0){ // 当油箱中还有汽油时
cur_gas -= cost[cur]; // 从当前油箱中减去到下一个加油站所需的汽油
if(cur_gas<0) // 如果油量小于0,说明无法到达下一个加油站
break; // 退出循环
cur = (cur + 1) % count; // 移动到下一个加油站
cur_gas += gas[cur]; // 加上下一个加油站的汽油量
if(cur == start){ // 如果回到起始加油站
return start; // 返回起始加油站的位置
}
}
}
return -1; // 如果没有找到合适的起始加油站,返回-1
}
};
算法时间复杂度O(n^2),空间复杂度为O(1)。
贪心算法
每到一个站点,都有消耗和补充,根据每个站点的gas和cost数组相减能得到一个数组,代表经过该站点的消耗或补充,若想要能够走完一圈,则消耗需小于等于补充,具体参考代码随想录视频。
贪心算法,得这么加油才能跑完全程!LeetCode :134.加油站_哔哩哔哩_bilibili
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int n = gas.size(); // 获取加油站的数量
int totalGas = 0, currentGas = 0, start = 0; // 定义总汽油量、当前汽油量和起始加油站
for (int i = 0; i < n; ++i) { // 遍历每个加油站
totalGas += gas[i] - cost[i]; // 计算总汽油量(所有加油站的汽油量减去消耗量)
currentGas += gas[i] - cost[i]; // 计算当前汽油量(从起始站到当前站的净汽油量)
if (currentGas < 0) { // 如果当前汽油量不足以到达下一个加油站
currentGas = 0; // 重置当前汽油量为0
start = i + 1; // 更新起始加油站为下一个加油站
}
}
return totalGas >= 0 ? start : -1; // 如果总汽油量大于等于0,返回起始加油站,否则返回-1
}
};
算法的时间复杂度为O(n),空间复杂度为O(1)。
分发糖果
分发糖果由于若一个分数大于两侧的分数,则它得到的糖果数一定要是这3人中最多的,所以有两个方向需要考虑,贪心也就是考虑在这两个方向上,由于一次考虑两个方向同时考虑很难做,所以简化为考虑两次。
考虑先创建一个长度为ratings的全为1的数组candy_distribution,表示分发的糖果数目,之后考虑先从左开始,根据题意,若当前元素大于前一个元素,则当前位置的分发糖果数目为前一个位置分发数目+1,经过一次循环后,在单方向上,得到了符合分发糖果的最少且都满足要求的糖果分发数组。之后再遍历一次,从右向左,判断当前元素是否大于后一个元素,且在糖果分发数组中,当前元素小于或等于后一个元素,若是,则将糖果分发数组当前元素 = 糖果分发数组后方元素 +1,即在两个方向上都完成了要求,此时分发的糖果总数也是最少的。
class Solution {
public:
int candy(vector<int>& ratings) {
// 创建一个与ratings同大小的数组candy_distribution,用于存储每个孩子应得的糖果数。
// 初始化所有孩子的糖果数为1,因为每个孩子至少得到一颗糖果。
vector<int> candy_distribution(ratings.size(), 1);
// 从左到右遍历孩子,确保评分更高的孩子得到更多的糖果。
for (int i = 1; i < ratings.size(); i++) {
if (ratings[i] > ratings[i - 1]) {
// 如果当前孩子的评分比前一个孩子高,那么他应该得到比前一个孩子多一颗糖果。
candy_distribution[i] = candy_distribution[i - 1] + 1;
}
}
// 从右到左遍历孩子,确保评分更高的孩子得到更多的糖果。
for (int i = ratings.size() - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1] && candy_distribution[i] <= candy_distribution[i + 1]) {
// 如果当前孩子的评分比后一个孩子高,并且当前孩子的糖果数不大于后一个孩子的糖果数,
// 那么当前孩子应该得到比后一个孩子多一颗糖果。
candy_distribution[i] = candy_distribution[i + 1] + 1;
}
}
// 使用accumulate函数计算所有孩子糖果数的总和,这就是最少需要的糖果数。
return accumulate(candy_distribution.begin(), candy_distribution.end(), 0);
}
};
算法的时间复杂度为O(n),两次遍历,一次求和(所以是三次遍历)。
空间复杂度O(n),维护一个数组用于保存分发的糖果数目。