LeeCode算法总结——数组/字符串

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.先给所有学生一颗糖；
1. 对于学生i来说，如果相邻右侧i+1学生的分数更高，则将其糖果数量更改为left_list[i]+1；
2. 如果学生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