516. 最长回文子序列给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。可以假设 s 的最大长度为 1000 。 示例 1:输入: "bbbab"输出: 4一个可能的最长回文子序列为 "bbbb"。 示例 2:输入: "cbbd"输出: 2一个可能的最长回文子序列为 "bb"。解题思路回文子序列和回文子串的区别是它不连续我们考虑动态规划dp[i][j]表示s[i:j]的最长回文子序列长度，则只有一个字符为1，其他情况为0;那么我们可以确定出递进方程 if(s.charAt(i)==s.charA...

5. 最长回文子串给你一个字符串 s，找到 s 中最长的回文子串。 示例 1： 输入：s = "babad"输出："bab"解释："aba" 同样是符合题意的答案。示例 2： 输入：s = "cbbd"输出："bb"示例 3： 输入：s = "a"输出："a"示例 4： 输入：s = "ac"输出："a"解题思路我们求解以每个元素为中心的回文子串，比较长度求最大值考虑到奇偶性，所以要求出以i为中心，和以i和i+1为中...

712. 两个字符串的最小ASCII删除和给定两个字符串s1, s2，找到使两个字符串相等所需删除字符的ASCII值的最小和。 示例 1: 输入: s1 = "sea", s2 = "eat"输出: 231解释: 在 "sea" 中删除 "s" 并将 "s" 的值(115)加入总和。在 "eat" 中删除 "t" 并将 116 加入总和。结束时，两个字符串相等，115 + 116 = 231 就是符合条件的最小和。示例 2: 输入: s1 = "...

583. 两个字符串的删除操作给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。 示例： 输入: "sea", "eat"输出: 2解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea" 提示： 给定单词的长度不超过500。给定单词中的字符只含有小写字母。解题思路该题的答案一定是每个字符串都删除除了公共最长子串之外的数字---多删也可以，不符合最少因此可以求出最长公共子串...

1143. 最长公共子序列给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。 若这两个字符串没有公共子序列，则返回 0。 示例 1: 输入：text1 = "abcde&qu...

53. 最大子序和给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。 示例 1： 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]输出：6解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2： 输入：nums = [1]输出：1示例 3： 输入：nums = [0]输出：0示例 4： 输入：nums = [-1]输出：-1示例 5： 输入：nums = [-100000]输出：-100000解题思路dp[i]：表示到i的最大子序和，如果到前一个元素的最大子序和大于0，则保留，否则舍弃//动态规划的优化：dp[...

354. 俄罗斯套娃信封问题给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。 请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。 说明:不允许旋转信封。 示例: 输入: envelopes = [[5,4],[6,4],[6,7],[2,3]]输出: 3解释: 最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。解题思路我们可以通过排序将其转化为求最长上升子序列的问题我们先按宽度递增，等...

300. 最长递增子序列给你一个整数数组 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[i]存储的是0-i的最...

72. 编辑距离给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作： 插入一个字符删除一个字符替换一个字符 示例 1： 输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose -> ros (删除 'e')示例 2： 输入：word1 = "intention", word2 = &quo...

494. 目标和给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例： 输入：nums: [1, 1, 1, 1, 1], S: 3输出：5解释： -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3 一共有5种方法让最终目标和为3。运行结果解题思路利用子集划分思想只有+和-。我们将数组分为A（+）和B（-）两个子集那...

322. 零钱兑换给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 你可以认为每种硬币的数量是无限的。 示例 1： 输入：coins = [1, 2, 5], amount = 11输出：3解释：11 = 5 + 5 + 1示例 2： 输入：coins = [2], amount = 3输出：-1示例 3： 输入：coins = [1], amount = 0输出：0示例 4： 输入：coins = [1], amount = 1输出：1示例 5： 输入：coins = [1],...

1. 两数之和给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 你可以按任意顺序返回答案。 示例 1： 输入：nums = [2,7,11,15], target = 9输出：[0,1]解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2： 输入：nums = [3,2,4], target = 6输出：[1,2]示例 3： 输入：nums = [3,3], target = 6输出：[0,1]解题思...

解题思路利用快慢指针：慢指针指向已排好的索引，快指针指向待排指针。 26. 删除排序数组中的重复项给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: 给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 ...

316. 去除重复字母1081. 不同字符的最小子序列给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。 注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同 示例 1： 输入：s = "bcabc"输出："abc"示例 2： 输入：s = "cbacdcbc"输出："acdb" 运行结果解题思路利用...