您的位置:时时app平台注册网站 > web前端 > 在贰个冬辰整数数组中,找寻接二连三进步部分

在贰个冬辰整数数组中,找寻接二连三进步部分

2019-11-08 03:51

希望有大神可以分享一下自己的解决方案

4.最长单调增长子序列

设置状态数组d[i],表示以s[i]这个元素结尾的最长的单调增长子序列的长度。

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/08.
//  Copyright © 2015年 YangKi. All rights reserved.

#include <cstdio>
#include <iostream>
#define length 9
using namespace std;

int s[length]={2,4,3,5,1,7,6,9,8};
int d[length];
int predecessor[length];//  里面的数字是当前元素的前置元素的坐标
int max(int a, int b)
{
    return a>b? a:b;
}

void print_seq(int index)
{
    if (predecessor[index]<index)
        print_seq(predecessor[index]);
    printf("%d ", s[index]);
}

void lis_length(int n)
{
    for (int i=0; i<length; i  )
        predecessor[i]=i;

    d[0]=1;
    for (int i=1; i<length; i  )
    {
        int maax=1;
        int temp;
        for (int j=0; j<i; j  )
        {
            if (s[j]<s[i])
                temp=d[j] 1;
            else temp=1;
            if(temp>maax)
            {
                maax=temp;
                predecessor[i]=j;
            }
        }
        d[i]=maax;
    }
    int maax=-1;
    int tail;
    for (int i=0; i<length; i  )
    {
        if (d[i]>maax)
        {
            maax=d[i];
            tail=i;
        }
    }
    print_seq(tail);
    printf("n");

    return;
}

int main()
{
    lis_length(length);

    return 0;
}

题目大意:
找出给定数组中的最长增长序列

下面是我自己的编写的代码,感觉还能再优化。

3.最长公共子序列

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/07.
//  Copyright © 2015年 YangKi. All rights reserved.


#include <cstdio>
#include <iostream>
#define X_length 7
#define Y_length 6
using namespace std;

int X[X_length 1]={-1,1,2,3,2,4,1,2};
int Y[Y_length 1]={-1,2,4,3,1,2,1};

int c[X_length 1][Y_length 1];//c[i][j]表示长度为i的x与j的y之间的lcs长度

int s[X_length 1][Y_length 1];//记录具体怎么安排
                              //1->situation1 (x[i]==y[j], use c[i-1][y-1])
                              //2->situation2 (x[i]!=y[j], use c[i-1][j]  )
                              //3->situation3 (x[i]!=y[j], use c[i][j-1]  )
void lcs_length(int a, int b)//x1...xa 与 y1...yb 的lcs长度
{
    for (int i=0; i<=X_length; i  )
        c[i][0]=0;
    for (int i=0; i<=Y_length; i  )
        c[0][i]=0;

    for (int i=1; i <= a; i  )
    {
        for (int j=1; j <= b; j  )
        {
            if (X[i]==Y[j])
            {
                c[i][j]=c[i-1][j-1] 1;
                s[i][j]=1;
            }
            else
            {
                if (c[i-1][j] >= c[i][j-1])
                {
                    c[i][j]=c[i-1][j];
                    s[i][j]=2;
                }
                else
                {
                    c[i][j]=c[i][j-1];
                    s[i][j]=3;
                }
            }
        }
    }

    printf("lcs: %dn", c[a][b]);

    return;
}

void print_path(int a, int b)
{
    while (a!=0 && b!=0)
    {
        printf("c[%d][%d]=%dn", a, b, c[a][b]);
        if (s[a][b]==1)
        {
            a--;
            b--;
        }
        else if (s[a][b]==2)
            a--;
        else
            b--;

        if(a==0 || b==0)
        {
            printf("c[%d][%d]=%dn", a, b, c[a][b]);
            break;
        }
    }
}
int main()
{
    lcs_length(7, 6);
    print_path(7, 6);

    return 0;
}

1.只用2Xmin(m,n)个表项来替代c[ ][ ]的版本。

2.只用min(m,n)个表项来替代c[ ][ ]的版本。

以上两个优化比较简单

参考文章:
O(nlogn) Clean and easy Java DP Binary Search solution with detailed explanation

 

2.矩阵链乘法

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/06.
//  Copyright © 2015年 YangKi. All rights reserved.


#include <cstdio>
#include <iostream>

using namespace std;

int p[7]={30, 35, 15, 5, 10, 20, 25};// 代表矩阵30X35,35X15....

