佛山市企业网站seo营销工具,一个网站可以做多少地区词,建筑信息公开平台,2022世界500强企业排名最长严格递增子序列
题目描述
给你一个整数数组nums#xff0c;找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列#xff0c;删除#xff08;或不删除#xff09;数组中的元素而不改变其余元素的顺序。例如#xff0c;[3,6,2,7] 是数组 [0,3,1,6,2,2,7…
最长严格递增子序列
题目描述
给你一个整数数组nums找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 输入nums [2,1,6,3,5,4] 输出3 解释最长递增子序列是 [1,3,4]因此长度为 3。
思路
这道题要求最长上升子序列的长度可以使用动态规划或贪心二分查找两种方法来解决。 动态规划 定义状态dp[i]表示以第i个元素为结尾的最长上升子序列的长度。 状态转移方程对于第i个元素枚举其前面的元素j如果nums[i] nums[j]则dp[i] dp[j] 1。同时在每次更新dp[i]时更新ans为其最大值。 贪心二分查找 定义一个数组dd[i]记录长度为i的上升子序列的末尾元素的最小值。对于一个新的元素num[i]如果num[i]大于d[len]说明可以扩展当前的最长上升子序列直接将其加入到d中否则在d中查找第一个大于等于num[i]的元素位置pos用num[i]替换它使得可以扩展更长的上升子序列。
两种方法的时间复杂度分别为O(n^2)和O(nlogn)空间复杂度都是O(n)。
代码
// 方法一动态规划时间复杂度O(n^2) 空间复杂度O(n)
var lengthOfLIS function(nums) {if(nums.length 0) return 0const dp new Array(nums.length).fill(1)let ans 1;for(let i 1 ; i nums.length; i ) {for(let j 0 ; j i ; j ) {if(nums[i] nums[j]) {dp[i] Math.max(dp[i],dp[j] 1);}}ans Math.max(dp[i],ans);}console.log(dp);return ans;
}; // 方法二贪心二分查找时间复杂度O(nlogn) 空间复杂度O(n)
var lenghtOfLIS function(nums) {let n nums.length;if(n 0) return 0;let d new Array(n 1).fill(0);let len 1;d[len] nums[0];for(let i 1; i n ; i ) {if(num[i] d[len]) {d[len] nums[i];} else {let l 1 , r len , pos 0;while(l r) {let mid (l r) 1;if(d[mid] num[i]) {pos mid;l mid 1;} else {r mid - 1;}}d[pos 1] nums[i];}}return len;
}
路径总和 II
题目描述
给你一个整数数组 nums 找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
输入nums [10,9,2,5,3,7,101,18] 输出4 解释最长递增子序列是 [2,3,7,101]因此长度为 4 。
思路
我们可以采用深度优先搜索的方式枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点且此时路径和恰为目标和时我们就找到了一条满足条件的路径。
代码
var pathSum function(root, target) {let ans [],path [];let dfs (root,target) {if(!root) return;path.push(root.val);target - root.val;if(root.left null root.right null target 0) {ans.push([...path]);}dfs(root.left,target);dfs(root.right,target);path.pop(root.val);}dfs(root,target);return ans;
};
