来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/russian-doll-envelopes
494.目标和
给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/target-sum
class Solution(object):
def findTargetSumWays(self, nums, S):
"""
:type nums: List[int]
:type S: int
:rtype: int
"""
length = len(nums)
dp = [[0 for _ in range(2001)] for _ in range(length)]
dp[0][nums[0] + 1000] = 1
dp[0][-nums[0] + 1000] += 1
# 其中i表示前i个数,j表示i个数的和
# j-/+nums[i]表示当前数,是从哪个两个数计算过来的
# for j in range(-1000, 1001) 根据题目描述,数组中的所有数字合小于1000(因为可能出现-的情况,所以-1000包含进来)
for i in range(1, length):
for j in range(-1000, 1001):
dp[i][j] = dp[i-1][j-nums[i]] + dp[i-1][j+nums[i]]
return 0 if S > 1000 else dp[length - 1][S + 1000]
if __name__ == '__main__':
s1 = Solution()
nums = [1, 1, 1, 1, 1]; S = 3
nums =[0, 0, 0, 0, 0, 0, 0, 0, 1]; S= 1
root = s1.findTargetSumWays(nums, S)
print(root)
300. 最长递增子序列
# 300. 最长递增子序列
class Solution(object):
def lengthOfLIS_(self, nums: list):
"""
https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
:type nums: List[int]
:rtype: int
此问题使用动态规划实现,
dp[i] 存放的是num[:i](包含nums[i]并且当且最长子序中nums[i]必须是最后一个元素) 范围中上升子序的值
在此之前一定有一个索引j使得j < i,使得当nums[j] < nums[i],i的上升子序等于max(nums[j] + 1, dp[i])
(其中nums[j]可能是for j in range(i)中任何一个,所以需要求出他的最大值;同时dp[i]=1初始值赋值为1,因为最少也有1个)
"""
length = len(nums)
if length < 2:
return nums
dp = [0 for _ in range(length)]
dp[0] = 1
for i in range(1, length):
dp[i] = 1
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[j] + 1, dp[i])
return max(dp)
def lengthOfLIS1(self, nums: list):
"""
:type nums: List[int]
:rtype: int
暴力求解:将nums的所有子集暴力求解出来,其中严格上升子集中长度最大的, 看不懂可以全看先看78题
"""
length = len(nums)
if length < 2:
return nums
max_ret = 1
for i in range(1 << length):
temp_list = []
for j in range(length):
if i & (1 << j):
temp_list.append(nums[j])
flag = False
# 这一部分是判断子集是否是严格上升
for k in range(1, len(temp_list)):
if temp_list[k] <= temp_list[k - 1]:
flag = True
break
if not flag:
max_ret = max(max_ret, len(temp_list))
return max_ret
def lengthOfLIS(self, nums: list):
length = len(nums)
if length < 2:
return length
tail = [nums[0]]
for i in range(1, length):
if nums[i] > tail[-1]:
tail.append(nums[i])
continue
left = 0
right = len(tail) - 1
while left < right:
mid = (left + right) >> 1
if nums[i] < tail[mid]:
right = mid - 1
else:
left = mid + 1
tail[left] = nums[i]
return len(tail)
if __name__ == '__main__':
nums = [10, 9, 2, 5, 3, 7, 101, 18]
# nums = [7, 7, 7, 7, 7, 7, 7]
nums = [2, 3, 4, 3413, 412, 4234, 1233, 4123, 4, 124, 33, 245, 65, 46, 654, 86, 8]
# nums = [0, 1, 0, 3, 2, 3]
obj = Solution()
root = obj.lengthOfLIS(nums)
# print(root)
print(dir())
354. 俄罗斯套娃信封问题
# 354. 俄罗斯套娃信封问题
import bisect
class Solution(object):
def maxEnvelopes1(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
length = len(envelopes)
if length < 2:
return length
dp = [1 for _ in range(length)]
envelopes = sorted(envelopes, key=lambda x: x[0], reverse=True)
for i in range(1, length):
for j in range(i):
if envelopes[j][0] > envelopes[i][0] and envelopes[j][1] > envelopes[i][1]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def maxEnvelopes2(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
# 这里对(x[0], -x[1])第二元素倒序很关键,可以保证x[0]有了顺序,也就是你只需要关心x[1]的大小就好了
# 同时倒序保证如果x[0]相同,大的先入dp中,后面小的只能替换它的而不是append追加
# (注意:由于x[0]是递增的,所以只需要考虑x[1]的大小;
当x[1]>dp[-1][1]的时候,由于x[0]递增,因此x[0]>dp[-1][0],说明这个时候新加入的x大于当前递增序列的最后一个值
(也就是其中的最大值,所以直接append);
当x[1]<=dp[-1][1]的时候,虽然x[0]是递增的,但是x[1]却不是,这个时候x不能直接append,但是dp[i]中存放的是前i+1
个元素中,dp长度个递增元素的结尾最小的值,我们可以使用x[-1]替换它,以保证获取更长长度的dp(因为只有当dp[i]最小
后面比它大的才会更多)
)
"""
length = len(envelopes)
if length < 2:
return length
envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))
dp = [envelopes[0][1]]
for i in range(1, length):
if envelopes[i][1] > dp[-1]:
dp.append(envelopes[i][1])
else:
left = 0
right = len(dp) - 1
while left < right:
mid = (left + right) >> 1
if envelopes[i][1] > dp[mid]:
left = mid + 1
else:
right = mid
# left = bisect.bisect_left(dp, envelopes[i][1])
dp[left] = envelopes[i][1]
return len(dp)
def maxEnvelopes(self, envelopes):
"""
:type envelopes: List[List[int]]
:rtype: int
"""
length = len(envelopes)
if length < 2:
return length
dp = [1 for _ in range(length)]
envelopes = sorted(envelopes, key=lambda x: (x[0], -x[1]))
for i in range(1, length):
for j in range(i):
if envelopes[j][1] < envelopes[i][1]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
if __name__ == '__main__':
envelopes = [[5, 4], [6, 4], [6, 7], [2, 3]]
# envelopes = [[30, 50], [12, 2], [3, 4], [12, 15]]
# envelopes = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [5, 5], [6, 7], [7, 8]]
# envelopes = [[2, 100], [3, 200], [4, 300], [5, 500], [5, 400], [5, 250], [6, 370], [6, 360], [7, 380]]
# envelopes = [[15, 8], [2, 20], [2, 14], [4, 17], [8, 19], [8, 9], [5, 7], [11, 19], [8, 11], [13, 11], [2, 13],
# [11, 19], [8, 11], [13, 11], [2, 13], [11, 19], [16, 1], [18, 13], [14, 17], [18, 19]]
# envelopes = [[1, 3], [1, 2], [1, 1], [3, 5]]
obj = Solution()
root = obj.maxEnvelopes(envelopes)
print(root)