admin管理员组文章数量:1564695
tasks for today:
1. 122.买股票的最佳时机II
2. 55.跳跃游戏
3. 45.跳跃游戏II
4. 1005.K次取反后最大化的数组和
----------------------------------------------------------------------------------1. 122.买股票的最佳时机II
In this practice, the essence is actually record the assending amount, therefore, sa long as the prices[i] >= prices[i-1], the diff should be cummulated in result.
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 1: return 0
if len(prices) == 2: return max(0, prices[1] - prices[0])
result = 0
for i in range(1, len(prices)):
if prices[i] >= prices[i-1]:
result += (prices[i] - prices[i-1])
return result
2. 55.跳跃游戏
The essence of this practice is monitor if the max_id can be covered finally.
class Solution:
def canJump(self, nums: List[int]) -> bool:
cur = 0
max_id = 0
cur_max_len = 0
if len(nums) == 1: return True
# method 1
# python不支持动态修改for循环中变量,使用while循环代替
while cur <= cur_max_len:
max_id = cur + nums[cur]
if max_id > cur_max_len:
cur_max_len = max_id
if cur_max_len >= len(nums) - 1:
return True
cur += 1
# method 2
# 如果用for,就需要在内置一个if条件判断
for cur in range(len(nums)):
if cur <= cur_max_len:
max_id = cur + nums[cur]
if max_id > cur_max_len:
cur_max_len = max_id
if cur_max_len >= len(nums) - 1:
return True
return False
3. 45.跳跃游戏II
This practice's essence is when to "return result" and when to execute "result += 1". Also, when to update the search cover range.
The answer is the result += 1 is execute only when the cur exceed the current max range, also when this happens, the current max range should also be updated as next max range.
So being different from the last practice 55, the key point is to use two different variable to record the current max cover range and the next max cover range.
Besides, not just in this practice, also in other greedy practice, the dealing of special circumstance is important. The special circumstance should be considered comprehensively.
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1: return 0
if len(nums) == 2: return 1
cur = 0
cur_max = cur + nums[cur]
if cur_max >= len(nums) - 1:
return 1
next_max = 0
result = 1
while cur <= cur_max:
if cur + nums[cur] >= next_max:
next_max = cur + nums[cur]
if cur + nums[cur] >= len(nums) - 1:
return result + 1
cur += 1
if cur > cur_max:
cur_max = next_max
result += 1
return result
4. 1005.K次取反后最大化的数组和
This practice is easy, the following two methods can be used, to simplify the method1, the key operation is the sorting method according to the abs(x).
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
# method 1
record = []
record_left = []
for i in nums:
if i < 0:
record.append(i)
else:
record_left.append(i)
num_neg = len(record)
# print(num_neg)
record.sort()
if k == num_neg:
return sum(nums) - 2 * sum(record)
elif k < num_neg:
return sum(nums) - 2 * sum(record[:k])
elif k > num_neg:
if (k - num_neg) % 2 == 0:
return sum(nums) - 2 * sum(record)
else:
if num_neg == 0:
return sum(nums) - 2 * sum(record) - 2 * min(nums)
elif num_neg == len(nums):
return sum(nums) - 2 * sum(record) - 2 * (-max(record))
else:
return sum(nums) - 2 * sum(record) - 2 * min(-max(record), min(record_left))
# method 2
nums.sort(key=lambda x: abs(x), reverse=True) # 第一步:按照绝对值降序排序数组A
for i in range(len(nums)): # 第二步:执行K次取反操作
if nums[i] < 0 and k > 0:
nums[i] *= -1
k -= 1
if k % 2 == 1: # 第三步:如果K还有剩余次数,将绝对值最小的元素取反
nums[-1] *= -1
result = sum(nums) # 第四步:计算数组A的元素和
return result
本文标签: greedy
版权声明:本文标题:day28-greedy-part02-7.30 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1726617592a1078369.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论