Pascal's Triangle II Leetcode լուծում


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

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

Այս խնդրում մեզ տրվել է Պասկալ եռանկյունու տողի ցուցիչ (i): Մենք պետք է ստեղծենք մի գծային զանգված, որը պարունակի ith շարքի արժեքները և վերադարձնել այն: Տողի ինդեքսը սկսվում է 0-ից:
Մենք գիտենք, որ Պասկալի եռանկյունին այն եռանկյունին է, որտեղ յուրաքանչյուր թիվ երկու իրարից անմիջապես վեր գտնվող երկու թվերի հանրագումարն է:

Pascal's Triangle II Leetcode լուծում

Օրինակ

rowIndex = 3
[1,3,3,1]
rowIndex = 0
[1]

Ինչպես գիտենք, որ պասկալի եռանկյունու յուրաքանչյուր արժեքը երկիշխանության գործակից է (nCr), որտեղ n շարքն է, իսկ r- ը ՝ այդ արժեքի սյունակի ցուցիչը:

Մենք քննարկել ենք նմանատիպ խնդիր, երբ մենք պետք է բոլոր տողերը վերադարձնենք տողի ցուցիչ 0-ից այստեղ Պասկալի եռանկյունու տողի այս ցուցիչին - Pascal եռանկյունու Leetcode

Բայց այս խնդրում մենք միայն պետք է վերադարձնենք մեկ տող, որի ինդեքսը տրված է:
Այստեղ մենք կքննարկենք այս խնդրի լուծման երեք մոտեցում.

Մոտեցում 1 (Brute Force Recursion)

Մենք գիտենք, որ այս եռանկյունու յուրաքանչյուր թիվ ուղղակիորեն վերևում գտնվող երկու թվերի հանրագումար է: այսինքն ՝
Num (տող, սյուն) = Num (տող -1, սյուն) + Num (տող -1, սյուն 1):
Այսպիսով, մենք կարող ենք բազմիցս զանգահարել գործառույթ Num (rowIndex, j) այդ շարքի յուրաքանչյուր սյունակի ինդեքսի համար և վերադարձնել ձևավորված ցուցակը:

Ինչպես տեսնում ենք, Num (i, j) գտնելու համար մենք ձևակերպել ենք ռեկուրսիվ մոտեցում: Այժմ դրա համար կան բազային դեպքեր, որոնք են.

  • Առաջին շարքի արժեքը կլինի 1. Այսպիսով, տողի համար = 0, Num (տող,…) = 0:
  • Առաջին սյունակի արժեքը կլինի 1. Այսպիսով, col = 0, Num (…, col) = 0 համար:
  • Յուրաքանչյուր տողի վերջին արժեքը հավասար կլինի 1. Այսպիսով, col = row = k, Num (k, k) = 0 համար:

Իրականացում Pascal's Triangle II Leetcode Solution- ի համար

C ++ ծրագիր

#include <bits/stdc++.h>
using namespace std;

