300. 最长上升子序列

题目描述 给定一个无序的整数数组,找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18]输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。说明: 可能会有多种最长上升子序列的组合,你只需要输出对应的长度即可。你算法的时间复杂度应该为 O(n2) 。进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗? 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – O(n^2) 这是一道经典的dp题目,大体上有两种解法,第一种是dp(时间复杂度O(n^2));第二种是dp+二分搜索(时间复杂度O(nlogn)),我们先介绍O(n^2)的解法。而第一种dp还可以分为Bottom-up和Top-down两种实现方式。 Bottom-up 我们定义数组dp[|nums|],dp[i]表示使用nums数组前i个元素且必须使用nums[i],能够构成的最长递增子序列的长度。那么有dp[i] = max(dp[j]) + 1, 其中nums[i] > nums[j], j < i,如果找不到这样的j,那么dp[i] = 1。 如果形象的描述算法的执行过程那就是使用双重循环,外循环使用变量i指向nums数组的每个元素,然后内循环用变量j扫描0~i。当nums[i] > nums[j]时,更新prev = max(prev, dp[j])。当内层循环扫描完毕,更新dp[i] = perv + 1。当双重循环执行完毕,dp数组中的最大值就是nums的最长递增子序列。 Top-down 自顶向下的思路使用递归来实现,我们定义一个辅助函数LIS(nums, curr),表示从nums数组的前curr个元素(包含curr)寻找LIS,并返回LIS的长度。那么我们需要利用更小的子问题求解当前问题,所以在for循环中又递归调用LIS。 为了避免重复求解,我们使用数组int[] cache记录求解过问题的答案。现在我们只需要循环的调用LIS函数,将各种问题的规模都交给LIS函数来求解,最大值就是数组nums的LIS。 全部代码如下: 解法2 – O(nlogn) 解法2是一个神奇的解法,我们一边读取nums数组,一边维护一个由nums形成的递增子序列 –…

Read more

140. 单词拆分 II

题目描述 给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,在字符串中增加空格来构建一个句子,使得句子中所有的单词都在词典中。返回所有这些可能的句子。 说明: 分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。 示例 1: 输入:s = “catsanddog”wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]输出:[  “cats and dog”,  “cat sand dog”] 示例 2: 输入:s = “pineapplepenapple”wordDict = [“apple”, “pen”, “applepen”, “pine”, “pineapple”]输出:[  “pine apple pen apple”,  “pineapple pen apple”,  “pine applepen apple”]解释: 注意你可以重复使用字典中的单词。 示例 3: 输入:s = “catsandog”wordDict = [“cats”, “dog”, “sand”, “and”,…

Read more

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。 说明: 拆分时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。 示例 1: 输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。 示例 2: 输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词。 示例 3: 输入: s = “catsandog”, wordDict =…

Read more

120. 三角形最小路径和

题目描述 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/triangle 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这道题目使用dp来求解,通过之前求得小规模的问题计算更大规模的问题。题目提到“每一步只能移动到下一行中相邻的结点上”,我们把题目给定的样例按照最左端对其,我们将这个数组记为triangle。 [ [2], [3,4], [6,5,7], [4,1,8,3] ] 我们在triangle数组中找一个比较general的case,对于元素8,它的上一行只有5和7能够走到8。也就是说当元素处于第i行第j列时(i,j从0计数),只能从i-1, j-1与i-1, j的位置走来。我们就可以定义数组dp[i][j]表示自顶向下走到第i, j位置时最小路径和,有dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]。 需要注意一点的是越界处理。当i=0,j=0时,自顶向下只有triangle[0][0]一个元素,取dp[i][j] = trangle[i][j];当j=0时,dp[i-1][j-1]是越界的,取dp[i][j] = dp[i-1][j] + triangle[i][j];当j=i时,dp[i-1][j]是越界的,取dp[i][j] = dp[i-1][j-1] + triangle[i][j]。 在实现时,我们采用Bottom-up的解法,声明与triangle数组同型(大小一致)的数组dp,递增变量i,j,将变量带入公式循环更新dp数组,最终的答案为min(dp[dp.length – 1])。在实现中,为了避免扫描dp[dp.length – 1]来求最小值,我们使用临时变量来存储当前遇到的最小值。 解法1优化 题目提到“如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。”,下面我们就来优化解法1的空间复杂度。通过观察dp公式,可以看出dp[i][j]仅依赖于dp[i-1][j-1]与dp[i-1][j]。那我们可以声明大小为dp[2][|triangle|]的数组,循环使用dp[0]与dp[1]。dp[0]表示上一轮计算结果,dp[1]表示本轮计算结果,当完成一轮迭代后交换dp[0]与dp[1]。

