د پاسکال مثلث II لیټکوډ حل


مشکل کچه په اسانۍ سره
په مکرر ډول دننه پوښتل کیږي ترلاسه کړئ Amazon د Microsoft
پیشه متحرک برنامې ریاضی

ستونزه بیان

پدې ستونزه کې موږ ته د پاسکال مثلث د قطار شاخص (i) ورکړل شو. موږ باید یو خطي سلسله جوړه کړو چې د ith قطار ارزښتونه پکې شامل دي او بیرته یې بیرته ورکوو. د قطار شاخص له 0 څخه پیل کیږي.
موږ پوهیږو چې د پاسکال مثلث یو مثلث دی چیرې چې هر شمیره د دوه شمیرو مجموعه ده له پورته پورته.

د پاسکال مثلث II لیټکوډ حل

بېلګه

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

لکه څنګه چې موږ پوهیږو چې د پاسکال مثلث کې هر ارزښت دوه اړخیز کوفیف (nCr) دی چیرې چې n صف دی او r د ورته ارزښت کالم شاخص دی.

موږ ورته ستونزې بحث کړی دی چیرې چې موږ باید د قطار شاخص 0 څخه ټول قطارونه د پاسکال مثلث ته ورکړل شوي قطار شاخص ته راوبولو. پاسکال مثلث لیټکوډ

مګر پدې ستونزه کې موږ باید یوازې یو قطار بیرته راستون کړو چې شاخص یې ورکړل شوی.
دلته به موږ د دې ستونزې د حل لپاره درې لارې په اړه بحث وکړو:

تګلاره 1 (د ځواک ځواک تکرار)

موږ پوهیږو چې پدې مثلث کې هره شمیره د مستقیم پورته پورته د دوه شمیرونو مجموعه ده. يعني
Num (قطار ، col) = Num (قطار -1 ، col) + Num (قطار -1 ، کول-1).
نو موږ کولی شو په تکرار سره د دې قطار هر کالم شاخص لپاره Num (rowIndex ، j) فنکشن ته زنګ ووهلو ، او جوړ شوی لیست بیرته راستون کړو.

لکه څنګه چې موږ لیدلی شو موږ د نیوم (i ، j) موندلو لپاره تکراري چلند ترتیب کړی. اوس دلته د هغې لپاره ځینې اساسې قضیې شتون لري کوم چې دي:

  • په لومړي قطار کې ارزښت به 1 وي. نو د قطار لپاره 0 0 ، Num (قطار ،…) = XNUMX.
  • په لومړي کالم کې ارزښت به 1 وي. نو د col = 0 ، Num (… ، col) = 0 لپاره.
  • د هر قطار آخري ارزښت به د 1 سره مساوي وي. نو د col = قطار = k لپاره ، Num (k ، k) = 0.

د پاسکال مثلث II لیټکوډ حل لپاره پلي کول

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

جاوا پروګرام

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

د پاسکال مثلث II لیټکوډ حل لپاره د پیچلو تحلیلونه

د وخت پیچلتیا

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) سټیک ځای ته اړتیا ولري. له همدې امله O (k) + O (k) = ~ O (k).

کړنلاره 2 (متحرک برنامې)

په پورتنۍ تکرار کې موږ لیدلی شو چې موږ د Num (i، j) فنکشن د ورته (i ، j) لپاره تکرار کوو.

نو هغه څه چې موږ یې کولی شو دا دی چې موږ د هرې (i ، j) لپاره ځوابونه یادداشت کولی شو نو کله چې بیا د دې فعالیت غږولو ته اړتیا وي نو موږ پرته له محاسبه کولو پرته له حافظې څخه نیغ په نیغه ځواب راوړو. پدې توګه د ډیری وخت سپمول.
په متحرک ډول د ځوابونو ذخیره کولو لپاره چې موږ یې وکاروو هیش نقشه چیرې چې کیلي به د قطار شاخص او د کالم شاخص ترکیب وي.

