打开题目->思索半天->打开题解->思索一会->妙不可言->我是废物
+198.打家劫舍
示例
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n < 2:
return nums[0]
dp = [0 for i in range(n)]
dp[0],dp[1] = nums[0],nums[1]
for i in range(2,n):
dp[i] = max(dp[:i-1])+nums[i]
return max(dp[n-1],dp[n-2])
+213.打家劫舍②
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，能够偷窃到的最高金额。
示例
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
class Solution:
def rob(self, nums: List[int]) -> int:
if (nums==None or len(nums)==0): return 0
if (len(nums)<=3): return max(nums)
dp1=[0]*(len(nums)-1)
dp2=[0]*(len(nums)-1)
dp1[0]=nums[0]
dp1[1]=max(nums[0],nums[1])
dp2[0]=nums[1]
dp2[1]=max(nums[1],nums[2])
for i in range(2,len(nums)-1):
dp1[i]=max(dp1[i-2]+nums[i],dp1[i-1])
dp2[i]=max(dp2[i-2]+nums[i+1],dp2[i-1])
return max(dp1[-1],dp2[-1])
+416.分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
class Solution:
def canPartition(self, nums: List[int]) -> bool:
n = len(nums)
if n<2:
return False
target = sum(nums)//2
if sum(nums)%2 == 1:
return False
maxnum = max(nums)
if maxnum > target:
return False
dp = [[False]*(target+1) for i in range(n)]
for i in range(n):
dp[i][0] = True
dp[0][nums[0]] = True
for i in range(1,n):
for j in range(1,target+1):
if j >=nums[i]:
dp[i][j] = (dp[i-1][j] or dp[i-1][j-nums[i]])
else:
dp[i][j] = dp[i-1][j]
return dp[n-1][target]
+474.一和零
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的大小，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
示例
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
if len(strs) == 0:
return 0
dp = [[0] * (n+1) for _ in range(m+1)]
for strs_item in strs:
zeros = strs_item.count("0")
ones = strs_item.count("1")
for i in range(m, zeros - 1, -1):
for j in range(n, ones - 1, -1):
dp[i][j] = max(dp[i][j], 1+dp[i- zeros][j-ones])
return dp[m][n]
- 978.最长湍流子数组
当 A 的子数组 A[i], A[i+1], …, A[j] 满足下列条件时，我们称其为湍流子数组：
若 i <= k < j，当 k 为奇数时， A[k] > A[k+1]，且当 k 为偶数时，A[k] < A[k+1]；
或 若 i <= k < j，当 k 为偶数时，A[k] > A[k+1] ，且当 k 为奇数时， A[k] < A[k+1]。
也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
返回 A 的最大湍流子数组的长度。
示例
输入：[9,4,2,10,7,8,8,1,9]
输出：5
解释：(A[1] > A[2] < A[3] > A[4] < A[5])
class Solution:
def maxTurbulenceSize(self, arr: List[int]) -> int:
n = len(arr)
up = [1]*n
down = [1]*n
res = 1
for i in range(1,n):
if arr[i-1]<arr[i]:
down[i] = up[i-1]+1
elif arr[i-1]>arr[i]:
up[i] = down[i-1]+1
res = max(res,max(down[i],up[i]))
return res
+96.不同的二叉搜索数
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
示例
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
class Solution:
def numTrees(self, n: int) -> int:
# g(n) = f(1)+f(2)+...+f(n)
# f(i) = g(i-1)*g(n-i)
# f(5) = g(5-1)*g(5-5)
# = g(4)*g(0)
# =
# g(n) = g(n-1)*g(0) + g(n-2)*g(1)+...g(n-i)*g(i-1)
g = [0] * (n+1)
g[0],g[1] = 1,1
for i in range(2,n+1):
for j in range(1,i+1):
g[i] += g[i-j]*g[j-1]
return g[n]
