221. 最大正方形

题目描述 在一个由 0 和 1 组成的二维矩阵内,找到只包含 1 的最大正方形,并返回其面积。 示例: 输入: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 输出: 4 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/maximal-square著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 题目要求找到矩阵matrix中只包含1的最大正方形,并返回其面积。我们可以转换成求子方阵中1的数量。如果子方阵中所有元素的和与子方阵的size的平方相等,那么这个方阵中的元素肯定都是1。 如果采用暴力的解法: 枚举每个起始位置时间复杂度O(n^2); 在该位置下枚举子方阵的大小时间复杂度O(n); 最后需要统计该方阵有多少个1,时间复杂度为O(n^2)。 那么整体来看,使用暴力法的时间复杂度为O(n^5)。这么高的复杂度,肯定是通不过的。但是我们可以利用预计算,提前求出从左上角(0, 0)到任意位置的矩阵中1的数量。再通过简单的加减法,就能求得任意子方阵中1的数量: 图1描述了对于矩阵matrix,通过预计算求得从(0, 0)到任意位置(row, col)的和。我们先忽略sum这个矩阵是怎么求得的,下面我们用它实现O(1)的时间复杂度来计算任意子方阵中1的数量。 图1中红色区域是我们想要求得的解,红色 = 橙色 – 蓝色 – 绿色 + 紫色。因为从左上角到任意位置的和都通过预计算求过了,只需要带入公式用O(1)的时间复杂度就能求得起始位置为(row, col),大小为size的方阵的和。对于整个问题,我们只需要枚举起始位置和枚举方阵的大小,整体的时间复杂度为O(n^3)。 上面的那个例子可以用公式可以表述为:…

Read more

673. 最长递增子序列的个数

题目描述 给定一个未排序的整数数组,找到最长递增子序列的个数。 示例 1: 输入: [1,3,5,4,7] 输出: 2 解释: 有两个最长递增子序列,分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。 示例 2: 输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1,并且存在5个子序列的长度为1,因此输出5。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。 来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。 解法1 – Top-down 这道题目是第300题的升级,那道题目仅要求找出最长递增子序列(LIS)的长度,而这道题目需要统计LIS有多少个。为了求出数组nums的LIS个数,我们先要求得最长递增子序列的长度maxLen。然后扫描nums数组,统计LIS长度为maxLen的个数。 首先我们实现一个函数,求数组nums的LIS的长度(参考300题的Top-down解法)。我们定义函数lengthOfLIS(int[] nums, int n),表示计算数组nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)能够形成LIS的长度。例如我们有nums = [1,2,3,2,2],那么lengthOfLIS(nums, 4) = 2而不是3,因为我们必须使用nums[4]。 为了求num前n个元素的LIS,我们可以使用递归来解决。对于长度n,我们向前寻找某一元素i,使其满足nums[n] > nums[i](递增的定义),然后递归调用lengthOfLIS(nums, i),即求解nums数组前i个元素的LIS。代码如下: 下一步,我们定义函数count(int[] nums, int n)用于计算nums前n个元素(n从1开始,包含第n个且必须使用第n个元素)构成的LIS长度为maxLen的递增子序列数量。它会调用上面实现的函数lengthOfLIS(nums, n)。在这里我们举一个例子,nums = [1,3,2,4,5],则 count(nums,…

Read more

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