337. 打家劫舍 III

题目描述 在上次打劫完一条街道之后和一圈房屋后,小偷又发现了一个新的可行窃的地区。这个地区只有一个入口,我们称之为“根”。 除了“根”之外,每栋房子有且只有一个“父“房子与之相连。一番侦察之后,聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫,房屋将自动报警。 计算在不触动警报的情况下,小偷一晚能够盗取的最高金额。 示例 1: 输入: [3,2,3,null,3,null,1] 3 / \ 2 3 \ \ 3 1 输出: 7 解释: 小偷一晚能够盗取的最高金额 = 3 + 3 + 1 = 7. 示例 2: 输入: [3,4,5,1,3,null,1]   3 / \ 4 5 / \ \ 1 3 1 输出: 9 解释: 小偷一晚能够盗取的最高金额 = 4 + 5 = 9. 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/house-robber-iii著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1…

Read more

376. 摆动序列

题目描述 如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。 例如, [1,7,4,9,2,5] 是一个摆动序列,因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。 给定一个整数序列,返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。 示例 1: 输入: [1,7,4,9,2,5] 输出: 6 解释: 整个序列均为摆动序列。 示例 2: 输入: [1,17,5,10,13,15,10,5,16,8] 输出: 7 解释: 这个序列包含几个长度为 7 摆动序列,其中一个可为[1,17,10,13,10,16,8]。 示例 3: 输入: [1,2,3,4,5,6,7,8,9] 输出: 2 进阶:你能否用 O(n) 时间复杂度完成此题? https://leetcode-cn.com/problems/wiggle-subsequence/ 解法1 – 动态规划 O(n^2) 我们定义dp数组为dp[|nums|][2],dp[i][0]表示第i个元素作为较小元素构成的摆动序列最大长度;dp[i][1]表示第i个元素作为较大元素构成的摆动序列最大长度,且必须使用nums[i]。那么我们有dp[i][0] = dp[j][1]+1如果存在nums[j] > nums[i],否则dp[i][0]=1;dp[i][1] = dp[j][0]+1如果存在nums[j] < nums[i],否则dp[i][1]=1(0<=j<i)。 需要注意,当我们填充dp[i][0/1]时,我们向前寻找dp[j][1/0],不能找到第一个大于/小于nums[i]的元素后就停止,而是应该搜索到j = 0。因为有这样的case: 例如图1中的case,当i=4时nums[4]=0,当我们更新dp[4][0]时,我们不能只向前搜寻第一个大于nums[4]的位置。因为前面可能有更长的摆动序列,能够和0链接上,形成更长的摆动序列。在这个例子中,{53,1,3,1}与{1}都能和[0]形成摆动序列,但是我们要选最长的。 该方法的时间复杂度为O(n^2),空间复杂度为O(n)。全部代码如下: 解法2 – 动态规划 O(n) 我们还是使用动态规划,但是我们更改了dp数组的定义。我们定义数组dp[|nums|][2],dp[i][0]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较小的;dp[i][1]表示nums前i个数构成的摆动序列最大长度且序列最后一个数是较大的。那么有dp[i][0]…

Read more

53. 最大子序和

题目描述 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例: 输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。 进阶: 如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。 https://leetcode-cn.com/problems/maximum-subarray/ 解法1 – 使用DP,O(n) 我们定义一维数组|dp| = |nums|,dp[i]表示必须使用nums[i]元素,得到的连续子数组的最大和。那么有dp[i] = max(nums[i], dp[i – 1] + nums[i])。 解释一下,如果前面累积的最大和是负数,那么使用累积的和与nums[i]相加会使得和更小,我们还不如直接使用nums[i]作为新的连续子数组。 时间复杂度O(n),空间复杂度O(n)。全部代码如下: 我们观察到dp[i]只依赖于dp[i-1],因此我们可以使空间复杂度压缩到O(1)。 解法2 – 分治法,O(nlogn) 我们定义函数maxSubArray(nums, l, r),表示区间[l, r]内找到的连续子数组的最大和。那么在区间[l, r]内的连续子数组最大和有3种来源: 来源于[l, m) (m = (l + r) / 2),记为max1; 来源与(m, r],记为max2; 来源于跨中间元素m的区间,记为max3 那么[l, r]区间的连续子数组最大和有max(max1, max2, max3)。其中,第3种情况比较复杂。我们需要从m的左右两侧出发,通过扫描来求和,如图1所示。 我们递归求解区间[l,…

Read more

309. 最佳买卖股票时机含冷冻期

题目描述 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。​ 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。 示例: 输入: [1,2,3,0,2] 输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 解法1 解法1使用到了有限状态机(FSM),在第i天我们的状态有3种,分别是hold(持股)、sold(抛售)和rest(休息)。第i天的hold状态可由第i-1天的hold状态(继续持有)和第i-1天的rest状态(买入股票)而来。第i天的rest状态可由第i-1天的rest状态(继续休息)和第i-1天的sold状态(冷冻期)而来。第i天的sold状态只能从第i-1天的hold状态而来(抛售股票)。我们在图1描述了这些状态。 对于第1天,sold状态是不合法的,因为我们还没有买进;对于hold和rest状态是合法的。题目要求计算最大利润,那么最后一天的最大利润只可能来自sold或者rest状态,而绝不可能来自于hold状态(因为我们手中持有股票)。 我们定义了3个长度为|prices|的数组来实现有限状态机,分别是hold、sold和rest。对于第1天,我们初始化hold[0] = -prices[0], sold[0] = -∞ (第1天抛售状态为不合法), rest[0]。hold[i], sold[i]与rest[i]的物理意义分别是如果选择第i持股、抛售与休息能获得的最大利益。那么我们有: hold[i] = max(hold[i-1], rest[i-1] – prices[i]) rest[i] = max(rest[i – 1], sold[i-1]) sold[i] = hold[i-1] + prices[i] 下面,我们举两个例子来解释算法执行过程。 图2中列举了算法执行过程,我们分别解释i=1(第二天)与i=4(第5天)的计算过程。 例1: (i…

Read more

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