2021-11-1
题目
判断子序列
排列硬币
分糖果
递增的三元子序列
题解
1.判断子序列
本题最简单的就是用双指针来写，我开始看子序列然后我就想用dp回溯，但是我发现，虽然dp能写出来但是让这个问题变的超级复杂，最后我看了题解一眼，发现不是dp，用双指针，我当场裂开！！！接下来我们看双指针的办法。‘
首先我们分别用i ， j指向两个不同的字符串的首字符，然后开始向右移动，当 s1 [i] == s2 [j]时i加一，而 j 是每次循环的时候都会加一，当i的长度等于s1的长度就返回true，否者返回false。
2.排列硬币
本题其实不是一个很难的问题，就是一个简单的阶梯问题，我们弄一个每次递增为1的变量，然后让n减去这个数，最后当n小于这个变量就退出循环，最后来判断一共有多少个满行。
3.分糖果
本题直接使用长度除2来判断。
4.递增的三元子序列
本题还没理解一种方便的算法，我用的dp没有解出来！！！！！
代码
1.判断子序列
class Solution: def isSubsequence(self, s: str, t: str) -> bool: if len(s) == 0: return True i = 0 j = 0 while i < len(s) and j <len(t): if s[i] == t[j]: i += 1 j += 1 if i ==len(s): return True return False
2.排列硬币
class Solution: def arrangeCoins(self, n: int) -> int: res =1 while res<=n: n-=res if n == 0: return res res +=1 return res-1
3.分糖果
class Solution: def distributeCandies(self, candyType: List[int]) -> int: res = [] for i in candyType : if len(res)!=len(candyType)/2 and i not in res: res.append(i) return len(res)
4.递增的三元子序列
class Solution: def increasingTriplet(self, nums: List[int]) -> bool: small, mid = max(nums), max(nums) for num in nums: if num <= small: small = num elif num <= mid: mid = num else: return True return False
