2021-10-31
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
题解
因为今天学了基础的dp所以我就拿这个最经典的题来练练手，我们直接开始这个题解正题吧。
本题可以有很多种解法，贪心加二分，dp等，我是用的dp，我们可以先写一个递归，终止条件就是循环达到最后一个元素就返回，在递归里面判断是否有后面的数大于前面的数，有的话就直接加一，然后返回最大的那个长度。
本题还有数学归纳法，我直接把两种算法代码发在下面。
代码
1.dp
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: meno = {} def l(nums,i): if i in meno: return meno[i] if i == len(nums) -1 : return 1 max_1 = 1 for j in range(i+1,len(nums)): if nums[j]>nums[i]: max_1 = max(max_1,l(nums,j)+1) meno[i] = max_1 return max_1 return max( l(nums,i)for i in range(len(nums)))
2.数学归纳法
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: l = [1]*len(nums) for i in reversed(range(len(nums))): for j in range(i,len(nums)): if nums[j]>nums[i]: l[i] = max(l[i],l[j]+1) return max(l)
键盘行
给你一个字符串数组 words ，只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。
美式键盘 中：
第一行由字符 "qwertyuiop" 组成。
第二行由字符 "asdfghjkl" 组成。
第三行由字符 "zxcvbnm" 组成。
示例 1：
输入：words = ["Hello","Alaska","Dad","Peace"]
输出：["Alaska","Dad"]
示例 2：
输入：words = ["omk"]
输出：[]
示例 3：
输入：words = ["adsdf","sfd"]
输出：["adsdf","sfd"]
提示：
1 <= words.length <= 20
1 <= words[i].length <= 100
words[i] 由英文字母（小写和大写字母）组成
题解
本题就是用all放来来判断一个单词是否属于键盘三行里面的算法，我们可以，本题过于简单，大家可以直接看代码就懂了。
代码
class Solution: def findWords(self, words: List[str]) -> List[str]: res = [] s1 = "qwertyuiop" s2 = "asdfghjkl" s3 = "zxcvbnm" for i in words: if all(x.lower() in s1 for x in i) or all(x.lower() in s2 for x in i) or all(x.lower() in s3 for x in i): res.append(i) return res
递增子序列
给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。
示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
提示：
1 <= nums.length <= 15
-100 <= nums[i] <= 100
题解
本题使用dp加剪枝来解，我们可以定义一个dfs然后传参，传入nums和一个需要添加子序列的数组，添加条件是我们判断子序列大于等于2的时候。然后我们开始进行剪枝，首先创建一个集合，然后把每个子序列放在集合里面用来判断是否有重复的，如果有就跳过此次循环，没有就添加，然后在进行递归。直到递归结束。
代码
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = []
def dfs(nums,path):
if len(path) > 1:
res.append(path)
x = set()
for index ,i in enumerate(nums):
if i in x:
continue
if not path or i >= path[-1]:
x.add(i)
dfs(nums[index+1:],path+[i])
dfs(nums,[])