یو بل شی چې موږ دلته لیدلی شو هغه دا چې موږ د اوسني قطار ارزښتونو موندلو لپاره یوازې پخوانۍ قطار ارزښتونو ته اړتیا لرو. له همدې امله موږ کولی شو په یو وخت کې یوازې د یو قطار ارزښتونه ذخیره کړو او د راتلونکي قطار د ارزښتونو موندلو لپاره یې وکاروو. له همدې امله موږ کولی شو دلته O (k) ته د ځای پیچلتیا کمه کړو.

ځای مطلوب الګوریتم:
1. په ترتیب سره د تیرو قطار او اوسني قطار لپاره دوه تیرونه جوړ کړئ.
2. پیل کول مخکې قطار د {1} په توګه.
3. د I = 1 څخه i = تر ith قطار لپاره لوپ چل کړئليکه. او د پخواني قطار څخه نوي قطار ارزښتونه تولید کړئ او په کې یې زیرمه کړئ کرور صف.
4. اوس تازه کړئ مخکې په برابرولو سره قطار وروست ته مخکې قطار او ورته پروسه په دې لوپ کې تکرار کړئ.
5. په کې ساتل شوي وروستی قطار بیرته راستانه کړئ مخکې صف.

د پاسکال مثلث II لیټکوډ حل لپاره پلي کول

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

د جاوا برنامې د میموشن په کارولو سره

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+" ");
    }
}

د جاوا برنامه (د فضا مطلوب 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

د پاسکال مثلث II لیټکوډ حل لپاره د پیچلو تحلیلونه

د وخت پیچلتیا

O (K ^ 2):  یادداشت به ډاډ ترلاسه کړي چې یو ځانګړی عنصر یوازې یو ځل محاسبه کیږي. او فرض کړئ چې دا د hash نقشې څخه د ځوابونو ترلاسه کولو لپاره ثابت وخت نیسي چې د پاسکال مثلث هر ارزښت محاسبه کولو لپاره دوامداره وخت نیسي.
اوس موږ د 1 + 2 + 3 +… + + (K + 1) = (k + 1) (K + 2) / 2 ارزښتونو حساب کولو پای ته رسولی چې = ~ O (k ^ 2) دي.

د ځای پیچلتیا 

1. ساده یادداشت به په ټولو خراب حالت کې ټول 1 + 2 + 3 + ... + ((K + 1) = (k + 1) (K + 2) / 2 عناصر وساتي. دا به اړتیا ولري O (K ^ 2) ځای.
2. په فضا کې مطلوب DP ته موږ اړتیا لرو سمه ده) ځای د وروستي تولید شوی قطار ساتلو لپاره.

دریم (ریاضی)

لکه څنګه چې موږ پوهیږو چې د پاسکال مثلث کې هر ارزښت دوه اړخیز کوفیف (nCr) دی. او موږ کولی شو پدې ډول nCr ولیکو:
د پاسکال مثلث II لیټکوډ حل

اوس که موږ وګورو ، پرله پسې دوه اړخیز متفاوت NC (r-1) او nCr د فاکتور سره توپیر لري:
د پاسکال مثلث II لیټکوډ حل

په دې توګه ، موږ کولی شو راتلونکی اصطلاح د مخکینۍ اصطالح څخه ، د پاسکال مثلث کې په یو قطار کې ترلاسه کړو.

الګوریتم:

  1. د قطار لومړۍ دوره د 1 په توګه پیل کړئ.
  2. د ith ترتیب شوي کالم لپاره لوپ پرمخ وړئ او راتلونکی اصطلاح (اصطلاح (i)) لکه څنګه چې ، اصطلاح (i) = اصطلاح (i-1) * (n-i + 1) / i محاسبه کړئ.
  3. محاسبه شوي ارزښتونه د لیست په توګه راستانه کړئ.

د پاسکال مثلث II لیټکوډ حل لپاره پلي کول

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

جاوا پروګرام

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

د پاسکال مثلث II لیټکوډ حل لپاره د پیچلو تحلیلونه

د وخت پیچلتیا

سمه ده): د قطار هر ارزښت په ثابت وخت کې محاسبه کیږي.

د ځای پیچلتیا 

سمه ده): د محصول ساتلو پرته نور اضافي ځای ته اړتیا نشته.