本文主要是介绍算法打卡day45,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
今日任务:
1)300.最长递增子序列
2)674.最长连续递增序列
3)718.最长重复子数组
4)复习day20
300.最长递增子序列
题目链接:300. 最长递增子序列 - 力扣(LeetCode)
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出:4 解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。示例 2: 输入:nums = [0,1,0,3,2,3] 输出:4示例 3: 输入:nums = [7,7,7,7,7,7,7] 输出:1提示: 1 <= nums.length <= 2500 -10^4 <= nums[i] <= 104
文章讲解:代码随想录 (programmercarl.com)
视频讲解:动态规划之子序列问题,元素不连续!| LeetCode:300.最长递增子序列哔哩哔哩bilibili
思路:
这个问题可以使用动态规划来解决。我们可以定义一个状态数组
dp
,其中dp[i]
表示以第 i 个元素结尾的最长递增子序列的长度。具体的动态规划转移方程如下:
- 对于
dp[i]
,我们需要考虑第 i 个元素与前面的元素的关系:
- 如果 nums[i] 大于 nums[j](0 ≤ j < i),则第 i 个元素可以接在第 j 个元素后面形成一个更长的递增子序列,此时
dp[i] = max(dp[i], dp[j] + 1)
。- 否则,第 i 个元素无法接在任何元素后面形成递增子序列,此时
dp[i] = 1
(表示只有第 i 个元素自己构成一个递增子序列)。最终的答案就是
dp
数组中的最大值。
class Solution:def lengthOfLIS(self, nums: List[int]) -> int:n = len(nums)if n == 0:return 0# 初始化状态数组dp = [1]*n# 动态规划转移for i in range(1,n):for j in range(i):if nums[j] < nums[i]:dp[i] = max(dp[i],dp[j]+1)# 返回dp数组中的最大值return max(dp)
674.最长连续递增序列
题目链接:674. 最长连续递增序列 - 力扣(LeetCode)
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。示例 1: 输入nums = [1,3,5,4,7] 输出:3 解释:最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。示例 2: 输入:nums = [2,2,2,2,2] 输出:1 解释:最长连续递增序列是 [2], 长度为1。提示: 0 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9
文章讲解:代码随想录 (programmercarl.com)
视频讲解:动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列哔哩哔哩bilibili
思路:
这一题我们可以用动态规划,也可以用贪心 算法来解决这个问题。
动态规划:
我们可以定义一个状态数组
dp
,其中dp[i]
表示以第i
个元素结尾的最长连续递增子序列的长度。初始时,所有元素的最长连续递增子序列长度都为1。然后,我们可以从第二个元素开始遍历数组,对于每个位置
i
,我们判断nums[i]
是否大于nums[i-1]
:
- 如果是,则
dp[i] = dp[i-1] + 1
,表示以当前元素结尾的最长连续递增子序列的长度比前一个元素多1;- 如果不是,则
dp[i] = 1
,表示以当前元素结尾的最长连续递增子序列的长度重新开始计算。最终,我们返回状态数组
dp
中的最大值即为所求的最长连续递增子序列的长度。
class Solution:# 动态规划def findLengthOfLCIS(self, nums: List[int]) -> int:n = len(nums)if n <= 1:return n# 初始化状态数组dp = [1] * n# 动态规划转移for i in range(1, n):if nums[i] > nums[i-1]:dp[i] = dp[i-1] + 1# 返回dp数组中的最大值return max(dp)
贪心算法:
我们可以遍历数组,用一个变量记录当前连续递增子序列的长度,同时维护一个变量记录最长连续递增子序列的长度。
具体步骤如下:
- 初始化当前连续递增子序列的长度
cur_len
和最长连续递增子序列的长度max_len
,均设为1(因为至少有一个元素构成子序列)。- 从数组的第二个元素开始遍历,判断当前元素是否比前一个元素大:
- 如果是,则当前连续递增子序列的长度加1,并更新最长连续递增子序列的长度;
- 如果不是,则当前连续递增子序列的长度重新设为1。
- 最终返回
max_len
即为最长连续递增子序列的长度。
class Solution:# 贪心算法def findLengthOfLCIS2(self, nums: List[int]) -> int:n = len(nums)if n <= 1:return ncur_len = 1 # 当前连续递增子序列的长度max_len = 1 # 最长连续递增子序列的长度for i in range(1, n):if nums[i] > nums[i - 1]: # 当前元素比前一个元素大cur_len += 1max_len = max(max_len, cur_len)else:cur_len = 1return max_len
感想:
针对给定一个未经排序的整数数组,找到最长且连续递增的子序列,两种方法都可以解决,但在这种情况下,贪心算法更为简单且高效。
贪心算法的优势:
- 在这个问题中,连续递增子序列的最大长度实际上就是最长连续递增子序列的长度。因此,我们只需要从头到尾遍历数组一次,记录当前递增序列的起始位置和长度即可。
- 贪心算法的时间复杂度是 O(n),空间复杂度是 O(1),非常高效。
动态规划的不足:
- 对于这个问题,使用动态规划可能会过于复杂。动态规划通常用于更复杂的问题,其中状态之间存在更复杂的依赖关系,而在这个问题中,并不需要记录每个位置的状态,只需要记录当前递增序列的起始位置和长度即可。
718.最长重复子数组
题目链接:718. 最长重复子数组 - 力扣(LeetCode)
给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。示例: 输入: A: [1,2,3,2,1] B: [3,2,1,4,7] 输出:3 解释:长度最长的公共子数组是 [3, 2, 1] 。提示: 注意题目中说的子数组,其实就是连续子序列 1 <= len(A), len(B) <= 1000 0 <= A[i], B[i] < 100
文章讲解:代码随想录 (programmercarl.com)
视频讲解:动态规划之子序列问题,想清楚DP数组的定义 | LeetCode:718.最长重复子数组哔哩哔哩bilibili
思路:
这个问题可以用动态规划来解决。我们可以使用一个二维数组
dp
,其中dp[i][j]
表示以A[i-1]
和B[j-1]
结尾的公共子数组的长度。如果A[i-1]
和B[j-1]
相等,那么dp[i][j] = dp[i-1][j-1] + 1
,否则dp[i][j] = 0
。
class Solution:def findLength(self, nums1: List[int], nums2: List[int]) -> int:# 获取数组 nums1 和 nums2 的长度m, n = len(nums1), len(nums2)# 初始化动态规划数组 dpdp = [[0] * (n + 1) for _ in range(m + 1)]# 初始化最大公共子数组长度为 0max_len = 0# 遍历数组 nums1 和 nums2for i in range(1, m + 1):for j in range(1, n + 1):# 如果 nums1[i-1] 和 nums2[j-1] 相等,则更新 dp[i][j] 为前一个状态加 1if nums1[i - 1] == nums2[j - 1]:dp[i][j] = dp[i - 1][j - 1] + 1# 更新最大公共子数组长度max_len = max(max_len, dp[i][j])# 返回最大公共子数组长度return max_len
这篇关于算法打卡day45的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!