本文目录
- 1005.K次取反后最大化的数组和
- 做题
- 看文章
- 134. 加油站
- 做题
- 看文章
- 解法1
- 解法2
- 135. 分发糖果
- 做题
- 看文章
- 以往忽略的知识点小结
- 个人体会
1005.K次取反后最大化的数组和
代码随想录:1005.K次取反后最大化的数组和
Leetcode:1005.K次取反后最大化的数组和
做题
无实现思路。
看文章
解题步骤为:
- 将数组按照绝对值大小从大到小排序,注意要按照绝对值的大小
- 从前向后遍历,遇到负数将其变为正数,同时K–
- 如果K还大于0,那么反复转变数值最小的元素,将K用完
- 求和
class Solution:
def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
A.sort(key=lambda x: abs(x), reverse=True) # 第一步:按照绝对值降序排序数组A
for i in range(len(A)): # 第二步:执行K次取反操作
if A[i] < 0 and K > 0:
A[i] *= -1
K -= 1
if K % 2 == 1: # 第三步:如果K还有剩余次数,将绝对值最小的元素取反
A[-1] *= -1
result = sum(A) # 第四步:计算数组A的元素和
return result
时间复杂度: O(nlogn)
空间复杂度: O(1)
134. 加油站
代码随想录:134. 加油站
Leetcode:134. 加油站
做题
无思路。
看文章
解法1
直接从全局进行贪心选择,情况如下:
- 情况一:如果gas的总和小于cost总和,那么无论从哪里出发,一定是跑不了一圈的。
- 情况二:rest[i] = gas[i]-cost[i]为一天剩下的油,i从0开始计算累加到最后一站,如果累加没有出现负数,说明从0出发,油就没有断过,那么0就是起点。
- 情况三:如果累加的最小值是负数,汽车就要从非0节点出发,从后向前,看哪个节点能把这个负数填平,能把这个负数填平的节点就是出发节点。
具体代码如下:
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
curSum = 0 # 当前累计的剩余油量
minFuel = float('inf') # 从起点出发,油箱里的油量最小值
for i in range(len(gas)):
rest = gas[i] - cost[i]
curSum += rest
if curSum < minFuel:
minFuel = curSum
if curSum < 0:
return -1 # 情况1:整个行程的总消耗大于总供给,无法完成一圈
if minFuel >= 0:
return 0 # 情况2:从起点出发到任何一个加油站时油箱的剩余油量都不会小于0,可以从起点出发完成一圈
for i in range(len(gas) - 1, -1, -1):
rest = gas[i] - cost[i]
minFuel += rest
if minFuel >= 0:
return i # 情况3:找到一个位置使得从该位置出发油箱的剩余油量不会小于0,返回该位置的索引
return -1 # 无法完成一圈
时间复杂度:O(n)
空间复杂度:O(1)
这种方式不太算贪心算法,因为没有找出局部最优,而是直接从全局最优的角度上思考问题。但这种解法又说不出是什么方法,这就是一个从全局角度选取最优解的模拟操作。
解法2
局部最优:当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行。全局最优:找到可以跑一圈的起始位置。具体代码如下:
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
curSum = 0 # 当前累计的剩余油量
totalSum = 0 # 总剩余油量
start = 0 # 起始位置
for i in range(len(gas)):
curSum += gas[i] - cost[i]
totalSum += gas[i] - cost[i]
if curSum < 0: # 当前累计剩余油量curSum小于0
start = i + 1 # 起始位置更新为i+1
curSum = 0 # curSum重新从0开始累计
if totalSum < 0:
return -1 # 总剩余油量totalSum小于0,说明无法环绕一圈
return start
时间复杂度:O(n)
空间复杂度:O(1)
135. 分发糖果
代码随想录:135. 分发糖果
Leetcode:135. 分发糖果
做题
测试能通过,但提交无法AC。
看文章
要确定一边之后,再确定另一边,例如比较每一个孩子的左边,然后再比较右边,如果两边一起考虑一定会顾此失彼。
具体代码如下:
class Solution:
def candy(self, ratings: List[int]) -> int:
candyVec = [1] * len(ratings)
# 从前向后遍历,处理右侧比左侧评分高的情况
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
candyVec[i] = candyVec[i - 1] + 1
# 从后向前遍历,处理左侧比右侧评分高的情况
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)
# 统计结果
result = sum(candyVec)
return result
时间复杂度: O(n)
空间复杂度: O(n)
以往忽略的知识点小结
- 贪心算法无套路,要多积累
个人体会
完成时间:2h。
心得:贪心算法比较难,无套路,要多积累。