int m[7][7];//m[i,j]表示矩阵链i...j最小的乘法次数

int s[7][7];//记录具体怎么安排

void print(int i, int j)//打印矩阵链i...j的括号分配
{
    if(i==j) printf("A_%d", i);
    else
    {
        printf("(");
        print(i, s[i][j]);
        print(s[i][j] 1, j);
        printf(")");
    }
}

int main()
{
    int i=1;
    while (i<7)
    {
        m[i][i]=0;
        i  ;
    }

    for (int i=1; i<=5; i  )// 一共进行i-1次
    {
        for (int j=1; (j i) <= 6; j  )
        {
            //m[j][j i]-->m[a][b]
            int q=INT_MAX;
            int a=j;
            int b=j i;
            for (int k=a; k<b; k  )
            {
                int temp=m[a][k]   m[k 1][b]   p[a-1]*p[k]*p[b];
                if(temp<q)
                {
                    q=temp;
                    s[a][b]=k;
                }
            }
            m[a][b]=q;
        }
    }

    for (int i=1; i<=6; i  )
    {
        for (int j=1; j<=6; j  )
        {
            if(i<j)
            {
                printf("m[%d][%d]=d   ", i, j, m[i][j]);
            }
        }
        printf("n");
    }

    print(1, 6);

    return 0;
}

代码如下:

 1 let arr = [3,2,1,14,5,5,8,1,2,3,4,5,6,76,7,1,2,9];
 2 
 3 function fn(arr){
 4     let temp = [];
 5     let sub = [];
 6     for ( let i = 0; i < arr.length; i   ){
 7         if(arr[i] 1 === arr[i 1]){
 8             temp.push(arr[i]);
 9         }else{
10             if(temp.length!=0){
11                 let temp1 = [];
12                 temp.push(arr[i]);
13                 
14                 for( let i = 0 ; i < temp.length; i  ){
15                     temp1.push(temp[i])
16                 }
17                 
18                 if(sub.length===0||sub.length<temp1.length){
19                     sub = temp1
20                 }
21                 temp = [];
22             }
23         }
24     }
25     return sub;
26 }
27 let arr1 = fn(arr);
28 console.log(arr1);

5.最优二叉搜索树

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/10.
//  Copyright © 2015年 YangKi. All rights reserved.

#include <cstdio>
#include <iostream>
#define keyNum 5 //the num of key
using namespace std;

double p[keyNum 1]={-1, 0.15, 0.1, 0.05, 0.1, 0.2};   // p1, ..., pn
double q[keyNum 1]={0.05, 0.1, 0.05, 0.05, 0.05, 0.1};// q0, q1, ..., qn
double e[keyNum 2][keyNum 2];
double w[keyNum 2][keyNum 2];
int root[keyNum 2][keyNum 2];

void optimal_bst()
{
    for (int i=0; i <= keyNum; i  )
    {
        e[i 1][i] = q[i];
        w[i 1][i] = q[i];
    }

    for (int i=1; i <= keyNum; i  )
    {
        for (int j=1; (i j) <= keyNum 1; j  )
        {
            w[j][i j-1] = w[j][i j-1-1]   p[i j-1]   q[i j-1];
            e[j][i j-1] = 100.0;//e[j][i j], 正无穷大
            for (int r=j; r <= (i j-1); r  )
            {
                double temp = e[j][r-1]   e[r 1][i j-1]   w[j][i j-1];
                if (temp < e[j][i j-1])
                {
                    e[j][i j-1] = temp;
                    root[j][i j-1]=r;
                }
            }
        }
    }
    return;
}

void PRINT_OPTIMAL_BST(int i,int j)
{
    int Root = root[i][j];//当前根结点
    if (i==1 && j==keyNum)
        printf("k_%d为根n", Root);
    if (i==Root)
    {//如果左子树是叶子
        printf("d_%d为k_%d的左子树n", i-1, Root);
    }
    else
    {
        printf("k_%d为k_%d的左子树n", root[i][Root-1], Root);
        PRINT_OPTIMAL_BST(i,Root-1);
    }
    if (j==Root)
    {//如果右子树是叶子
        printf("d_%d为k_%d的右子树n", j, Root);
    }
    else
    {
        printf("k_%d为k_%d的右子树n", root[Root 1][j], Root);
        PRINT_OPTIMAL_BST(Root 1,j);
    }
}