Read more

70. 爬楼梯

题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 注意:给定 n 是一个正整数。 示例 1: 输入: 2输出: 2解释: 有两种方法可以爬到楼顶。 1 阶 + 1 阶 2 阶 示例 2: 输入: 3输出: 3解释: 有三种方法可以爬到楼顶。 1 阶 + 1 阶 + 1 阶 1 阶 + 2 阶 2 阶 + 1 阶 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/climbing-stairs著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 这是一道简单的DP题目,是DP的应用之一 – 计数。给定一个台阶数目n,我们可以从n-1节台阶跳一步到达第n节;也可以从n-2跳两步到达第n节。我们把到达第n节台阶的爬楼梯方法记为dp[n],那么有dp[n] = dp[n-1]…

Read more

312. 戳气球

题目描述 有 n 个气球,编号为0 到 n-1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。每当你戳破一个气球 i 时,你可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后,气球 left 和气球 right 就变成了相邻的气球。 求所能获得硬币的最大数量。 说明: 你可以假设 nums[-1] = nums[n] = 1,但注意它们不是真实存在的所以并不能被戳破。 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100 示例: 输入: [3,1,5,8] 输出: 167 解释: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> []   coins = 315 + 358…

Read more

174. 地下城游戏

题目描述 一些恶魔抓住了公主(P)并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士(K)最初被安置在左上角的房间里,他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下,他会立即死亡。 有些房间由恶魔守卫,因此骑士在进入这些房间时会失去健康点数(若房间里的值为负整数,则表示骑士将损失健康点数);其他房间要么是空的(房间里的值为 0),要么包含增加骑士健康点数的魔法球(若房间里的值为正整数,则表示骑士将增加健康点数)。 为了尽快到达公主,骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。 例如,考虑到如下布局的地下城,如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下,则骑士的初始健康点数至少为 7。 -2 (K) -3 3 -5 -10 1 10 30 -5 (P) 说明: 骑士的健康点数没有上限。 任何房间都可能对骑士的健康点数造成威胁,也可能增加骑士的健康点数,包括骑士进入的左上角房间以及公主被监禁的右下角房间。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/dungeon-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – DP 题目给定的数组dungeon存放了走入每个房间造成的血量变化,为了救出公主,要求到达右下角(P)时扣除外血量至少为1,因此我们可以从P点逆行回到起点K,求出起点K要求的最少血量。我们定义一个二维数组dp[|dungeon|+1][|dungeon[0]|+1],dp数组比原数组“大了一圈“,这样做能够方便我们统一地处理逻辑,否则需要判断边界条件。到达P点以后还会扣除或者增加血量,所以走过P点到达右方或下方的血量至少需要1。 图1展示了题目的例子计算dp数组后的结果。要想求出到达位置i,j需要的最少血量,那么可以从位置i+1,j与i,j+1逆推而来。例如dp[2][1]=1,dp[1][2]=5,dungeon[1][1] = -10,说明我们只需要在位置1,1有血量11,就能够到达[2][1]。还有一点要注意,血量不可能为负数。例如在2,1处能够加血30,那我们不能说到达2,1时只需要-29点血量,然后再给我加上30变成1,这是不对的,血量不能为负值。所以在计算完min(dp[i+1][j], dp[i][j+1])+dungeon[i][j]还需要对1取最大。 该解法时间复杂度为O(m*n),m与n为dungeon数组长与宽。全部代码如下:

Read more

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) 我们定义与nums同型的一维数组dp,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, r]的连续子数组的最大值,取max1、max2、max3中三者最大的作为[l, r]的连续子数组最大和,然后返回。…

Read more