题目描述 描述转载自力扣《154. 寻找旋转排序数组中的最小值 II》已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到： 若旋转 4 次，则可以得到 [4,5,6,7,0,1,4] 若旋转 7 次，则可以得到 [0,1,4,4,5,6,7] 注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。 给你一个可能存在 重复 元素值的数组 nums ，...

题目描述 描述转载自力扣《15. 三数之和》给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。 示例1 输入：nums = [-1,0,1,2,-1,-4]输出：[[-1,-1,2],[-1,0,1]] 示例2 输入：nums = []输出：[] 示例3 输入：nums = [0]输出：[] 解题思路 如果本题允许出现重复的三元组，那就只需要三重循环暴力算法就能够得出答案了。下面是伪代码。 for i = 1..(len -...

题目描述 描述转载自力扣《33. 搜索旋转排序数组》整数数组 nums 按升序排列，数组中的值 互不相同 。 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums ...

题目描述 描述转载自力扣《80. 删除有序数组中的重复项 II》给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 说明：为什么返回数值是整数，但输出的答案是数组呢？请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝 int len = removeDuplicates(nums); // 在函数里修改输...

题目描述 描述转载自力扣《74. 搜索二维矩阵》编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性： 每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例1 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3输出：true 示例2 输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13输出：false 解题思路 比较 target 和每一行最后一个元素，并截断为...

题目描述 描述转载自力扣《152. 乘积最大子数组》给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。 示例1 输入: [2,3,-2,4]输出: 6解释: 子数组 [2,3] 有最大乘积 6。 示例2 输入: [-2,0,-1]输出: 0解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。 解题思路 完成这题之前，建议先完成牛客《子数组的最大累加和问题》 或 力扣《最大子序和》。本题是基于上面给出的题目变型的。如果已经做过并理解这道题的解法，可以直接跳到第 3 条。 在我们完成牛客《子数组的最大累加和...

题目描述 描述转载自力扣《190. 颠倒二进制位》颠倒给定的 32 位无符号整数的二进制位。 提示： 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。 进阶： 如果多次调用这个函数，你将如何优化你的算法？ 示例1： 输入: 000000101001010000011110100...

题目描述 描述转载自力扣《面试题 17.21. 直方图的水量》给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的直方图，在这种情况下，可以接 6 个单位的水（蓝色部分表示水）。 感谢 Marcos 贡献此图。 示例 输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6 解题思路 其实不难，每个格子能装的水量本质就是木桶效应，比较左边和右边哪根柱子最低，然后用最低的那个值减去自己这根柱子的高度，当然，减去之后的值不能为负数，否则就是不能装水的意思。 ...

题目描述 描述转载自力扣《354. 俄罗斯套娃信封问题》给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。 示例1 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]输出：3解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7...

题目描述 描述转载自力扣《300. 最长递增子序列》给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例1 输入：nums = [10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。 示例2 输入：nums = [0,1,0,3,2,3]输出：4 示例3 输入：nums = [7,7,7,7,7,7,7]输出：1 解题思路 先讲结论：这种类型的题...

单串问题是什么 单串问题是线性动态规划中最简单的一类题，通过输入一串数，即数组，考虑 [0..i] 上原问题的解。而原问题的最优解，最常见的就是取 i 位置上的解，当然也有不在 i 上的情况，我们先只讨论取 i 位置的解的情况。 最优解依赖比 i 小的 个子问题：i 只与前面固定个数的子问题有关，如斐波那契数列 只考虑 i - 1 和 i - 2 的解。练习题：跳台阶 最优解依赖比 i 小的 个子问题：i 与 [0..i-1] 的子问题都有关，比如之前《Prologue - 简述动态规划》 举过的例子（最长递增子序列）他的转移方程为 dp[n] = max(dp[n-1]..dp[0...

线性动态规划是什么？   顾名思义，线性动态规划推导问题是线性的，通俗地讲就是逐元素进行推导。拿上期《Prologue - 简述动态规划》 举过的例子（最长递增子序列）来讲，我们可以从两个角度描述线性动态规划 状态定义：dp[n] 是 [0..n] 上问题最优解 状态转移：dp[n] = max(dp[n-1]..dp[0]) + 1 脱离这个例子，将其抽象，即dp[n] = f(dp[n-1]..dp[0])   根据上面的状态定义和状态转移两个方面得知，大规模的问题只与小规模问题的解有关，所以我们解题的过程就是从小到大推导问题的解，这种方式就是线性动态规划。 线性动态规划分类   ...