وڏا لڳاتار وڌندڙ جلوس


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon گوگل Microsoft جي
ڪيريو متحرڪ پروگرامنگ

بعد ۾ هڪ ٻيو موضوع آهي انٽرويو ڪندڙن سان پيار. اُنهن کي چوڌاري ڇڪڻ به هميشه انهن اميدوارن جي جانچ لاءِ نوان موقعا ڏئي سگهي ٿو. اهو اميدوارن جي سوچڻ ۽ تجزيو ڪرڻ جي صلاحيت کي جانچ ڪري سگهي ٿو ۽ بهترين ۽ بهترين حل سان گڏ اچي سگھي ٿو. اسان ا we هڪ بعد واري مسئلي کي حل ڪري رهيا آهيون جيڪا ساڳي ئي ڊگهي عرصي تائين جاري رهندي.

مسئلي جو بيان

سڀ کان پهريان اسان کي ڏسڻو آهي ته مسئلو ڇا ٻڌائڻ آهي. اسان کي انٽيگرز جي هڪ قطار ڏني وئي آهي. ھي قطعو بند ٿيل آھي. اسان جو ڪم اهو آهي ته گهڻي کان وڏي سبسٽ ڳولهڻ جو جيڪو وڌي رهيو آهي. قاعدو بيان ڪري رهيو آهي ته اهي انٽيگرز انهن جي وچ ۾ هڪ فرق هجڻ گهرجي.

مثال

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

ممڪن سبسڪيٽ

6,7

2,3,4,5

9,10

Length of Longest Increasing Subsequence: 4

جئين تصوير هڪ هزار لفظن جي قيمت آهي. اچو ته هڪ تصوير ڏسون جيڪو ساڳئي نموني بيان ٿئي. تصوير ۾ ڳاڙهي علائقو قابل ذيلي حصو ڏيکاريندو آهي.

وڏا لڳاتار وڌندڙ جلوس

ايل آءِ ايس ايس جي ڊيگهه لاءِ رستو

هن مسئلي کي حل ڪرڻ جا ڪيترائي طريقا آهن بروٽي فورس کان وٺي ڊي پي تائين. جڏهن به اهڙا سوال پڇيا ويندا آهن ته اسان آسان رستو اختيار ڪندا آهيون ۽ بروٽس فورس ۾ نظر اينداسين. پر ، فڪر نه ڪريو. آئون بهتر حل سان توهان جي شرمندگي بچائڻ لاءِ هتي آيو آهيان.

  • پهرين ، اسان هڪ ٺاهيندا آهيون هش ميپ
  • هي هشميپ اسان جي جيڪو بعد جي شروعات ڪري ٿو ان جي ڊيگهه آهي
  • هن هش ايمپ ۾ اهم نمبر آهي.
  • ويليو انهي سان تعلق رکندڙ جي ڊيگهه آهي.
  • ٻيو ، اسين صف ذريعي آتش ڪريون ٿا
  • اسين arr [i] -1 لاءِ چڪاس ڪيون ٿا.
  • جيڪڏهن هشميپ ڪيچ آهي جنهن کي اسين پهرين ۾ شامل ڪريون ٿا
  • اسان پنهنجي سهولت ۽ جڳهه کي ذخيرو ڪرڻ لاءِ پوئين ڪن کي حذف ڪري سگهون ٿا
  • جيڪڏھن ھاش ميپ جي چاٻي ناھي
  • اسان 1 کي موجوده عنصر جي چاٻي طور شامل ڪريون ٿا
  • آخر ۾ ، اسان سڀني جي وڌ کان وڌ ڳولهي لڌو
  • ان ڪري ، اسان وٽ هاڻي LICS آهن!

ڪوڊ

ھاڻي اسان سمجھيو آھي ته ھي مسئلو ڪيئن حل ڪري رھيا آھن. پهرين اسان کي پنهنجن خيالن جاوا ڪوڊ سان ترتيب ڏيڻ ڏيو.

جاوا ڪوڊ ڳولڻ لاءِ لڳاتار وڌندڙ لڳاتار اڳيان واري ويڙهه جي ڊيگهه

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

جئين اسان جاوا کان سي ++ ڏانهن تبديل ٿي رهيا آهيون. اسان ڪليڪشن فريم ورڪ کان ايس ٽي ايل ۾ تبديل ڪري رهيا آهيون. ان ڪري ، اسان کي منتقلي ڪري رهيا آهيون بي ترتيب نقشي کان هش ميپ. ھاڻي اسان knowاڻون ٿا ته تبديليون اچو اسان ٻولي کي ھلائڻ ڏيو.

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

پيچيدگي تجزيي

وقت جي پيچيدگي = اي (ن)

  • اسان س arrayي ترتيب ذريعي لوپ ڪيو
  • اسان هڪ وقت تي هڪ عنصر سمجهي رهيا آهيون
  • ان ڪري ، وقت جي پيچيدگي O (N)

خلائي ڪمپليڪس = اي (اين)

  • اسان انگن وانگر ڪنجيون وجھي رهيا آهيون
  • جيتوڻيڪ چابين کي ڪ onڻ تي ، بهترين صورت ۾ ، صرف هڪ اهم ٿي سگهي ٿو
  • تنهن هوندي ، بدترين صورت ۾ ، اسان شايد هٽائي ميپ ۾ سڀني عنصرن کي شامل ڪري ڇڏينداسين
  • جيڪو او (ن) کي خلائي پيچيدگي ڏياري ٿو.