int main()
{
    optimal_bst();

    PRINT_OPTIMAL_BST(1, 5);

    return 0;
}
public int lengthOfLIS(int[] nums) {
        if(nums == null || nums.length ==0) return 0;

       int [] dp = new int[nums.length];
        dp[0] = 1;
        int lenght = 1;
        for (int i = 1; i <nums.length ; i  ) {
            for (int j = i-1; j >= 0 ; j--) {
                if(nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i],dp[j] 1);
                }
            }
            dp[i] = Math.max(dp[i],1);
            lenght = Math.max(lenght,dp[i]);
        }

        return lenght;
    }

在一个无序整数数组中,找出连续增长片段最长的一段, 增长步长是1。Example: [3,2,4,5,6,1,9], 最长的是[4,5,6]

1.钢条切割

//
//  main.cpp
//  pearls
//
//  Created by YangKi on 16/03/06.
//  Copyright © 2015年 YangKi. All rights reserved.


#include <cstdio>
#include <iostream>

using namespace std;

int price[11]={-1,1,5,8,9, 10,17,17,20, 24,30};

int r[11];//r[i] 表示长度为i的钢条的最大收益

int max(int a, int b)
{
    return a>b? a:b;
}
///////////////////////////////////////////////////////////没有用动态规划的版本
int cut_1(int *p, int length)//计算长度为length的钢条的最大收益
{
    if(length == 0) return 0;
    int q=-1;
    for (int i=1; i <= length; i  )
    {
        q=max(q, p[i] cut_1(p, length-i) );
    }
    return q;
}

///////////////////////////////////////////////////////////自底向上的dp
int cut_2(int *p, int length)
{
    for (int i=0; i < 11; i  )
    {
        r[i]=-1;
    }
    r[0]=0;

    for (int i=1; i<11; i  )
    {
        int q=-1;
        for (int j=1; j<=i; j  )
        {
            q=max(q, p[j]   r[i-j]);
        }
        r[i] = q;
    }
    return r[length];
}
///////////////////////////////////////////////////////////增加切割成本cost,课后第三题,自底向上的dp
int cut_3(int *p, int length, int cost)
{
    for (int i=0; i < 11; i  )
    {
        r[i]=-1;
    }
    r[0]=0;

    for (int i=1; i<11; i  )
    {
        int q=-1;
        for (int j=1; j<i; j  )
        {
            q=max(q, p[j]   r[i-j] - cost);
        }

        q=max(q, p[i]);//不剪的情况
        r[i] = q;
    }
    return r[length];
}


int main()
{
    int i=0;
    while (i<12)
    {
        r[i  ]=-1;
    }

    printf("maxr: %dn", cut_3(price, 10, 1));

    return 0;
}

题目要求:
Given an unsorted array of integers, find the length of longest increasing subsequence.

解题思路:
首先想到用动态规划解决该问题,维护数组 dp , dp[i] 表示以第i个元素为结尾的增长序列的长度,则递归式为:
dp[i]= Math.max( dp[j] 1 ,1) 其中 j < i && nums[j] < nums[i]

后来发现有更巧妙的解题方法,时间复杂度减少到 nlog(n),在此做下笔记:
维护一个整数 len 代表当前最长增长序列的长度,一个数组 dp , 数组内维护着当前最长增长序列的最小序列,尽管从原序列顺序看来,它完全不符合,但这丝毫不影响结果。比如:
nums [ 1,4,3,8,2,10]
正常的增长序列为: [1,4,8,10] 或 [1,3,8,10]
而dp 中的序列为:[1,2,8,10]

Your algorithm should run in O(n2) complexity.

public int lengthOfLIS(int[] nums) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int len = 0;
    for(int i = 1; i < nums.length; i  ) {
        if(nums[i] > dp[len]) {
            dp[  len] = nums[i];
        }
        else {
            int index = search(dp, len, nums[i]);
            dp[index] = nums[i];
        }
    }
    return len   1;
}

private int search(int[] dp, int len, int val) {
    int start = 0;
    while(start <= len) {
        int mid = start   (len - start) / 2;
        if(dp[mid] == val) {
            return mid;
        }
        else if(dp[mid] < val) {
            start = mid   1;
        }
        else {
            len = mid - 1;
        }
    }
    return start;
}

参考代码如下:

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

本文由时时app平台注册网站发布于web前端,转载请注明出处:在贰个冬辰整数数组中,找寻接二连三进步部分

关键词: