字节前端实习的两道算法题，看看强度如何

最长严格递增子序列

题目描述

给你一个整数数组nums，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例：
输入：nums = [2,1,6,3,5,4]
输出：3
解释：最长递增子序列是 [1,3,4]，因此长度为 3。

思路

这道题要求最长上升子序列的长度，可以使用动态规划或贪心+二分查找两种方法来解决。

1. 动态规划 定义状态：dp[i]表示以第i个元素为结尾的最长上升子序列的长度。 状态转移方程：对于第i个元素，枚举其前面的元素j，如果nums[i] > nums[j]，则dp[i] = dp[j] + 1。同时，在每次更新dp[i]时，更新ans为其最大值。
2. 贪心+二分查找 定义一个数组d，d[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)varlengthOfLIS=function(nums){if(nums.length ===0)return0const dp =newArray(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)varlenghtOfLIS=function(nums){let n = nums.length;if(n ===0)return0;let d =newArray(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 。

思路

我们可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当我们遍历到叶子节点，且此时路径和恰为目标和时，我们就找到了一条满足条件的路径。

代码

varpathSum=function(root, target){let ans =[],path =[];letdfs=(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;};