力扣刷题day40：10-10

1.第 k 个缺失的正整数

给你一个 严格升序排列 的正整数数组 arr 和一个整数 k 。

请你找到这个数组里第 k 个缺失的正整数。

方法一：二分法  #方法一：二分法 def findKthPositive(arr,k): arr.insert(0,0) #边界问题 补充0 0 left,right=0,len(arr) -1 while left<=right: mid=(left+right)//2 loss=arr[mid]-mid #当前位置缺失的个数 if loss<k: left=mid+1 elif loss>=k: right=mid-1 return k+right 2.单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

方法一：动态规划  #方法一：动态规划 def wordBreak(s,wordDict): dp=[False for i in range(len(s)+1)] #dp[i] 表示长度为i的字符串能否由字典拼出 dp[0]=True #空字符串肯定满足 for i in range(len(s)): for j in range(i+1,len(s)+1): if dp[i] and s[i:j] in wordDict: dp[j]=True #判断i-j之间的字符串是否在字典中 return dp[-1]