188. 买卖股票的最佳时机 IV

题目描述 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入: [2,4,1], k = 2 输出: 2 解释: 在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得利润 = 4-2 = 2 。 示例 2: 输入: [3,2,6,5,0,3], k = 2 输出: 7 解释: 在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润…

Read more

123. 买卖股票的最佳时机 III

题目描述 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 示例 1: 输入: [3,3,5,0,0,3,1,4] 输出: 6 解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。   随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格…

Read more

121. 买卖股票的最佳时机

题目描述 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。 示例 1: 输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 解法1 解法1使用动态规划方法,我们定义两个数组L和P。L[i]表示第0…i天最低的股价;P[i]表示第0…i天能获得的最大利益,那么答案 = max(P[i]), 1 <= i < |prices|。 那么我们就能够写出状态转移方程L[i] = min(L[i] –…

Read more

115. 不同的子序列

题目描述 给定一个字符串 S 和一个字符串 T,计算在 S 的子序列中 T 出现的个数。 一个字符串的一个子序列是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,”ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是) 示例 1: 输入: S = “rabbbit”, T = “rabbit” 输出: 3 解释: 如下图所示, 有 3 种可以从 S 中得到 “rabbit” 的方案。 (上箭头符号 ^ 表示选取的字母) rabbbit ^^^^ ^^ rabbbit ^^ ^^^^ rabbbit ^^^ ^^^ 示例 2: 输入: S = “babgbag”, T = “bag” 输出: 5 解释: 如下图所示, 有 5 种可以从 S 中得到 “bag” 的方案。 (上箭头符号 ^ 表示选取的字母) babgbag…

Read more

最长公共子串

在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。 https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2 解法1 – 动态规划 Wiki中提到要寻找最长公共子串,可以在两个字符串中所有的前缀组合中寻找最长的公共后缀。 例如:S1=”ABAB”, S2=”BABA”。那么S1与S2的所有前缀组合有(A, B) (A, BA) (A, BAB), (A, BABA), …, (ABAB, BABA)。我们可以使用一个矩阵来描述所有前缀的组合,表头代表两个字符串,表中的数值代表两个前缀的最长后缀。表头中的双引号代表空串,因为空串是任何字符串的前缀。 “” A B A B “” 0 0 0 0 0 B 0 0 1 0 1 A 0 1 0 2 0 B 0 0 2 0 3 A 0 1 0 3 0 我们很容易我们可以填好S1或S2只取一个字符后与另一个字符串的最长公共后缀,如果相同则填1,不同填0。那么如果S1或S2取两个字符与另一个字符串的最长公共后缀怎么求呢?我们可以看两个前缀最后一个字符,如果不相同那么该位置肯定是0,因为公共子串要求相同的字符连续。如果两个前缀最后一个字符相同,我们再对两个前缀各往回看一个字符,也就是该位置的斜上方。我们用斜上方的数值+1填入矩阵即可。 总结成公式也就是:…

Read more

5. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1: 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。 示例 2: 输入: “cbbd” 输出: “bb” https://leetcode-cn.com/problems/longest-palindromic-substring/ 解法1 暴力法很容易想到,我们使用双层循环固定字串的起止位置,然后对字串判断是否为回文串。双层循环的时间复杂度是O(n^2),再嵌套一个回文判断循环O(n),时间复杂度为O(n^3)。但是这里,我们不打算使用暴力法,因为很容易想到,码代码就好了。 我们在这里使用了一种方法,我称之为中心扩展法,那么我们先来定义中心。中心是由单个字符或连续多个相同的字符组成的子串。我们第一次扫描,找到字符串所有的中心。然后遍历每个中心的左右两边的字符,如果相同就继续扩展直到遇到边界或两边字符不同,这样我们就找到了一个回文串。题目要求最长回文串,我们就遍历每个中心,都做相同的扩展操作,选取找到的最长的回文串既是答案。需要特殊注意的是,中心本身也是回文串,也是潜在的答案。 代码中我们使用List<int[]>来存放找到的中心列表,int[0]与int[1]分别是中心的起止索引,都是闭区间。 解法2 方法分析 解法1是我自己想的,解法2、3都是源于LeetCode官方题解。解法2首先对字符串s逆序(reverse),记为s’。我们对字符串s与s’求最长公共子串。 例如,s=”acbcd”, s’=”dcbca”。求s与s’的最长公共子串为”cbc”,在这个例子中,这样的方法成功的求出了答案。我们再举一个例子,s=”abcdxydcba”, s’=”abcdyxdcba”。s与s’的最长公共子串是”abcd”,这显然不是回文子串。 问题出在哪呢?LeetCode题解说道“当s的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败”。我们来分析下,正是因为s中存在了非回文子串的反向副本,导致非回文子串出现在s’中。我们对s与s’求最长公共子串,也就把非回文子串取了出来。 举例分析:s=”[abcd]xy[dcba]”, s’=”[abcd]yx[dcba]”。s中第一个括号是[abcd],他的反向副本[dcba]同样在s中出现了。我们观察s中第二个中括号[dcba],在对s进行逆序操作后跑到了s’中第一个括号中。这样,我们对s与s’求最长公共子串就得到了错误的”abcd”。 那我们如何修正这样对情况,使得这个方法正确呢?我们只需要确保找到的最长公共子串的索引(indexOf)与最长公共子串的逆序的索引相同,就能保证找到的子串是反向的。(我认为这与判断找到的最长公共子串是否是回文串的条件是等价的,不对的话望指正) 作者疑问 还有一个问题,真的只需要寻找最长公共子串,并且确定最长公共子串的索引与其逆序的索引相同就够了吗? 例如 s=”abacdfgdcaba”, s’=”abacdgfdcaba”。s与s’的最长公共子串为abacd,但其在s中的索引与其反向索引不同,一个是0,一个是7,所以该子串不是最长回文子串。可是,方法二所说的求s与s’的最长公共子串可只有一个啊,接下来没法玩了啊!!!。 那该方法说的是不是不准确啊,应该找出s与s’所有的公共子串,然后所有公共子串的索引与其逆序的索引是否相同。这么做不就和暴力法差不多了吗?暴力法是找到s所有的子串判断是否为回文串。这个方法是找到s与s’所有的公共子串,判断索引与其逆序的索引是否相同。 代码 好吧,带着疑问写代码。我的做法是求出s与s’所有的公共子串,然后求其索引与反向索引是否相同。运行了几个case答案是正确的,但是粘贴到LeetCode提示超时。这个方法不太可取,创建了大量的临时变量,还包含递归函数。 解法3 解法三使用动态规划,这个方法源自LeetCode官方题解。 状态转移方程:P(i, j) = S[i] == S[j] and P(i + 1, j – 1)…

Read more