代码随想录算法训练营第二十七天 | leetcode:K次取反后最大化的数组和,加油站,分发糖果
1005. K 次取反后最大化的数组和
注意的地方
- k次取反可以多次选择同一个元素,这点非常重要。
解题方法
- 先从小到大排序,开始遍历数组,从最小的数开始取反,同时k–。
- 判断k是否还有次数,如果K>0,则对k求余,如果==1则k剩余次数为单数,重新排序(因为数组存在负数,步骤1遍历后取反后,需要重新排序)后,对nums[0]取反即可。因为k次取反可以多次选择同一个元素,所以当k为复数时,无论取反多少次,都会等于本身,为单数时只需要取反一次即可。
Tips:实际最好的流程如下,因为php好像没有已封装的方法可以实现按照绝对值大小从大到小排序。于是手动修改快排返回结果按照绝对值大小从大到小排序后,再执行流程。时间复杂度还是不理想,所以得出现在的解法。按从小到大排序处理,需要两次sort();
- 第一步:将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
- 第二步:从前向后遍历,遇到负数将其变为正数,同时K–
- 第三步:如果K还大于0,那么反复转变数值最小的元素,将K用完
- 第四步:求和
复杂度
时间复杂度
O(nlogn)
空间复杂度
O(1)
code
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function largestSumAfterKNegations($nums, $k) {
sort($nums);
for($i = 0; $i <= count($nums); $i++){
if($nums[$i] < 0 && $k > 0){
$nums[$i] = - $nums[$i];
$k--;
}
}
if($k % 2 == 1){
sort($nums);
$nums[0] = -$nums[0];
}
return array_sum($nums);
}
}
55. 跳跃游戏
注意的问题
- 如果题目有解,该答案即为唯一答案。
- 输入数组均为非空数组,且长度相同。
- 输入数组中的元素均为非负数。
解题方法
从每一站的剩余油量开始考虑,如果当前剩余油量大于0,则代表可以开到下一个加油站。反之则不行。那么假设从0开始遍历,碰到gas[i] - cos[i] < 0的代表此前的一段,均不适合作为起点。需要重置剩余量,重新制定开始位置。直到遍历完数组,判断总剩余量是否小于0,如果小于0表示,一定无解,返回-1。否则返回start。
复杂度
时间复杂度
O(n)
空间复杂度
O(1)
code
class Solution {
/**
* @param Integer[] $gas
* @param Integer[] $cost
* @return Integer
*/
function canCompleteCircuit($gas, $cost) {
$surplus = 0;//当前剩余油量
$total = 0;//总剩余油量
$start = 0;//起始位置
for($i = 0; $i < count($gas); $i++){
$surplus += $gas[$i] - $cost[$i];
$total += $gas[$i] - $cost[$i];
if($surplus < 0){
//当i为起点时出现剩余油量小于0,所以不能作为起始位置,更新start,
$start = $i + 1;
//重置surplus
$surplus = 0;
}
}
//total<0 代表总加油量小于总消耗量
if($total < 0) return -1;
return $start;
}
}
135. 分发糖果
注意的问题
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中,评分高的孩子必须获得更多的糖果。
解题方法
- 分别按两个不同方向处理,右边相邻孩子与左边相邻孩子。
- 初始化与孩子数量相同的糖果数值Candy, 处理右边相邻孩子按从左到右遍历,当ratings[i] > ratings[i-1], Candy[i] = Candy[i - 1] + 1。处理左边孩子按从右到左方向遍历,当ratings[i] > ratings[i+1], Candy[i] = max(Candy[i+1],Candy[i])。]
复杂度
时间复杂度
O(n)
空间复杂度
O(n)
code
class Solution {
/**
* @param Integer[] $ratings
* @return Integer
*/
function candy($ratings) {
$length = count($ratings);
$Candy[0] = 1;//初始化candy[0]
$sum = 0;
//处理相邻右孩子,因为要比较i, i-1,所以从i=1开始遍历
for($i = 1; $i < $length; $i++){
//糖果赋默认值
$Candy[$i] = 1;
//比较相邻右孩子,处理糖果数量
if($ratings[$i] > $ratings[$i - 1]) $Candy[$i] = $Candy[$i - 1] + 1;
}
//处理相邻右孩子,因为要比较i, i+1,所以从length - 2开始遍历
for($i = $length - 2; $i >= 0; $i--){
//比较相邻左孩子,处理糖果数量,因为相邻孩子(或左或右)较大都需要获得更多的糖果,那么取当前最大值即可满足两边需求
if($ratings[$i] > $ratings[$i + 1]) $Candy[$i] = max($Candy[$i + 1] + 1, $Candy[$i]);
}
for($i=0;$i<$length;$i++){
$sum += $Candy[$i];
}
return $sum;
}
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
推荐文章: