代码随想录算法训练营第二十七天 | leetcode：K次取反后最大化的数组和,加油站,分发糖果
0 / 0 / 创建于 6个月前
_zzh 的个人博客
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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：