lthero

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 ...

LeetCodeCampsDay36动态规划part04 01背包，分割等和子集的变式题目 416.分割等和子集是问：能否将背包装满到target值 1049.石头：尽量将背包装满到target值，如果装不到，则最小差值是多少 494.目标和：装满一个到target值，有多少种方法 474.一和零：装满一个背包，最多有多少物品 1049. 最后一块石头的重量 II https://leetcode.cn/problems/last-stone-weight-ii/ 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。 示例 1： 1234567输入：stones = ...

LeetCodeCampsDay35动态规划part03 背包问题/01背包/一维dp数组与二维dp数组的执行区别 背包问题 背包问题可以分成01背包/完全背包/多重背包与分组背包； 不过搞定01背包与完全背包就可以了 01背包 有n件物品和一个最多能背重量为w 的背包。 第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 这是标准的背包问题，以至于很多同学看了这个自然就会想到背包，甚至都不知道暴力的解法应该怎么解了。 这样其实是没有从底向上去思考，而是习惯性想到了背包，那么暴力的解法应该是怎么样的呢？ 每一件物品其实只有两个状态，取或者不取 ，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是O(2^n)，这里的n表示物品数量。 所以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！ 在下面的讲解中，我举一个例子： 背包最大重量为4。 物品为： 重量 价值 物品0 1 15 物品1 3 20 物品2 4 30 问背包能背的物品最大价值是多少？ ...

LeetCodeCampsDay34动态规划part02 62. 不同路径 https://leetcode.cn/problems/unique-paths/ 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？ 示例 1： 12输入：m = 3, n = 7输出：28 示例 2： 1234567输入：m = 3, n = 2输出：3解释：从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向下 -> 向下2. 向下 -> 向下 -> 向右3. 向下 -> 向右 -> 向下 示例 3： 12输入：m = 7, n = 3输出：28 示例 4： 12输入：m = 3, n = 3输出：6 提示： 1 <= m, n <= 100 题目数据保证答案小于等于 2 * 109 动态规划思路 dp下标与数组含义: 一维数组即可，下标指地图下标，数组含意到达当 ...

LeetCodeCampsDay32动态规划paro01 动态规划基础 动态规划基础 什么是动态规划 在关于贪心算法，你该了解这些！ (opens new window)中我举了一个背包问题的例子。 例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。 动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。 但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。 所以贪心解决不了动态规划的问题。 其实大家也不用死扣动规和贪心的理论区别，后面做做题目自然就知道了。 而且很多讲解动态规划的文章都会讲最优子结构啊和重叠子问题啊这些，这些东西都是教科书的上定义，晦涩难懂而且不实用。 大家知道动规是由前一个状态推导出来的，而贪心是局部直接选最优的，对于刷题来说就够用了。 动态规划的解题步骤 确定dp数组以及下标的含义 研究递推公式 dp数组 ...

LeetCodeCampsDay31贪心part05 本题目有个和二叉树结合的，值得注意 56. 合并区间 https://leetcode.cn/problems/merge-intervals/ 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。 示例 1： 123输入：intervals = [[1,3],[2,6],[8,10],[15,18]]输出：[[1,6],[8,10],[15,18]]解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 示例 2： 123输入：intervals = [[1,4],[4,5]]输出：[[1,5]]解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。 提示： 1 <= intervals.length <= 104 intervals[i].length == 2 0 <= starti <= endi <= ...

LeetCodeCampsDay30贪心part04 三个区间问题的题目，用贪心算法解决 本题需要用到python的lambda表示式 x.sort(key = lambda x: (x[0], x[1])) 表示对列表x进行排序，优先对x[0]从小到大排序，再按x[1]从小到大 如果需要先从大到小，再从小到大，可以先使用-x[0] x.sort(key = lambda x: (-x[0], x[1])) 452. 用最少数量的箭引爆气球 https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/ 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 x``start，x``end， 且满足 xst ...