Ամենաերկար աճող հաջորդական հետևանքները


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Google Microsoft
Դասավորություն Դինամիկ ծրագրավորում

Հետևանքները հարցազրույց վարողների կողմից սիրված մեկ այլ թեմա է: Նրանց շուրջ փոփոխությունները միշտ կարող են նրանց նոր հնարավորություններ տալ թեկնածուների թեստավորման համար: Այն կարող է ստուգել թեկնածուի կարողությունները մտածելու և վերլուծելու իր կարողությունները և գտնելու լավագույն և օպտիմալ լուծումները: Այսօր մենք լուծում ենք հետևյալ խնդրի լուծումը, որը կկատարի նույն «Ամենաերկար աճող հաջորդական հետևանքները»:

Խնդիրի հայտարարություն

Նախ եկեք տեսնենք, թե ինչ խնդիր է պետք փոխանցել: Մեզ տրված է ամբողջ թվերի զանգված: Այս զանգվածը տեսակավորված չէ: Մեր խնդիրն է պարզել աճող ամենամեծ ենթաբազմությունը: Կանոնն ասում է, որ այդ ամբողջ թվերը պետք է ունենան մեկի միջև տարբերություն:

Օրինակ

6, 7, 2, 3, 4, 5, 9, 10

Հնարավոր ենթաբազմություն

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

Որպես պատկեր ՝ արժե հազար բառ: Եկեք նայենք նույնը պատկերող պատկերին: Պատկերում կարմիր շրջանը ցույց է տալիս իրավասու ենթաբազմությունը:

Ամենաերկար աճող հաջորդական հետևանքները

Մոտեցում LICS- ի երկարությանը

Այս խնդիրը լուծելու մի քանի մեթոդներ կան ՝ սկսած կոպիտ ուժից մինչև ԴP: Երբ այդպիսի հարցեր են տրվում, մենք հակված ենք գնալու ավելի հեշտ ճանապարհով և նայելու դեպի Brute Force: Բայց մի անհանգստացեք: Ես այստեղ եմ, որպեսզի փրկեմ ձեզ ամոթը լավագույն լուծմամբ:

  • Նախ, մենք ստեղծում ենք HashMap
  • Այս HashMap- ը պահպանում է մեր ունեցած ենթահողերի երկարությունը
  • Այս HashMap- ի բանալին համարն է:
  • Արժեքը դրա հետ կապված հաջորդականության երկարությունն է:
  • Երկրորդ, մենք կրկնում ենք զանգվածի միջոցով
  • Ստուգում ենք arr [i] -1:
  • Եթե ​​HashMap- ն ունի բանալին, մենք ավելացնում ենք հաջորդականությանը
  • Մենք կարող ենք ջնջել նախորդ բանալին `մեր հարմարության համար և տարածք պահելու համար
  • Եթե ​​HashMap- ը չունի բանալին
  • Մենք որպես ընթացիկ տարրի բանալին ավելացնում ենք 1-ը
  • Վերջապես, մենք գտնում ենք ամբողջ երկարության առավելագույնը
  • Այսպիսով, մենք ունենք ԼԻSԵՐԸ հիմա:

Կոդ

Հիմա, երբ մենք հասկացանք, թե ինչպես են լուծում այս խնդիրը: Նախ եկեք մեր գաղափարները կոդավորենք Java կոդով:

Java կոդ ՝ հետևողական հետևանքների ամենաերկար աճող տևողությունը գտնելու համար

import java.util.*;
public class Main
{
    public static int LICS(int[] arr)
    {
        HashMap<Integer,Integer>hash=new HashMap<Integer,Integer>();
        for(int i=0;i<arr.length;i++)
        {
            if(hash.containsKey(arr[i]-1))
            {
                hash.put(arr[i],hash.get(arr[i]-1)+1);
                hash.remove(arr[i]-1);
            }
            else
                hash.put(arr[i],1);
        }
        return Collections.max(hash.values());
    }
    public static void main(String args[]) 
    { 
        int arr[]={3, 10, 3, 11, 4, 5, 6, 7, 8, 12};
        System.out.println(LICS(arr));
    }
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

Քանի որ մենք Java- ից անցնում ենք C ++: Մենք հավաքագրման շրջանակից անցնում ենք STL: Այսպիսով, մենք անցնում ենք դեպի չպատվիրված քարտեզներ - ից HashMap, Այժմ, երբ մենք գիտենք փոփոխությունները, թույլ տվեք փոխել լեզուն:

C ++ կոդ ՝ հաջորդական հաջորդականության ամենաերկար աճող տևողությունը գտնելու համար

#include<bits/stdc++.h>
using namespace std;
int maxs(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
}
int LICS(int arr[],int n)
{
    unordered_map<int,int>store;
    int max=-1;
    for(int i=0;i<n;i++)
    {
        if(store.find(arr[i]-1)!=store.end())
        {
            store[arr[i]]=store[arr[i]-1]+1;
        }
        else
            store[arr[i]]=1;
        max=maxs(max,store[arr[i]]);
    }
    return max;
}
int main()
{
    int a[] = { 3, 10, 3, 11, 4, 5, 6, 7, 8, 12 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    cout << LICS(a, n); 
    return 0; 
}
3, 10, 3, 11, 4, 5, 6, 7, 8, 12
6

Բարդության վերլուծություն

Timeամանակի բարդություն = O (N)

  • Մենք շրջում ենք ամբողջ զանգվածով
  • Մենք միանգամից դիտարկում ենք մեկ տարր
  • Այսպիսով, ժամանակի բարդությունը O (N) է

Տիեզերական բարդություն = O (N)

  • Մենք բանալիները դնում ենք որպես թվեր
  • Նույնիսկ ստեղները հանելու դեպքում, լավագույն դեպքում, կարող է լինել միայն մեկ բանալի
  • Այնուամենայնիվ, ավելի վատ դեպքում, մենք կարող է ի վերջո ավելացնել բոլոր տարրերը HashMap- ին
  • Ինչը հանգեցնում է O (N) տիեզերական բարդության