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

209. 长度最小的子数组

题目描述 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。 示例:  输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。 https://leetcode-cn.com/problems/minimum-size-subarray-sum/ 解法1 – 朴素算法O(n^2) 解法1使用朴素算法,我们使用指针i, j(0<=i<=j<|nums|)来描述子数组,然后计算i到j区间元素到和,如果大于等于s则取j – i + 1作为可能到解ans;如果小于s则j右移。为了实现O(1)时间复杂度的区间求和,我们可以使用prefix sum算法预先计算前缀和。当指针i和j扫描完所有的连续区间,我们取最小的解就是答案。如果找不到子数组当和大于等与s,就返回0。 需要注意一点,当找到一对i, j我们就可以退出内层循环。因为继续找下去的子序列长度已定大于(i-j+1),否则会TLE。算法的时间复杂度为O(n^2),空间复杂度为O(n) (存放前缀和)。全部代码如下: 解法2 – 优化的朴素算法O(nlogn) 我们沿用解法1的思路,但是对寻找连续区间上进行优化。我们让i = [0, |nums|),使用二分搜索寻找j,其中i <= j < |nums|。因为我们有前缀和数组prefix,我们可以在O(logn)的时间内找到一个下界(lower bound),使得prefix[j] – prefix[i] >= s。那么,j – i +1就是其中一个解,当i遍历完整个数组时,就取最小的那个解作为答案。…

Read more

4. 寻找两个有序数组的中位数

题目描述 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5 https://leetcode-cn.com/problems/median-of-two-sorted-arrays/ 解法1 解法1使用Binary Search。考虑两个排序数组nums1与nums2,合并后后形成有序数组nums。记|nums1| = n1, |nums2| = n2, |nums| = n, 有n = n1 + n2。对nums求中位数,那么需要取nums的第k个数(n是奇数)或与第k+1个数取平均(n是偶数),其中k =…

Read more

275. H指数 II

题目描述 给定一位研究者论文被引用次数的数组(被引用次数是非负整数),数组已经按照升序排列。编写一个方法,计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”(high citations),一名科研人员的 h 指数是指他(她)的 (N 篇论文中)至多有 h 篇论文分别被引用了至少 h 次。(其余的 N – h 篇论文每篇被引用次数不多于 h 次。)” 示例: 输入: citations = [0,1,3,5,6] 输出: 3 解释: 给定数组表示研究者总共有 5 篇论文,每篇论文相应的被引用了 0, 1, 3, 5, 6 次。   由于研究者有 3 篇论文每篇至少被引用了 3 次,其余两篇论文每篇被引用不多于 3 次,所以她的 h 指数是 3。 说明: 如果 h 有多有种可能的值 ,h 指数是其中最大的那个。 进阶: 这是 H指数 的延伸题目,本题中的 citations 数组是保证有序的。 你可以优化你的算法到对数时间复杂度吗? https://leetcode-cn.com/problems/h-index-ii/ 解法1 本题目和274. H指数的区别是,文章已经按照应用次数排序。此外,题目要求优化到对数时间复杂度,很自然能联想到Binary Search。…

Read more