લાંબી વધતી સતત અનુગામી


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન Google માઈક્રોસોફ્ટ
અરે ડાયનેમિક પ્રોગ્રામિંગ

સબક્ક્વેન્સ એ એક અન્ય વિષય છે જેનો ઇન્ટરવ્યુ લેનારાઓ દ્વારા પ્રિય છે. તેમને ફરતે ટ્વીક કરવાથી ઉમેદવારોની ચકાસણી માટે હંમેશા નવી તકો મળી શકે છે. તે વસ્તુઓની વિચારણા અને વિશ્લેષણ કરવાની અને શ્રેષ્ઠ અને શ્રેષ્ઠ ઉકેલો સાથે ઉમેદવારની ક્ષમતા ચકાસી શકે છે. આજે આપણે એક અનુગામી સમસ્યા હલ કરી રહ્યા છીએ જે સમાન “લાંબી વધતી જતી સતત અનુગામી” કરશે.

સમસ્યા નિવેદન

સૌથી પહેલાં ચાલો જોઈએ કે સમસ્યા શું અભિવ્યક્ત કરે છે. આપણને પૂર્ણાંકોની એરે આપવામાં આવે છે. આ એરે સ unsર્ટ કરેલું છે. અમારું કાર્ય એ સૌથી મોટા સબસેટને શોધવાનું છે જે વધી રહ્યું છે. નિયમ જણાવે છે કે આ પૂર્ણાંકો વચ્ચે તેમની વચ્ચેનો તફાવત હોવો જોઈએ.

ઉદાહરણ

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

શક્ય ઉપગણો

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

એક છબી હજાર શબ્દોની કિંમત તરીકે. ચાલો તે જ ચિત્રણ કરતી એક છબી જોઈએ. છબીમાં લાલ પ્રદેશ લાયક સબસેટ બતાવે છે.

લાંબી વધતી સતત અનુગામી

એલઆઈસીએસ લંબાઈ માટે અભિગમ

બ્રુટ ફોર્સથી લઈને ડીપી સુધીની આ સમસ્યા હલ કરવાની ઘણી પદ્ધતિઓ છે. જ્યારે પણ આવા પ્રશ્નો પૂછવામાં આવે છે ત્યારે આપણે વધુ સહેલો રસ્તો લઈ બ્રુટ ફોર્સ પર ધ્યાન આપીએ છીએ. પણ કાઇ ચિંતા કરો નહી. હું શ્રેષ્ઠ સમાધાન સાથે તમને મૂંઝવણને બચાવવા માટે અહીં છું.

  • પ્રથમ, અમે એક બનાવીએ છીએ હેશમેપ
  • આ હેશમેપ આપણી પાસેના પેટા ભાગની લંબાઈને સંગ્રહિત કરે છે
  • આ હેશમેપમાં કી એ નંબર છે.
  • મૂલ્ય તેની સાથે સંકળાયેલ અનુગામીની લંબાઈ છે.
  • બીજું, આપણે એરે દ્વારા ફરી વળવું
  • અમે એઆરઆર માટે તપાસ કરીએ છીએ [i] -1.
  • જો હેશમેપ પાસે ચાવી છે અમે અનુગામીમાં ઉમેરીએ છીએ
  • આપણે આપણી સગવડ માટે અને જગ્યા સ્ટોર કરવા માટે અગાઉની કી કા canી શકીએ છીએ
  • જો હેશમેપમાં કી નથી
  • અમે વર્તમાન તત્વની ચાવી તરીકે 1 ઉમેરીએ છીએ
  • છેલ્લે, અમને મહત્તમ લંબાઈ મળે છે
  • આમ, અમારી પાસે હવે એલઆઈસીએસ છે!

કોડ

હવે આપણે સમજી ગયા છે કે આ સમસ્યા કેવી રીતે હલ કરવામાં આવે છે. પહેલા જાવા કોડવાળા કોડ પર અમારા વિચારો મૂકીએ.

લાંબી વધતી સતત અનુગામી લંબાઈ શોધવા માટે જાવા કોડ

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

આપણે જાવાથી સી ++ પર સ્વિચ કરી રહ્યા છીએ. અમે કલેક્શન ફ્રેમવર્કથી એસટીએલમાં ફેરવી રહ્યા છીએ. આમ, આપણે સ્થાનાંતરિત થઈ રહ્યા છીએ અનર્ડર્ડ નકશા થી હેશમેપ. હવે જ્યારે આપણે ફેરફારો જાણીએ તો ચાલો આપણે ભાષા બદલીએ.

લાંબી વધતી જતી સતત અનુગામી લંબાઈ શોધવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા = ઓ (એન)

  • આપણે આખા એરેમાંથી લૂપ લગાવીએ છીએ
  • અમે એક સમયે એક તત્વ પર વિચારણા કરી રહ્યા છીએ
  • આમ, સમય જટિલતા ઓ (એન) છે

અવકાશ જટિલતા = O (N)

  • આપણે નંબરો તરીકે ચાવી મૂકીએ છીએ
  • ચાવીઓ દૂર કરવા પર પણ, શ્રેષ્ઠ કિસ્સામાં, ત્યાં ફક્ત એક કી હોઈ શકે છે
  • જો કે, ખરાબ કિસ્સામાં, આપણે હેશમેપમાં બધા તત્વો ઉમેરવાનું સમાપ્ત કરીશું
  • જે ઓ (એન) ની અવકાશ જટિલતા તરફ દોરી જાય છે