Leetcode【368、986】
Leetcode【368、986】
echobingo
发布于 2019-07-25 18:43:43
发布于 2019-07-25 18:43:43
问题描述：【DP】368. Largest Divisible Subset
解题思路：
最大可除子集。给一个包含不同数字的数组，找一个最大的子集，对于子集中的每个元素对 (Si, Sj) 满足 Si % Sj = 0 或者 Sj % Si = 0，返回这个子集。
最长上升子序列问题。
Python3 实现：
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
if not nums:
return []
N = len(nums)
nums.sort()
dp = [1] * N
pre = [-1] * N
for i in range(1, len(nums)):
for j in range(i-1, -1, -1):
if nums[i] % nums[j] == 0:
if dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
pre[i] = j
ind = dp.index(max(dp))
ans = []
while ind != -1:
ans.append(nums[ind])
ind = pre[ind]
return ans问题描述：【Two Pointers】986. Interval List Intersections
解题思路：
区间列表的交集。给定两个由一些闭区间组成的列表，每个区间列表都是成对不相交的，并且已经排序。返回这两个区间列表的交集。
Python3 实现：
class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
ans = []
i = j = 0
while i < len(A) and j < len(B):
if A[i][0] >= B[j][0] and A[i][1] <= B[j][1]:
ans.append([A[i][0], A[i][1]])
elif A[i][0] <= B[j][0] and A[i][1] >= B[j][1]:
ans.append([B[j][0], B[j][1]])
elif A[i][0] <= B[j][0] and A[i][1] >= B[j][0]:
ans.append([B[j][0], A[i][1]])
elif A[i][0] >= B[j][0] and A[i][0] <= B[j][1]:
ans.append([A[i][0], B[j][1]])
if A[i][1] <= B[j][1]:
i += 1
elif A[i][1] >= B[j][1]:
j += 1
return ans改进版代码：
class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
ans = []
i = j = 0
while i < len(A) and j < len(B):
left = max(A[i][0], B[j][0])
right = min(A[i][1], B[j][1])
if left <= right:
ans.append([left, right])
if A[i][1] <= B[j][1]:
i += 1
else:
j += 1
return ans本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.07.23 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录