Ən uzun artan nəticələr

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon Citrix Kod milləti Facebook google microsoft Samsung Zoho
İkili axtarış Dinamik proqramlaşdırma LİSBaxılıb 90

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Biz ilə təmin olunur array çeşidlənməmiş tam ədədi və ən uzun artan ardıcıllığı tapmalıyıq.

  • Ardıcıllığın ardıcıl olmasına ehtiyac yoxdur
  • Növbəti artmaqdadır

Bunu bir neçə nümunə ilə daha yaxşı başa düşək.

misal

Input

[9, 2, 5, 3, 7, 10, 8]

Buraxılış

4

Izahat

Ən uzun artan ardıcıllıq [2,3,7,10].

Yanaşma 1: Brute Force

Bu yanaşma bütün mümkün alt qruplara baxmağı və təbiətdə artan ən uzun ardıcıllığı tapmaqdan ibarətdir.

İndi, hər dəfə bir sıra içindəki tam ədədi ziyarət etdikdə iki hal ola bilər.

  • Ya alt sıraya daxil edilə bilər, yəni əvvəlki elementdən daha böyükdür
  • Əvvəlki elementdən daha kiçikdir və sonrakı hissəyə daxil edilə bilməz

Ancaq elementi müəyyən bir mövqeyə daxil edib etməməyimizdən asılı olmayaraq, müəyyən bir uzunluğun həmin nöqtəyə qədər artan bir ardıcıllığı mövcuddur və çəkilən maksimum uzunluğu o zamana qədər qaytara bilərik. Bunu kod parçası ilə daha yaxşı başa düşək (Java və C ++ dilində)

Ən Uzun Artan Nəticə üçün Java Proqramı

class Solution 
{
    public int helper(int[] nums,int prev,int cur)
    {
        if(cur==nums.length)
            return 0;
        int on_include=0;
        //If the element at current index is greater than 
        //previous element we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(Math.max(on_include,on_ignore));
    }
    public int lengthOfLIS(int[] nums) 
    {
        int max=helper(nums,Integer.MIN_VALUE,0);
        return max;
    }
}

Ən uzun artan nəticələr üçün C ++ proqramı

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int helper(vector<int> nums,int prev,int cur)
    {
        if(cur==nums.size())
            return 0;
        int on_include=0;
        //If we are greater than previous length we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(max(on_include,on_ignore));
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
     int max=helper(nums,-1,0);
        return max;    
    }
};

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2), burada N massivin ölçüsüdür. Burada bizi O (N * N) zaman mürəkkəbliyinə aparan döngələr üçün iki işləyirik.

Kosmik Mürəkkəblik

O (1), çünki bizi daimi kosmik c0mpleksliyə aparan bəzi dəyişənlərdən istifadə edirik.

Yanaşma 2: Dinamik proqramlaşdırma

[9, 2, 5, 3, 7, 10, 8, 7] üçün ən uzun artan ardıcıllığı tapaq.

  • Tamsayı massivinin ölçüsündə bir sıra yaradaq
  • Hər bir element ən azı bir uzunluğun bir ardıcıllığıdır, yəni rəqəmlərin özləri beləliklə massivi bir başlanğıc halına gətirirlər.
    1 1 1 1 1 1 1 1
  • Hər bir ith mövqeyi üçün ondan əvvəl j vəziyyətinə baxırıq
  • Bir [j]
  • İ = 2 üçün i = 0 və i = 1-ə eyni şəkildə baxırıq. Əməliyyatlardan sonra dəyişdirilmiş massivə baxaq
    1 1 Maksimum (j + 1, i)

    (2)

    1 1 1 1 1
  • Bütün müqayisələrdən sonra son sıra aşağıdakı kimi nəzərdən keçirilə bilər:
    1 1 2 2 3 4 4 3
  • Bütün rəqəmlərdən maksimumunu taparaq maksimum ardıcıllığın uzunluğunu 4-ə bərabər tapırıq. Bunu kodla daha yaxşı başa düşək.

Ən Uzun Artan Nəticə üçün Java Proqramı

class Solution 
{
    public int lengthOfLIS(int[] nums) 
    {
        int ans[]=new int[nums.length];
        for(int i=0;i<ans.length;i++)
            ans[i]=1;
        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=Math.max(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<ans.length;i++)
        {
            max=Math.max(ans[i],max);
        }
        return max;
    }
}

Ən uzun artan nəticələr üçün C ++ proqramı

class Solution 
{
public:
    int cmax(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
    int ans[nums.size()];
    int i,j;
        for(i=0;i<nums.size();i++)
            ans[i]=1;
        for(i=1;i<nums.size();i++)
        {
            for(j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=cmax(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            max=cmax(ans[i],max);
        }
        return max; 
    }
};

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

Yuxarıda göstərilən həllin zaman mürəkkəbliyi O (n ^ 2) -dir.

Kosmik Mürəkkəblik

O (n), çünki hər indeksdən sonra cavabı saxlamaq üçün bir sıra istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »