leetcode300-最长公共子序列

系统管理员 2023-05-30 04:56 15阅读 0赞

### 文章目录 ###

*  嘴上上升子序列
 *   *  题目描述
     *  code
     *   *  方法一: 暴力求解法
         *  方式二
         *  方式三：

# 嘴上上升子序列 #

## 题目描述 ##

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:

输入: [10,9,2,5,3,7,101,18]
    输出: 4 
    解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
    
    说明:
    
    可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
    你算法的时间复杂度应该为 O(n2)

## code ##

### 方法一: 暴力求解法 ###

public  class Solution {
            //方法一： 暴力求解
            public static int[] caled = new int[10000]; //保存以前计算的数据
            public static int[] p = new int[10000];
    
            public static int robot(int idx, int[] nums) {
                if (idx < 0) {
                    return 0;
                }
                //如果已经计算过了， 就不再使用递归进行重复计算了，节省效率
                if (caled[idx] > 0) {
                    return caled[idx];
                }
                int ans = 0;
                for (int i = 0; i < idx; ++i) {
                    if (nums[idx] > nums[i]) {
                        ans = Math.max(ans, robot(i, nums));
                    }
                }
                caled[idx] = ans + 1;
                return ans + 1;
            }
    
            public int lengthOfLIS(int[] nums) {
                //进行初始化操作
                for (int i = 0; i < caled.length; ++i) {
                    caled[i] = 0;
                }
                //进行初始化操作
                for (int i = 0; i < nums.length; ++i) {
                    p[i] = nums[i];
                }
                int n = nums.length;
                p[n] = 1000000;
                ++n;
                return robot(n - 1, p) - 1;
            }
        }

### 方式二 ###

//方式二： 优化方式： 递归转为非递归
    
        /**
         * 转非递归思路：
         * 将递归主过程进行拷贝
         * 将相关递归函数相关的处理，全部转为缓存的数组进行处理
         * 原先递归： 从后向前
         * 非递归： 需要改为 从前向后进行处理
         */
        static class Solution {
            public static int[] p = new int[10000];
            public static int[] f = new int[10000];
    
            public int lengthOfLIS(int[] nums) {
                for (int i = 0; i < f.length; i++) {
                    f[i] =0;
                }
                for (int i = 0; i < nums.length; ++i) {
                    p[i] = nums[i];
                }
                int n = nums.length;
                p[n] = 10000000;
                ++n;
                for (int idx = 0; idx < n; ++idx) {
                    int ans = 0;
                    for (int i = 0; i < idx; ++i) {
                        if (p[idx] > p[i]) {
                            ans = Math.max(ans, f[i]); //将结果存入f 缓存数组中
                        }
                    }
                    f[idx] = ans+1;
                }
                return f[n-1] -1;
            }
        }

### 方式三： ###

> 继续进行优化

package com.wangyg.leetcode;
    
    import org.junit.Test;
    import util.Logger;
    
    import java.util.Arrays;
    
    public class Leetcode300 {
        @Test
        public void test() {
            int[] nums = new int[]{10, 9, 2, 5, 3, 7, 101, 18};
    
            Solution solution = new Solution();
            System.out.println(solution.lengthOfLIS(nums));
        }
        //方法三
        //path是长度的定义
    
        /**
         *  min  i 一定是单调递增的，
         *
         *  所以使用动态规划+ 二分查找方式进行解决问题
         */
        class Solution {
            public int lengthOfLIS(int[] nums) {
                //dp是动态规划中的数组
                int[] dp = new int[nums.length]; //创建一个和原数组大小一样的数组
                int len =0;
                //进行遍历
                for (int num : nums) {
                    int i = Arrays.binarySearch(dp, 0, len, num); //使用二分查找， 查找当前的num
                    if (i < 0) { //如果小于0 ，就表示当前没有
                        i = -(i + 1);
                        Logger.info(" i" +i );
                    }
                    //一直插入当前的最小值 ,从结果来看一致插入当前的最小值，然后如果当前列索引和Len 相同，就向后移动，继续进行插入
                    dp[i] = num;
                    Logger.info("dp="+ Arrays.toString(dp));
                    if (i == len) {
                        len++;
                        Logger.info(" len = " + len);
                    }
                }
                return len;
            }
        }
    
    }