LeeCode.135 分发糖果
题目描述
题目链接:https://leetcode.cn/problems/candy/?envType=study-plan-v2&envId=top-interview-150
n
个孩子站成一排,给定一个整数数组表示每个孩子的评分。
你需要按照以下要求,给这些孩子分发糖果:
- 每个孩子至少分配到
1
个糖果。 - 相邻两个孩子,评分更高的孩子会获得更多的糖果
请给每个孩子分发糖果,计算并返回需要准备的最少糖果数目。
示例一:
输入:ratings=[1,0,2]
输出:5
解释:你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果
示例二:
输入:ratings=[1,2,2]
输出:4
解释:你可以分别给第一个、第二个、第三个孩子分别分发1、2、1颗糖果。
第三个孩子只得到1颗糖果,满足题面中的两个条件。
提示:
n==rating.length
1<=n<=2*10^4
0<=rating[i]<=2*10^4
解题思路
考虑使用贪心的思想进行求解,即对对相邻的学生A
和学生B
(A
在B
左侧),应该满足:
- 如果ratings_B>ratings_A,B的糖果比A多
- 如果rating_A>ratings_B,A的糖果比B多
因此,要得出满足题目要求的答案,可以分别从左到右、从右到左遍历两条规则,取二者的最大值,从而满足题目条件。
算法流程
- 首先从左到右遍历
ratings
,将糖果记录在left_list
中
1.先给所有学生一颗糖;- 对于学生
i
来说,如果相邻右侧i+1
学生的分数更高,则将其糖果数量更改为left_list[i]+1
; - 如果学生
i+1
的分数比学生i
低,不做处理(在第二轮遍历中处理)。
- 对于学生
- 接着从右到左遍历学生层级,将糖果数量记录在
right_list
中,完成对第二条规则的匹配。 - 取
left_list
和right_list
每个元素的最大值,该值可以同时满足上述两条规则,sum
后即得到每个同学的最少糖果数量。
复杂度分析
- 空间复杂度O(N):建立了两个长度为n的列表保存两轮遍历的糖果数量
- 时间复杂度O(N):两轮遍历,没有嵌套
解题代码
class Solution:
def candy(self, ratings: List[int]) -> int:
n=len(ratings)
left_list=[1]*n
right_list=[1]*n
#遍历左规则
for i in range(1,n):
if ratings[i]>ratings[i-1]:
left_list[i]=left_list[i-1]+1
count=left_list[-1]
#遍历右规则
for i in range(n-2,-1,-1):
if ratings[i]>ratings[i+1]:
right_list[i]=right_list[i+1]+1
count+=max(left_list[i],right_list[i])
return count
LeeCode.42 接雨水
题目描述
题目链接:https://leetcode.cn/problems/trapping-rain-water/description/?envType=study-plan-v2&envId=top-interview-150
给定n
个非负整数表示每个宽度为1
的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
示例1:
输入:height=[0,1,0,2,1,0,1,3,2,1,2,1]
输出:6
解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
解题思路
对于下标i,下雨后能够达到的最大高度等于下标i两边高度的最小值,下标i处能够存储的雨量等于下标i处水能达到的最大高度减去height[i],因此,在解题时,可以分别遍历下标i左侧和右侧的最大高度,然后计算每个下标位置能接的雨水量,考虑使用动态规划的方法减少计算复杂度。
- 创建两个长度为n的数组leftMax和rightMax,分别表示左侧和右侧的最大高度
- 对leftMax进行正向遍历,初值为height[0],对rightMax进行反向遍历,初值为height[n-1],遍历方法如下:
- 当1/leqi/leqn-1时,leftMax[i]=max(leftMax[i-1],height[i]);
- 当0/leqi/leqn-2时,rightMax[i]=max(rightMax[i+1],height[i])
- 在得到数组leftMax和rightMax的每个元素值后,下标i出能接的雨水量等于min(leftMax[i],rightMax[i])-height[i],遍历每个下标既得到雨水总量
复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(n)
示例代码
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n=len(height)
#对左侧最大值赋初始值
leftMax=[height[0]]+[0]*(n-1)
for i in range(1,n):
leftMax[i]=max(leftMax[i-1],height[i])
#对右侧最大值赋初值
rightMax=[0]*(n-1)+[height[n-1]]
for i in range(n-2,-1,-1):
rightMax[i]=max(rightMax[i+1],height[i])
return sum(min(leftMax[i],rightMax[i])-height[i] for i in range(n))
最小矩阵乘法次数
题目描述
求解n个矩阵的连乘所需要的最小乘法次数
解题思路
- 首先,初始化长度为1的连乘矩阵的乘法次数都为零,因为矩阵本身不需要乘法
- 遍历分割点k,计算两部分的乘法次数,并加上当前矩阵乘法的次数
- 返回dp[1][n-1],即为所有矩阵连乘所需要的最小乘法次数
解题代码
def matrixChainOrder(p):
n=len(p) # 矩阵个数
dp=[[0]*n for _ in range(n)]
# 初始化长度为1的连乘矩阵的乘法次数都为0
for i in range(1,n):
dp[i][i]=0
# 逐个计算不同连乘链长度的最小乘法次数
for L in range(2,n):
for i in range(1,n-L+1):
j=L+i-1
dp[i][j]=float('inf') # 初始化次数为正无穷
# 计算不同分割点下的最小乘法次数
for k in range(i,j):
count=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]
if count<dp[i][j]:
dp[i][j]=count
# 返回所有矩阵连乘的最小乘法次数
return dp[1][n-1]
Leecode 152. 乘积最大子序列
题目描述
题目链接:https://leetcode.cn/problems/maximum-product-subarray/description/
给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。
测试用例的答案是一个32-位整数。
子数组是数组的连续子序列。
示例1:
- 输入:nums=[2,3,-2,4]
- 输出:6
- 解释:子数组[2,3]有最大乘积6
示例2:
- 输入:nums=[-2,0,-1]
- 输出:0
- 解释:结果不能为2,因为[-2,-1]不是子数组
解题思路
考虑使用动态规划方法求解,具体思路为:
- 遍历数组时计算当前最大值,不断更新
- 令
max_result[i]
为当前的最大值,则该动态规划的状态转移方程可以表示为:max_result[i]=max(nums[i],max_result[i-1]*nums[i])
- 由于存在负数,那么会导致最大值和最小值存在互换现象,因此需要同时维护最小值:
min_result[i]=min(nums[i],min_result[i-1]*nums[i])
- 当
nums[i]
为负数时,需要将max_result
和min_result
进行互换后,进行下一步计算。
复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(n)
解题代码
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if not nums:
return 0
n=len(nums)
max_result=[0]*n
min_result=[0]*n
max_result[0]=min_result[0]=result=nums[0]
for i in range(1,n):
if nums[i]<0:
max_result,min_result=min_result,max_result
max_result[i]=max(nums[i],max_result[i-1]*nums[i])
min_result[i]=min(nums[i],min_result[i-1]*nums[i])
result=max(result,max_result[i])
return result
Leecode 239. 滑动窗口最大值
题目描述
题目链接:https://leetcode.cn/problems/sliding-window-maximum/description/
给你一个整数数组nums
,有一个大小为k
的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的k
个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
示例1:
输入:nums=[1,3,-1,-3,5,3,6,7],k=3
输出:[3,3,5,5,6,7]
解题思路
可以使用双向队列来解决滑动窗口最大值的问题:
- 遍历数组,将数组下标存放在双向队列中,使用
R=i
,L=k-R
标记窗口的左边界和右边界 - 当滑动窗口移动时,弹出左边界对应的值
- 如果当前遍历的数比队尾的值大,则需要弹出队尾值,直到队列重新满足从大到小的排序规则
- 刚开始遍历时,L和R都为0,需要一个形成窗口的过程,此时没有最大值输出,L不动,R向右移动
- 当前窗口的最大值即为队首的数
复杂度分析
- 时间复杂度:O(nlogn),将一个元素放入优先队列的时间复杂度为O(logn)
- 空间复杂度:O(n),即为优先队列所需要使用的空间
解题代码
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
n=len(nums)
result=[]
#双端队列,存储当前窗口的元素索引
window=deque()
for i in range(n):
#当前元素超出窗口范围,移除队列左端元素
if window and window[0]<=i-k:
window.popleft()
#保持窗口队列中元素按照从大到小的顺序排列
while window and nums[i]>=nums[window[-1]]:
window.pop()
#将当前元素的索引添加到窗口队列的右端
window.append(i)
#当窗口长度达到k时,将窗口中最大值添加到结果数组中
if i>=k-1:
result.append(nums[window[0]])
return result
Leecode605. 种花问题
题目链接:https://leetcode.cn/problems/can-place-flowers/description/
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组flowerbed
表示花坛,由若干0
和1
组成,其中0
表示没种植花,1
表示种植了花。另有一个数n
,能否在不打破种植规则的情况下种入n
朵花?能则返回 true ,不能则返回 false 。
示例:
输入:flowerbed=[1,0,0,0,1],n=1
输出: true
解题思路
可以使用动态规划求解,定义dp[i]为长度为i的花坛的解,则规模缩小过程如下:
- 对于第i个位置,i可以种则i-1不可以种,问题规模缩小到i-2
- i不种的话,问题规模缩小到i-1
- 状态转移方程:
- i不种时:dp[i]=dp[i-1]
- i种时:dp[i]=dp[i-2]+1
复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(n)
解题代码:
class Solution:
def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
if n==0:
return True
flowerbed=[0]+flowerbed+[0]
dp=[0 for _ in range(len(flowerbed))]
for i in range(1,len(flowerbed)-1):
if flowerbed[i-1]==flowerbed[i]==flowerbed[i+1]==0:
dp[i]=dp[i-2]+1
else:
dp[i]=dp[i-1]
if dp[i]==n:
return True
return False
Comments NOTHING