1005. K 次取反后最大化的數(shù)組和
- 思路
- example
- 可以多次選擇同一個下標 i 。
- 排序 + 貪心
- 負數(shù)（取反），非負數(shù) （取決于頻率）
- [-1,-2,3] ----> [1,2,3] --> [-1,2,3] (k=3)
- 計算負數(shù)個數(shù)
- 負數(shù)取反
- 新數(shù)組最小數(shù)字處理（取決于剩余次數(shù)的奇偶）
- 負數(shù)（取反），非負數(shù) （取決于頻率）
- 復雜度. 時間：O(n logn) 排序
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
n = len(nums)
nums.sort()
negative_cnt = 0
for i in range(n):
if nums[i] < 0:
negative_cnt += 1
else:
break
for i in range(min(negative_cnt, k)):
nums[i] = - nums[i]
rest = k - min(negative_cnt, k)
if rest % 2 == 0:
return sum(nums)
return sum(nums) - 2*min(nums)
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort() # !!!
n = len(nums)
cnt = 0
for i in range(n):
if nums[i] < 0:
cnt += 1
for i in range(min(cnt, k)):
nums[i] = -nums[i]
k -= min(cnt, k)
if k % 2 == 0:
return sum(nums)
else:
return sum(nums) - 2*min(nums)
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
nums.sort()
n = len(nums)
neg_cnt = 0
for i in range(n):
if nums[i] < 0:
neg_cnt += 1
else:
break
sum_ = sum(nums)
for i in range(min(neg_cnt, k)):
nums[i] = -nums[i]
sum_ += 2*(nums[i])
k -= neg_cnt
if k <= 0:
return sum_
if k % 2 == 0:
return sum_
return sum_ - 2*min(nums)
- 桶計數(shù) + 貪心牵素，時間: O(n+201)
- 利用 -100 <= nums[i] <= 100
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
res = sum(nums)
table = collections.defaultdict(int)
for num in nums:
table[num] += 1
for num in range(-100, 0):
if table[num] > 0:
freq = min(table[num], k)
res -= 2*freq*num
table[num] -= freq
table[-num] += freq
k -= freq
if k == 0:
return res
for num in range(0, 101):
if table[num] > 0:
if k % 2 == 0:
return res
else:
res -= 2*num
return res
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
sum_ = sum(nums)
freq = collections.defaultdict(int)
for num in nums:
freq[num] += 1
for num in range(-100, 0):
if freq[num] == 0:
continue
times = min(k, freq[num])
sum_ -= 2*num*times
freq[num] -= times
freq[-num] += times
k -= times
if k == 0:
return sum_
for num in range(0, 101):
if freq[num] == 0:
continue
if k % 2 == 0:
return sum_
else:
return sum_ - 2*num
class Solution:
def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
n = len(nums)
sum_ = sum(nums)
table = collections.defaultdict(int)
for i in range(n):
table[nums[i]] += 1
for num in range(-100, 0):
if table[num] == 0: #!!!
continue
freq = min(k, table[num])
table[num] -= freq #!!!
table[-num] += freq #!!!
sum_ -= 2*freq*num
k -= freq
if k == 0:
return sum_
for num in range(0, 101):
if table[num] > 0:
if k % 2 == 0:
return sum_
else:
return sum_ - 2*num
- 大根堆/小根堆
TBA
134. 加油站
- 思路
- example
- 如果題目有解，該答案即為唯一答案织中。
- 暴力法: 遍歷每一個加油站當作起點。模擬跑圈衷戈。
- 復雜度. 時間：
, 空間:
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
for i in range(len(gas)):
rest = gas[i] - cost[i]
nxt = (i+1) % len(gas)
while rest > 0 and nxt != i:
rest += gas[nxt] - cost[nxt]
nxt = (nxt+1) % len(gas)
if rest >= 0 and nxt == i:
return i
return -1
- 貪心法
- time:
, space:
- if sum(gas) < sum(cost): return -1 否則必有答案狭吼。
- 假設index為答案，則必有index, index+1, ..., index+k中剩余和 >= 0, 并且對之間的每個指標殖妇，剩余都是 >= 0
- 從i出發(fā)順序遍歷刁笙，一旦碰到j，使得當前剩余和 < 0,說明i,..., j-1全部不可能是起始點拉一。（反證法）
-
所以實際只需一次遍歷即可采盒。
- time:
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
if sum(gas) < sum(cost):
return -1
n = len(gas)
balance = 0
index = 0
for i in range(n):
balance += gas[i] - cost[i] # “到達”i+1時的balance
if balance < 0:
balance = 0
index = i + 1
return index
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
n = len(gas)
diff = [0 for _ in range(n)]
for i in range(n):
diff[i] = gas[i] - cost[i]
if sum(diff) < 0:
return -1
balance = 0
start = 0
for i in range(n):
balance += diff[i] # can we reach station i+1?
if balance < 0:
balance = 0 # restart, stations start, ..., i cannot be the answer
start = i+1
return start
135. 分發(fā)糖果
- 思路
example
-
返回需要準備的 最少糖果數(shù)目
從左到右遍歷，依據(jù)左鄰居信息更新candy數(shù)組蔚润。
-
從右到左遍歷磅氨，依據(jù)右鄰居信息更新candy數(shù)組。
- 復雜度. 時間：O(n), 空間: O(n)
class Solution:
def candy(self, ratings: List[int]) -> int:
candys = [1 for _ in range(len(ratings))]
for i in range(1, len(ratings)):
if ratings[i] > ratings[i-1]:
candys[i] = candys[i-1] + 1
# else: candys[i] = 1
for i in range(len(ratings)-2, -1, -1):
if ratings[i] > ratings[i+1]:
candys[i] = max(candys[i], candys[i+1]+1)
return sum(candys)
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
candies = [1 for _ in range(n)]
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
if candies[i] < candies[i+1] + 1:
candies[i] = candies[i+1] + 1
return sum(candies)
- 小根堆?
TBA
