【每日一题】2022年2月9日-NC91 最长上升子序列(三)

描述
给定数组 arr ,设长度为 n ,输出 arr 的最长上升子序列。(如果有多个答案,请输出其中 按数值(注:区别于按单个字符的ASCII码值)进行比较的 字典序最小的那个)

 

答案:

import java.util.*;


public class Solution {
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型一维数组
     */
    public int[] LIS (int[] arr) {
        int n = arr.length;
        if (n == 0) {
            return null;
        }
        int[] dp = new int[n];
        int max = Integer.MAX_VALUE;
        int index = -1;
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                if (dp[i] >= max) {
                    index = i;
                    max = dp[i];
                }
            }
        }
        //赋值
        int[] res = new int[max];
        for (int j = max, i = index; j > 0; i--) {
            if (dp[i] == j) {
                res[j--] = arr[i];
            }
        }
        return res;
    }
}

 

本文来自博客园,作者:哥们要飞,转载请注明原文链接:https://www.cnblogs.com/liujinhui/p/15873917.html

推荐这些文章:

【每日一题】【奇偶分别中心扩展/动态规划】2022年2月5日-NC最长回文子串的长度

描述对于长度为n的一个字符串A(仅包含数字,大小写英文字母),请设计一个高效算法,计算其中最长回文子串的长度。

 
方法1:奇数偶数分别从中心扩展

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param A string字符串
* @return int整型
*/
public int getLongestPalindrome (String A) {
...

【每日一题】2022年1月18日-NC61 两数之和

描述给出一个整型数组 numbers 和一个目标值 target,请在数组中找出两个加起来等于目标值的数的下标,返回的下标按升序排列。(注:返回的数组下标从1开始算起)

 
算法:

import java.util.*;

public class Solution {
/**
* @param numbers int整型一维数组
* @param target int整型
* @return int整型一维数组
*/
public int[] twoSum (int[] numbers, int target) {...

【每日一题】【快速排序过程、循环过程无=、递归参数】2022年1月16日-NC140 排序

快速排序

 
对时间复杂度和空间复杂度有要求
方法1:快速排序-递归

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
quickSort(arr, 0, arr.length - ...

【每日一题】【双层循环、set判断】【双指针优化】2022年1月13日-NC41 最长无重复子数组

描述

给定一个长度为n的数组arr,返回arr的最长无重复元素子数组的长度,无重复指的是所有数字都不相同。
子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
 
数据范围:0\le arr.length \le 10^60≤arr.length≤106,0 < arr[i] \le 10^50<arr[i]≤105
要求:空间复杂度 O(n)O(n),时间复杂度 O(nlogn)O(nlogn)

方法1:双层循环,加入set,有重复看下一个

import java.util.*;
...

【每日一题】【动态规划】2022年1月30日-NC127 最长公共子串

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串
题目保证str1和str2的最长公共子串存在且唯一。

 
方法1:不算动态规划

import java.util.*;

public class Solution {
/**
* longest common substring
* @param str1 string字符串 the string
* @param str2 string字符串 the string
* @return string字符串
*/
public String...

2022-3-4剑指offer day22

题1:
JZ85 连续子数组的最大和(二)
描述

输入一个长度为n的整型数组array,数组中的一个或连续多个整数组成一个子数组,找到一个具有最大和的连续子数组。
1.子数组是连续的,比如[1,3,5,7,9]的子数组有[1,3],[3,5,7]等等,但是[1,3,7]不是子数组
2.如果存在多个最大和的连续子数组,那么返回其中长度最长的,该题数据保证这个最长的只存在一个
3.该题定义的子数组的最小长度为1,不存在为空的子数组,即不存在[]是某个数组的子数组
4.返回的数组不计入空间复杂度计算
 
数据范围:

1<=n<=10^51<=n<=1...

【每日一题】【二分mid&贪心】2022年2月8日-NC163 最长上升子序列(一)

1、描述给定一个长度为 n 的数组 arr,求它的最长严格上升子序列的长度。所谓子序列,指一个数组删掉一些数(也可以不删)之后,形成的新数组。例如 [1,5,3,7,3] 数组,其子序列有:[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

2、介绍
最长递增子序列(longest increasing subsequence),简称LIS
3、方法1:贪心+二分

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
...

【每日一题】【动态规划】2022年1月31日-NC92 最长公共子序列(二)

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列

 

本文来自博客园,作者:哥们要飞,转载请注明原文链接:https://www.cnblogs.com/liujinhui/p/15858137.html

...

动态规划DP入门问题----最大连续子序列,最长不下降子序列(可以不连续),最长公共子序列

一、最大连续子序列
1.题目叙述

对于一个数字序列A1A2A3...An,求出连续子序列的最大和,如对于序列-2,11,-4,13,-5,-2,其中的最大序列和是11+(-4)+13=20 

2.动态规划解法
将问题拆分成子问题,即dp[i]表示以A[i]为结尾的子序列的最大和,最后对于这些dp数组找出最大值即可,状态转移方程为:

dp[i] = max{ dp[i-1] + A[i] }  状态dp[i]表示,当前以A【i】结尾的子序列的最大和

3.方法一是经典算法,方法二是根据状态方程优化而来。

#include<iostream>
#inclu...

动态规划-最长连续递增序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
思路:
严格和前一个数比较,而不是前面的某个数。
代码:

class Solution {
public int findLengthOfLCIS(int[] nums) {
int len = nums.length;
int[] dp = new int[len];
Arrays.fill(dp, 1);
for (int i = 1; i < len; i++) {
if (nums[i] > nu...

文章标题:【每日一题】2022年2月9日-NC91 最长上升子序列(三)
文章链接:https://www.dianjilingqu.com/51185.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>