子序列 子数组问题
53. 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
解法1: 贪心法
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
cur_sum = 0
for i in range(0, len(nums)):
cur_sum += nums[i]
max_sum = max(max_sum, cur_sum)
if cur_sum < 0:
cur_sum = 0
return max_sum
解法2： 动态规划
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
if nums[i-1] > 0:
nums[i] = nums[i] + nums[i-1]
return max(nums)
674. 最长连续递增序列
给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。
连续递增的子序列 可以由两个下标 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 隔开。
解法1:
class Solution:
def findLengthOfLCIS(self, nums: List[int]) -> int:
if not nums:
return 0
max_length = 1
temp = 1
for i in range(1, len(nums)):
if nums[i] > nums[i-1]:
temp += 1
max_length = max(max_length, temp)
else:
temp = 1
return max_length
300. 最长递增子序列 ** 重点复习
给你一个整数数组 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 。
解法1： 动态规划
O
(
n
2
)
O(n^2)
O(n2)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
nums_len = len(nums)
dp = []
for i in range(nums_len):
dp.append(1)
for j in range(len(dp)):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
解法2：
O
(
n
l
o
g
(
n
)
)
O(nlog(n))
O(nlog(n))
673. 最长递增子序列的个数 ** 重点复习
给定一个未排序的整数数组，找到最长递增子序列的个数。
示例 1:
输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
解法1: 动态规划
O
(
n
2
)
O(n^2)
O(n2)
class Solution:
def findNumberOfLIS(self, nums: List[int]) -> int:
nums_len = len(nums)
length = []
counts = []
for i in range(nums_len):
length.append(1)
counts.append(1)
for j in range(i):
if nums[j] < nums[i]:
if length[i] <= length[j]:
length[i] = length[j]+1
counts[i] = counts[j]
elif length[i] == length[j]+1:
counts[i] += counts[j]
max_length = max(length)
max_count = 0
for i in range(len(length)):
if length[i] == max_length:
max_count += counts[i]
return max_count
1143. 最长公共子序列 ** 动态规划典型题目
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。
解法1: 动态规划重点题
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
text1_len = len(text1)
text2_len = len(text2)
dp = [[0] * (text2_len+1) for _ in range(text1_len+1)]
for i in range(1, text1_len+1):
for j in range(1, text2_len+1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[text1_len][text2_len]
718. 最长重复子数组 ** 动态规划
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例：
输入：
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出：3
解释：
长度最长的公共子数组是 [3, 2, 1] 。
解法1: 动态规划
class Solution:
def findLength(self, A: List[int], B: List[int]) -> int:
A_len = len(A)
B_len = len(B)
dp = [[0]*(B_len+1) for _ in range(A_len+1)]
max_res = 0
for i in range(1, A_len+1):
for j in range(1, B_len+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = 0
max_res = max(max_res, dp[i][j])
return max_res
724. 寻找数组的中心索引
给你一个整数数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
数组 中心索引 是数组的一个索引，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，返回 -1 。如果数组有多个中心索引，应该返回最靠近左边的那一个。
注意： 中心索引可能出现在数组的两端。
解法1: 前缀和
class Solution:
def pivotIndex(self, nums: List[int]) -> int:
total = sum(nums)
acc_sum = 0
for i in range(len(nums)):
if acc_sum == total - acc_sum - nums[i]:
return i
acc_sum += nums[i]
return -1
560. 和为K的子数组 *
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1:
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
- 数组的长度为 [1, 20,000]。
- 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = 0
hashtable = {0:1}
preSum = 0
for item in nums:
preSum += item
if hashtable.get(preSum-k):
count += hashtable.get(preSum-k)
if preSum not in hashtable:
hashtable[preSum] = 1
else:
hashtable[preSum] = hashtable[preSum] + 1
return count
523. 连续的子数组和 * 重点复习
给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1：
输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：
输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
说明：
- 数组的长度不会超过 10,000 。
- 你可以认为所有数字总和在 32 位有符号整数范围内。
解法1: 前缀和的 思想
详解
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
hashtable = {0:-1}
preSum = 0
for index, item in enumerate(nums):
preSum += item
if k != 0:
preSum = preSum % k
if hashtable.get(preSum) != None:
if index - hashtable.get(preSum)> 1:
return True
else:
hashtable[preSum] = index
return False
974. 和可被 K 整除的子数组
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
示例：
输入：A = [4,5,0,-2,-3,1], K = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
提示：
- 1 <= A.length <= 30000
- -10000 <= A[i] <= 10000
- 2 <= K <= 10000
解法1: 前缀和
思路：
那么每个连续子数组的和
s
u
m
(
i
,
j
)
sum(i,j)
sum(i,j)就可以写成$ P[j] - P[i-1]$, 此时，判断子数组的和能否被
K
K
K 整除就等价于判断
(
P
[
j
]
−
P
[
i
−
1
]
)
m
o
d
K
=
=
0
(P[j] - P[i-1]) \bmod K == 0
(P[j]−P[i−1])modK==0，根据 同余定理，只要
P
[
j
]
m
o
d
K
=
=
P
[
i
−
1
]
m
o
d
K
P[j] \bmod K == P[i-1] \bmod K
P[j]modK==P[i−1]modK，就可以保证上面的等式成立。
class Solution:
def subarraysDivByK(self, A: List[int], K: int) -> int:
dicts = {0:1}
preSum = 0
count = 0
for item in A:
preSum += item
if K != 0:
preSum = preSum % K
if dicts.get(preSum) != None:
count += dicts[preSum]
dicts[preSum] += 1
else:
dicts[preSum] = 1
return count
1248. 统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
方法1:
class Solution:
def numberOfSubarrays(self, nums: List[int], k: int) -> int:
odd_list = {0:1}
odd_s = 0
count = 0
for item in nums:
if item % 2 != 0:
odd_s += 1
if odd_list.get(odd_s - k):
count += odd_list.get(odd_s - k)
if odd_s not in odd_list:
odd_list[odd_s] = 1
else:
odd_list[odd_s] += 1
return count
713. 乘积小于K的子数组 ** 多复习
给定一个正整数数组 nums。
找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8个乘积小于100的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
解法1: 双指针
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
acc = 1
left = 0
count = 0
for right, value in enumerate(nums):
acc *= value
while acc >= k:
acc /= nums[left]
left += 1
count += right - left + 1
return count
325. 和等于 k 的最长子数组长度
给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
注意:
nums 数组的总和是一定在 32 位有符号整数范围之内的。
示例 1:
输入: nums = [1, -1, 5, -2, 3], k = 3
输出: 4
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。
解法1: 前缀和
class Solution:
def maxSubArrayLen(self, nums: List[int], k: int) -> int:
prelist = {0:-1}
presum = 0
max_len = 0
for index, item in enumerate(nums):
presum += item
if prelist.get(presum-k) != None:
max_len = max(max_len, index-prelist.get(presum-k))
if presum not in prelist:
prelist[presum] = index
return max_len
152. 乘积最大子数组 *
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
解法1: 动态规划
class Solution:
def maxProduct(self, nums: List[int]) -> int:
if len(nums) <= 0:
return 0
minValue = nums[0]
maxValue = nums[0]
ans = nums[0]
for i in range(1, len(nums)):
temp = minValue
minValue = min(minValue*nums[i], nums[i], maxValue*nums[i])
maxValue = max(temp*nums[i], nums[i], maxValue*nums[i])
ans = max(ans, maxValue)
return ans
238. 除自身以外数组的乘积 *
给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示： 题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
解法1: 左部分*右部分， 注意边界条件
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
left = 1
nums_len = len(nums)
res = [0]*nums_len
for i in range(nums_len):
if i > 0:
left = left*nums[i-1]
res[i] = left
right = 1
for i in range(nums_len-1, -1, -1):
if i < nums_len-1:
right = right*nums[i+1]
res[i] = res[i]*right
return res
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
