面试必刷TOP101:贪心算法(95-96,Python实现)
95.分糖果问题(小试牛刀)
95.1 贪心思想
要想分出最少的糖果,利用贪心思想,肯定是相邻位置没有增加的情况下,大家都分到1,相邻位置有增加的情况下,分到糖果数加1就好。什么情况下会增加糖果,相邻位置有得分差异,可能是递增可能是递减,如果是递增的话,糖果依次加1,如果是递减糖果依次减1?这不符合最小,因为减到最后一个递减的位置可能不是1,必须从1开始加才是最小,那我们可以从最后一个递减的位置往前反向加1。
step 1:使用一个辅助数组记录每个位置的孩子分到的糖果,全部初始化为 1。
step 2:从左到右遍历数组,如果右边元素比相邻左边元素大,意味着在递增,糖果数就是前一个加 1,否则保持 1 不变。
step 3:从右到左遍历数组,如果左边元素比相邻右边元素大, 意味着在原数组中是递减部分,如果左边在上一轮中分到的糖果数更小,则更新为右边的糖果数 +1,否则保持不变。
step 4:将辅助数组中的元素累加求和。
class Solution:
def candy(self , arr: List[int]) -> int:
# 记录每个位置的糖果数,初始为 1
nums = [1] * len(arr)
# 从左到右遍历
for i in range(1,len(arr)):
# 如果右边在递增,每次增加一个
if arr[i] > arr[i-1]:
nums[i] = nums[i-1] + 1
i = len(arr) - 2
# 从右到左遍历
for i in range(len(arr)-2,-1,-1):
# 如果左边更大但是糖果数更小
if arr[i] > arr[i+1] and nums[i] <= nums[i+1]:
nums[i] = nums[i+1] + 1
return sum(nums)
时间复杂度:
O
(
n
)
O(n)
O(n),单独遍历两次。
空间复杂度:
O
(
n
)
O(n)
O(n),记录每个位置糖果数的辅助数组。
96.主持人调度(二)(小试牛刀)
96.1 排序+遍历
我们利用贪心思想,什么时候需要的主持人最少?那肯定是所有的区间没有重叠,每个区间首和上一个的区间尾都没有相交的情况,我们就可以让同一位主持人不辞辛劳,一直主持了。但是题目肯定不是这种理想的情况,那我们需要对交叉部分,判断需要增加多少位主持人。
step 1: 利用辅助数组获取单独各个活动开始的时间和结束时间,然后分别开始时间和结束时间进行排序,方便后面判断是否相交。
step 2: 遍历 n 个活动,如果某个活动开始的时间大于之前活动结束的时候,当前主持人就够了,活动结束时间往后一个。
step 3: 若是出现之前活动结束时间晚于当前活动开始时间的,则需要增加主持人。
不理解可以画图!
class Solution:
def minmumNumberOfHost(self , n: int, startEnd: List[List[int]]) -> int:
start = []
end = []
# 分别得到活动起始时间
for i in range(n):
start.append(startEnd[i][0])
end.append(startEnd[i][1])
# 分别对开始和结束时间排序
start.sort()
end.sort()
res = 0
j = 0
for i in range(n):
# 新开始的节目大于上一轮结束的时间,主持人不变
if start[i] >= end[j]:
j = j + 1
else:
# 主持人增加
res = res + 1
return res
时间复杂度:
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n),遍历都是
O
(
n
)
O(n)
O(n),sort排序为
O
(
n
l
o
g
2
n
)
O(nlog_2n)
O(nlog2n)
空间复杂度:
O
(
n
)
O(n)
O(n),辅助空间记录开始时间和结束时间的数组
该问题类比于:同一时间最多重叠区间个数。