门户网站建设需注意的问题,新浪微博网页版qq登录入口,怎么推广自己的微信,引流推广方案【问题描述】[中等]
给定一个无序的整数数组#xff0c;找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]#xff0c;它的长度是 4。
说明:可能会有多种最长上升子序列的组合#xff0c;你只需要输出对应的…【问题描述】[中等]
给定一个无序的整数数组找到其中最长上升子序列的长度。示例:输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]它的长度是 4。
说明:可能会有多种最长上升子序列的组合你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
【解答思路】
1. 动态规划 时间复杂度O(N^2) 空间复杂度O(N)
import java.util.Arrays;public class Solution {public int lengthOfLIS(int[] nums) {int len nums.length;if (len 2) {return len;}int[] dp new int[len];Arrays.fill(dp, 1);for (int i 1; i len; i) {for (int j 0; j i; j) {if (nums[j] nums[i]) {dp[i] Math.max(dp[i], dp[j] 1);}}}int res 0;for (int i 0; i len; i) {res Math.max(res, dp[i]);}return res;}
}
2. 动态规划压缩空间贪心二分 时间复杂度O(NlogN) 空间复杂度O(N)
public class Solution {public int lengthOfLIS(int[] nums) {int len nums.length;if (len 1) {return len;}// tail 数组的定义长度为 i 1 的上升子序列的末尾最小是几int[] tail new int[len];// 遍历第 1 个数直接放在有序数组 tail 的开头tail[0] nums[0];// end 表示有序数组 tail 的最后一个已经赋值元素的索引int end 0;for (int i 1; i len; i) {// 【逻辑 1】比 tail 数组实际有效的末尾的那个元素还大if (nums[i] tail[end]) {// 直接添加在那个元素的后面所以 end 先加 1end;tail[end] nums[i];} else {// 使用二分查找法在有序数组 tail 中// 找到第 1 个大于等于 nums[i] 的元素尝试让那个元素更小int left 0;int right end;while (left right) {// 选左中位数不是偶然而是有原因的原因请见 LeetCode 第 35 题题解// int mid left (right - left) / 2;int mid left ((right - left) 1);if (tail[mid] nums[i]) {// 中位数肯定不是要找的数把它写在分支的前面left mid 1;} else {right mid;}}// 走到这里是因为 【逻辑 1】 的反面因此一定能找到第 1 个大于等于 nums[i] 的元素// 因此无需再单独判断tail[left] nums[i];}// 调试方法// printArray(nums[i], tail);}// 此时 end 是有序数组 tail 最后一个元素的索引// 题目要求返回的是长度因此 1 后返回end;return end;}// 调试方法以观察是否运行正确private void printArray(int num, int[] tail) {System.out.print(当前数字 num);System.out.print(\t当前 tail 数组);int len tail.length;for (int i 0; i len; i) {if (tail[i] 0) {break;}System.out.print(tail[i] , );}System.out.println();}public static void main(String[] args) {int[] nums new int[]{3, 5, 6, 2, 5, 4, 19, 5, 6, 7, 12};Solution solution new Solution8();int lengthOfLIS solution8.lengthOfLIS(nums);System.out.println(最长上升子序列的长度 lengthOfLIS);}
}
【总结】
1.子序列和子串 2.动态规划高度概括
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
3.动态规划详细说明
1、思考状态重点
状态的定义先尝试「题目问什么就把什么设置为状态」 然后思考「状态如何转移」如果「状态转移方程」不容易得到尝试修改定义目的依然是为了方便得到「状态转移方程」。 「状态转移方程」是原始问题的不同规模的子问题的联系。即大问题的最优解如何由小问题的最优解得到。
2、思考状态转移方程核心、难点
状态转移方程是非常重要的是动态规划的核心也是难点
常见的推导技巧是分类讨论。即对状态空间进行分类
归纳「状态转移方程」是一个很灵活的事情通常是具体问题具体分析
除了掌握经典的动态规划问题以外还需要多做题
如果是针对面试请自行把握难度。掌握常见问题的动态规划解法理解动态规划解决问题是从一个小规模问题出发逐步得到大问题的解并记录中间过程
「动态规划」方法依然是「空间换时间」思想的体现常见的解决问题的过程很像在「填表」。
3、思考初始化
初始化是非常重要的一步错步步错。初始化状态一定要设置对才可能得到正确的结果。
角度 1直接从状态的语义出发
角度 2如果状态的语义不好思考就考虑「状态转移方程」的边界需要什么样初始化的条件
角度 3从「状态转移方程」方程的下标看是否需要多设置一行、一列表示「哨兵」sentinel这样可以避免一些特殊情况的讨论。
4、思考输出
有些时候是最后一个状态有些时候可能会综合之前所有计算过的状态。
5、思考优化空间也可以叫做表格复用
「优化空间」会使得代码难于理解且是的「状态」丢失原来的语义初学的时候可以不一步到位。先把代码写正确是更重要 「优化空间」在有一种情况下是很有必要的那就是状态空间非常庞大的时候处理海量数据此时空间不够用就必须「优化空间」 非常经典的「优化空间」的典型问题是「0-1 背包」问题和「完全背包」问题。
4. 动态规划思考
边界问题考虑清楚第二第三步动态就是做表格 想清楚方向自底向上 子问题 学基础 再解决问题 通识教育自顶向下 一般解决问题思路
转载链接https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
