lthero

LeetCodeCampsDay48单调栈part01 初识单调栈 单调栈 什么时候用单调栈呢？ 通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。 如果暴力求解，比如两层for循环，时间复杂度是O(n^2) 那么单调栈的原理是什么呢？为什么时间复杂度是O(n)就可以找到每一个元素的右边第一个比它大的元素位置呢？ 单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。 更直白来说，就是用一个栈来记录我们遍历过的元素，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。 在使用单调栈的时候首先要明确如下几点： 单调栈里存放的元素是什么？ 单调栈里只需要存放元素的下标i就可以了，如果需要使用对应的元素，直接T[i]就可以获取。 单调栈里元素是递增呢？ 还是递减呢？ 注意以下讲解中，顺序的描述为 从栈头到栈 ...

LeetCodeCampsDay46动态规划part13 使用dp解决回文串和回文序列问题 647. 回文子串 https://leetcode.cn/problems/palindromic-substrings/ 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 示例 1： 123输入：s = "abc"输出：3解释：三个回文子串: "a", "b", "c" 示例 2： 123输入：s = "aaa"输出：6解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa" 提示： 1 <= s.length <= 1000 s 由小写英文字母组成 普通思路 本题和前面写过的26. 单词拆分有点像 需要将s拆分 ...

LeetCodeCampsDay45动态规划part12 下面几个子序列的题目都需要使用二维dp，而且关于两个字符串删除问题 并且都需要扩展dp的大小为dp(len(t1)+1, len(t2)+1)，第一行、第一列往往需要填充 所有涉及到两个字符串的dp问题，都有相似的状态转移过程 其中text1[i - 1] == text2[j - 1]，dp[i][j] 以及text1[i - 1] != text2[j - 1]，dp[i][j] 而dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]三种状态转移过来，只要能找到不同条件下状态转移的过程就好解决了 115. 不同的子序列 https://leetcode.cn/problems/distinct-subsequences/ 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。 测试用例保证结果在 32 位有符号整数范围内。 示例 1： 1234567输入：s = "rabbbit", t = "rabbit&qu ...

LeetCodeCampsDay44动态规划part11 下面几个子序列的题目都需要使用二维dp，一个维度给text1另一个给text2 并且都需要扩展dp的大小为dp(len(t1)+1, len(t2)+1)，第一行、第一列往往需要填充 所有涉及到两个字符串的dp问题，都有相似的状态转移过程 其中text1[i - 1] == text2[j - 1]，dp[i][j] 以及text1[i - 1] != text2[j - 1]，dp[i][j] 而dp[i][j]只能从dp[i - 1][j - 1]、dp[i - 1][j]、dp[i][j - 1]三种状态转移过来，只要能找到不同条件下状态转移的过程就好解决了 1143. 最长公共子序列 https://leetcode.cn/problems/longest-common-subsequence/ 给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。 一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某 ...

LeetCodeCampsDay43动态规划part10 使用动态规划解决子序列问题 非连续子序列可以看成模板，而连续子序列只是非连续子序列的特例 最长重复子序列需要使用二维dp（每个维度对应一个数组序列） 300. 最长递增子序列 https://leetcode.cn/problems/longest-increasing-subsequence/ 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1： 123输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例 2： 12输入：nums = [0,1,0,3,2,3]输出：4 示例 3： 12输入：nums = [7,7,7,7,7,7,7]输出：1 提示： 1 <= nums.length <= 2500 -104 <= nums[i] ...

LeetCodeCampsDay42动态规划part09 买卖股票的另类问题 309. 买卖股票的最佳时机含冷冻期 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/ 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 **注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 123输入: prices = [1,2,3,0,2]输出: 3 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出] 示例 2: 12输入: prices = [1]输出: 0 提示： 1 <= prices.length <= 5000 0 <= prices[i] <= 1000 动态规划思路 dp定义与含义 根据状态转移图 ...

LeetCodeCampsDay41动态规划part08 股票问题从入门到通关 121. 买卖股票的最佳时机 https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/ 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。 示例 1： 1234输入：[7,1,5,3,6,4]输出：5解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。 示例 2： 123输入：prices = [7,6,4,3,1]输出：0解释：在这种情况下, 没有交易完成, 所以最大利润为 0。 提示： 1 <= pric ...

LeetCodeCampsDay39动态规划part07 198. 打家劫舍 https://leetcode.cn/problems/house-robber/ 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。 示例 1： 1234输入：[1,2,3,1]输出：4解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。 示例 2： 1234输入：[2,7,9,3,1]输出：12解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。 提示： 1 <= nums.length <= 100 0 <= nums[i] ...

LeetCodeCampsDay38动态规划part06 最小个数问题：零钱兑换、完全平方数 求排列问题：单词拆分 322. 零钱兑换 https://leetcode.cn/problems/coin-change/ 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 示例 1： 123输入：coins = [1, 2, 5], amount = 11输出：3 解释：11 = 5 + 5 + 1 示例 2： 12输入：coins = [2], amount = 3输出：-1 示例 3： 12输入：coins = [1], amount = 0输出：0 提示： 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104 动态规划思路 完全背包、装满到target的最小物品数量的问题 ...

LeetCodeCampsDay37动态规划part05 完全背包问题 完全背包 01背包：每个物品最多只能被拿一次 完全背包：每个物品可被拿无限次数 举例，背包最大重量为4，物品为： 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 每件商品都有无限个！ 问背包能背的物品最大价值是多少？ 确定dp数组与下标含义 先使用较好理解的二维dp数组：dp[i][j]表示从下标为从0到i的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少 确定递推公式 以dp[1][4]为例，有两种情况，1）放物品1；2）不放物品1 如果装不下物品1，那背包的价值是dp[0][4]吗？即 只放物品0 并且容量为4的情况？如下图所示 没错，在装不下放物品1时的情况与01背包一致； 如果装得下物品1，那背包的价值上是max(dp[0][4], dp[0][4 - weight[1]] + val[4]) 吗？ 并不是！在“装得下物品1时”的情况与01背包不同 （如下图所示） 在01背包时，因为物品1只能被装一次，所以我们只会考虑dp ...