int nCr(int n,int r)
{
    if(n==0 || r==0 || r==n)
        return 1;

    return nCr(n-1,r-1)+ nCr(n-1,r);
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Java ծրագիր

import java.util.*;

class Rextester{
    
    static int nCr(int n,int r)
    {
        if(n==0 || r==0 || r==n)
            return 1;

        return nCr(n-1,r-1)+ nCr(n-1,r);
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Բարդության վերլուծություն Pascal's Triangle II Leetcode լուծման համար

Timeամանակի բարդություն

O (2 ^ k): որտեղ k- ը տրված Տողի ինդեքսն է:
Մենք կոչում ենք Num (i, j) ռեկուրսիան որպես Num (i-1, j) + Num (i-1, j-1): Ուստի Num (n, r) գտնելու ժամանակը կլինի nCr:
Մենք կոչում ենք այս ռեկուրսիվ գործառույթը տրված տողի (k) .ie բոլոր սյունակների ցուցիչի համար
kC0 + kC1 + kC2 +: + kCk = 2 ^ k:
Ուստի ընդհանուր ժամանակի բարդությունը կլինի O (2 ^ k):

Տիեզերական բարդություն 

Լավ): Մեզ պետք է O (k) տարածք ՝ տրված տողի բոլոր արժեքները ցուցակում պահելու համար: Նաև ամենավատ դեպքում մեր ռեկուրսիան կպահանջի O (k) stack տարածք ռեկուրսիվ զանգի համար: Ուստի O (k) + O (k) = ~ O (k):

Մոտեցում 2 (Դինամիկ ծրագրավորում)

Վերոնշյալ հետադարձում մենք կարող ենք տեսնել, որ մենք միանգամից կանչում ենք Num (i, j) ֆունկցիան նույնի համար (i, j):

Այսպիսով, այն, ինչ կարող ենք անել, այն է, որ մենք կարողանանք անգիր հիշել յուրաքանչյուրի համար (i, j) այնպես, որ երբ որևէ անգամ այդ գործառույթը կանչելու անհրաժեշտություն լինի, մենք վերադարձնենք պահված պատասխանը ուղղակիորեն հիշողությունից ՝ առանց կրկին հաշվարկելու: Այսպիսով խնայելով շատ ժամանակ:
Պատասխանները դինամիկ պահելու համար կարող ենք օգտագործել հեշ քարտեզ որտեղ առանցքային կլինի տողի ինդեքսի և սյունակի ինդեքսի համադրությունը:

Մեկ այլ բան, որ կարող ենք տեսնել այստեղ, այն է, որ մեզ անհրաժեշտ են միայն նախորդ շարքի արժեքներ `ընթացիկ շարքի արժեքները գտնելու համար: Հետևաբար, մենք կարող ենք միաժամանակ պահել միայն մեկ տողի արժեքներ և այն օգտագործել հաջորդ շարքի արժեքները գտնելու համար: Հետևաբար, մենք կարող ենք այստեղ տիեզերական բարդությունը հասցնել O (k):

Տիեզերքի օպտիմիզացված ալգորիթմ.
1. Ստեղծեք համապատասխանաբար նախորդ և ընթացիկ տողերի համար երկու զանգված:
2. Նախնական նկարագրում Նախորդ տող որպես {1}:
3. Գործարկել մի օղակ ith շարքի համար i = 1-ից i =rowIndex, Եվ նախորդ շարքից առաջացրեք շարքի նոր արժեքներ և պահեք այն ներսում curr զանգված
4. Այժմ թարմացրեք Նախորդ տող նշանակելով զ տող դեպի Նախորդ շարքով և կրկնել նույն գործընթացը այս օղակում:
5. Վերադարձրեք ներսում պահված վերջին շարքը Նախորդ զանգված

Իրականացում Pascal's Triangle II Leetcode Solution- ի համար

C ++ ծրագիր ՝ օգտագործելով հիշողությունը

#include <bits/stdc++.h>
using namespace std;

unordered_map<string,int> cache;

int nCr(int n,int r)
{
    string key= to_string(n)+to_string(r);
    if(cache.count(key)) return cache[key]; 

    if(n==0 || r==0 || r==n)
        return 1;

    return ( cache[key]= nCr(n-1,r-1)+ nCr(n-1,r) );
}


vector<int> getRow(int rowIndex) 
{
    vector<int> res(rowIndex+1);

    for(int i=0;i<=rowIndex;i++)
        res[i]= nCr(rowIndex,i);

    return res;

}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}

C ++ ծրագիր (տարածքի օպտիմիզացված DP)

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Java ծրագիր ՝ օգտագործելով հիշողությունը

import java.util.*;

class Rextester{
    
    static Map<String,Integer> cache=new HashMap<String,Integer>();
    
    static int nCr(int n,int r)
    {
        String key= "" + n + r;
        if(cache.containsKey(key)) return cache.get(key); 
        
        if(n==0 || r==0 || r==n)
            return 1;
        
        int ans= nCr(n-1,r-1)+ nCr(n-1,r);
        cache.put(key,ans);
        return ans;
    }

    public static List<Integer> getRow(int rowIndex) 
    {
       List<Integer> res=new ArrayList<Integer>();
        for(int i=0;i<=rowIndex;i++)
            res.add(nCr(rowIndex,i));

        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}

Java ծրագիր (տարածքի օպտիմիզացված DP)

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    vector<int> prev={1},curr;
    for(int i=1;i<=rowIndex;i++)
    {
        curr.clear();
        curr.resize(i+1,1);

        for(int j=1;j<i;j++)
            curr[j]=prev[j]+prev[j-1];

        prev=curr;
    }

    return prev;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Բարդության վերլուծություն Pascal's Triangle II Leetcode լուծման համար

Timeամանակի բարդություն

Ո (կ ^ 2):  Հիշատակումը համոզվելու է, որ որոշակի տարրը հաշվարկվում է միայն մեկ անգամ: Ենթադրելով, որ hash քարտեզից ans վերցնելու համար պահանջվում է անընդհատ ժամանակ, ապա Pascal- ի եռանկյան յուրաքանչյուր արժեքը հաշվարկելու համար անհրաժեշտ է անընդհատ ժամանակ:
Այժմ մենք ի վերջո հաշվարկում ենք 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 արժեքներ, որը = ~ O (k ^ 2):

Տիեզերական բարդություն 

1. Պարզ հիշատակումը վատագույն դեպքում կպահի բոլոր 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 տարրերը: Դա կպահանջեր Ո (կ ^ 2) տեղ.
2. Տիեզերական օպտիմիզացված ԴP-ում մեզ պետք է Լավ) տարածք միայն վերջին գեներացված շարքը պահելու համար:

Մոտեցում 3 (մաթեմատիկա)

Ինչպես գիտենք, որ պասկալի եռանկյունու յուրաքանչյուր արժեք երկիշխանության գործակից է (nCr): Եվ մենք կարող ենք գրել nCr ՝
Pascal's Triangle II Leetcode լուծում

Այժմ, եթե նկատենք, nC (r-1) և nCr հաջորդական երկընտիր գործակիցները տարբերվում են ըստ գործոնի.
Pascal's Triangle II Leetcode լուծում

Այսպիսով, հաջորդ տերմինը անընդմեջ մենք կարող ենք Պասկալի եռանկյունու մեջ վերցնել նախորդ եզրույթից:

Ալգորիթմ

  1. Տողի առաջին տերմինը նախաստորագրեք որպես 1:
  2. Գործարկեք մի ցուցիչ ինդեքսավորված սյունակի համար և հաշվարկեք հաջորդ տերմինը (տերմին (i)) որպես տերմին (i) = տերմին (i-1) * (n-i + 1) / i:
  3. Վերադարձեք հաշվարկված արժեքները որպես ցուցակ:

Իրականացում Pascal's Triangle II Leetcode Solution- ի համար

C ++ ծրագիր

#include <bits/stdc++.h>
using namespace std;

vector<int> getRow(int rowIndex) 
{
    int n=rowIndex;
   vector<int> res;
   res.push_back(1);

    for(int i=1;i<=n;i++)
    {
       int x= (int) ( ((long long)res.back()*(n-i+1) ) /i);
       res.push_back(x);
    }

    return res;
}

int main() 
{
    int rowIndex=3;
    vector<int> ans= getRow(rowIndex);
    for(auto val:ans) cout<<val<<" ";
    
    cout<<endl;
    return 0; 
}
1 3 3 1

Java ծրագիր

import java.util.*;

class Rextester{

    public static List<Integer> getRow(int rowIndex) 
    {
       int n=rowIndex;
       List<Integer> res=new ArrayList<Integer>();
       res.add(1);
        
        for(int i=1;i<=n;i++)
        {
           int x= (int) ( ((long)res.get(res.size()-1)*(n-i+1) ) /i);
           res.add(x);
        }
        
        return res;
    }

  public static void main(String args[])
    {
       	int rowIndex=3;
        List<Integer> ans= getRow(rowIndex);
        for(int val:ans)  System.out.print(val+" ");
    }
}
1 3 3 1

Բարդության վերլուծություն Pascal's Triangle II Leetcode լուծման համար

Timeամանակի բարդություն

Լավ): Տողի յուրաքանչյուր արժեք հաշվարկվում է հաստատուն ժամանակում:

Տիեզերական բարդություն 

Լավ): Ոչ մի լրացուցիչ տարածք չի պահանջվում, բացի ելքը պահելու համար: