題目簡(jiǎn)介
1005. K 次取反后最大化的數(shù)組和
給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k 家淤，按以下方法修改該數(shù)組：
選擇某個(gè)下標(biāo) i 并將 nums[i] 替換為 -nums[i] 勺馆。
重復(fù)這個(gè)過(guò)程恰好 k 次绣否。可以多次選擇同一個(gè)下標(biāo) i 胞谈。
以這種方式修改數(shù)組后，返回?cái)?shù)組 可能的最大和 。
134. 加油站
在一條環(huán)路上有 n 個(gè)加油站啡浊，其中第 i 個(gè)加油站有汽油 gas[i] 升。
你有一輛油箱容量無(wú)限的的汽車(chē)胶背，從第 i 個(gè)加油站開(kāi)往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升巷嚣。你從其中的一個(gè)加油站出發(fā)，開(kāi)始時(shí)油箱為空钳吟。
給定兩個(gè)整數(shù)數(shù)組 gas 和 cost 廷粒，如果你可以按順序繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號(hào)红且，否則返回 -1 坝茎。如果存在解，則 保證 它是 唯一 的暇番。
135. 分發(fā)糖果
n 個(gè)孩子站成一排嗤放。給你一個(gè)整數(shù)數(shù)組 ratings 表示每個(gè)孩子的評(píng)分。
你需要按照以下要求壁酬，給這些孩子分發(fā)糖果：
每個(gè)孩子至少分配到 1 個(gè)糖果次酌。
相鄰兩個(gè)孩子評(píng)分更高的孩子會(huì)獲得更多的糖果恨课。
請(qǐng)你給每個(gè)孩子分發(fā)糖果，計(jì)算并返回需要準(zhǔn)備的 最少糖果數(shù)目 岳服。
初見(jiàn)思路
- 按照絕對(duì)值倒序排序剂公，將負(fù)值轉(zhuǎn)換為正，如果最后剩余K值吊宋，將絕對(duì)值最小的變?yōu)樨?fù)纲辽。
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums = sorted(nums,reverse=True,key=lambda x:abs(x))
for i in range(len(nums)):
if nums[i] < 0 and k > 0:
nums[i] *= -1
k -= 1
if k % 2 == 1:
nums[-1] *= -1
return sum(nums)
134.如果唯一路徑存在，那么從唯一合法起點(diǎn)開(kāi)始贫母，全局的剩余耗油應(yīng)該大于0文兑，且唯一合法起點(diǎn)的載油量應(yīng)該是大于0的，由此可以得到以下解腺劣，和貪心思想關(guān)系并不大了：
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if len(gas) == 0:
return -1
total,cur = 0,0
start = 0
for i in range(len(gas)):
cur += gas[i] - cost[i]
total += gas[i] - cost[i]
if cur < 0:
start = i + 1
cur = 0
return start if total >= 0 else -1
做題的時(shí)候绿贞，第一步還是先觀(guān)察題目中是否存在某些特殊的數(shù)字規(guī)律，能用特殊規(guī)律橘原，不輕易套算法模板籍铁。
- 對(duì)于這道題的兩端比較，從左到右一次趾断，從右到左一次就好拒名。這種做法可以用到很多需要考慮兩端值的場(chǎng)景上，記住做不了O(N) 的時(shí)候想2*O(N).
class Solution:
def candy(self, ratings: List[int]) -> int:
candy_vec = [1] * len(ratings)
for i in range(1,len(ratings)):
if ratings[i] > ratings[i - 1]:
candy_vec[i] = candy_vec[i-1] + 1
for i in range(len(ratings)-2,-1,-1):
if ratings[i] > ratings[i+1]:
candy_vec[i] = max(candy_vec[i+1]+1,candy_vec[i])
return sum(candy_vec)
復(fù)盤(pán)思路
https://programmercarl.com/0134.%E5%8A%A0%E6%B2%B9%E7%AB%99.html
https://programmercarl.com/0135.%E5%88%86%E5%8F%91%E7%B3%96%E6%9E%9C.html
