1005. K 次取反后最大化的数组和
- 思路
- example
- 可以多次选择同一个下标 i 。
- 排序 + 贪心
- 负数（取反），非负数 （取决于频率）
- [-1,-2,3] ----> [1,2,3] --> [-1,2,3] (k=3)
- 计算负数个数
- 负数取反
- 新数组最小数字处理（取决于剩余次数的奇偶）
- 负数（取反），非负数 （取决于频率）
- 复杂度. 时间：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)
- 桶计数 + 贪心，时间: 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出发顺序遍历，一旦碰到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. 分发糖果
- 思路
example
-
返回需要准备的 最少糖果数目
从左到右遍历，依据左邻居信息更新candy数组。
-
从右到左遍历，依据右邻居信息更新candy数组。
- 复杂度. 时间：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
