పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది అమెజాన్ మైక్రోసాఫ్ట్
అర్రే డైనమిక్ ప్రోగ్రామింగ్ మఠం

విషయ సూచిక

సమస్యల నివేదిక

ఈ సమస్యలో మాకు పాస్కల్ ట్రయాంగిల్ యొక్క రో ఇండెక్స్ (i) ఇవ్వబడింది. మేము ith అడ్డు వరుస విలువలను కలిగి ఉన్న సరళ శ్రేణిని సృష్టించి దానిని తిరిగి ఇవ్వాలి. వరుస సూచిక 0 నుండి మొదలవుతుంది.
పాస్కల్ యొక్క త్రిభుజం ఒక త్రిభుజం అని మనకు తెలుసు, ఇక్కడ ప్రతి సంఖ్య దాని పైన ఉన్న రెండు సంఖ్యల మొత్తం.

పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్

ఉదాహరణ

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

పాస్కల్ యొక్క త్రిభుజంలోని ప్రతి విలువ ద్విపద గుణకం (nCr) అని మనకు తెలుసు, ఇక్కడ n వరుస మరియు r ఆ విలువ యొక్క కాలమ్ సూచిక.

పాస్కల్ యొక్క త్రిభుజం యొక్క అడ్డు వరుస సూచికకు అడ్డు వరుస సూచిక 0 నుండి అన్ని అడ్డు వరుసలను తిరిగి ఇవ్వాల్సిన చోట మేము ఇలాంటి సమస్యను చర్చించాము - పాస్కల్ ట్రయాంగిల్ లీట్‌కోడ్

కానీ ఈ సమస్యలో మనం ఒకే వరుసను తిరిగి ఇవ్వాలి, దీని సూచిక ఇవ్వబడుతుంది.
ఈ సమస్య పరిష్కారం కోసం ఇక్కడ మేము మూడు విధానాలను చర్చిస్తాము:

అప్రోచ్ 1 (బ్రూట్ ఫోర్స్ రికర్షన్)

ఈ త్రిభుజంలోని ప్రతి సంఖ్య దాని పైన ఉన్న రెండు సంఖ్యల మొత్తం అని మనకు తెలుసు. అనగా
సంఖ్య (అడ్డు వరుస, కోల్) = సంఖ్య (అడ్డు వరుస -1, కోల్) + సంఖ్యా (అడ్డు వరుస -1, కోల్ -1).
కాబట్టి మనం ఆ అడ్డు వరుస యొక్క ప్రతి కాలమ్ ఇండెక్స్ కొరకు నం (rowIndex, j) ఫంక్షన్‌ను పదేపదే పిలుస్తాము మరియు ఏర్పడిన జాబితాను తిరిగి ఇవ్వవచ్చు.

మనం చూడగలిగినట్లుగా, సంఖ్యా (i, j) ను కనుగొనటానికి పునరావృత విధానాన్ని రూపొందించాము. ఇప్పుడు వాటి కోసం కొన్ని బేస్ కేసులు ఉన్నాయి:

  • మొదటి వరుసలో విలువ 1. ఉంటుంది. కాబట్టి అడ్డు వరుస = 0, సంఖ్య (అడ్డు వరుస,…) = 0.
  • మొదటి నిలువు వరుస వద్ద విలువ 1. అవుతుంది. కాబట్టి col = 0, Num (…, col) = 0.
  • ప్రతి అడ్డు వరుస యొక్క చివరి విలువ 1 కి సమానంగా ఉంటుంది. కాబట్టి col = row = k, Num (k, k) = 0.

పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్ కోసం అమలు

సి ++ ప్రోగ్రామ్

#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 అనేది ఇచ్చిన వరుస సూచిక.
మేము సంఖ్యా (i, j) కోసం పునరావృత్తిని Num (i-1, j) + Num (i-1, j-1) అని పిలుస్తున్నాము. అందువల్ల సంఖ్యా (n, r) ను కనుగొనే సమయం nCr అవుతుంది.
ఇచ్చిన వరుస (k) యొక్క అన్ని కాలమ్ ఇండెక్స్ కోసం మేము ఈ పునరావృత ఫంక్షన్‌ను పిలుస్తున్నాము .ఇది
kC0 + kC1 + kC2 +…. + kCk = 2 ^ k.
అందువల్ల మొత్తం సమయ సంక్లిష్టత O (2 ^ k) అవుతుంది.

అంతరిక్ష సంక్లిష్టత 

అలాగే): ఇచ్చిన అడ్డు వరుస యొక్క అన్ని విలువలను జాబితాలో నిల్వ చేయడానికి మాకు O (k) స్థలం అవసరం. చెత్త సందర్భంలో కూడా మా పునరావృతానికి పునరావృత కాల్ కోసం O (k) స్టాక్ స్థలం అవసరం. అందువల్ల O (k) + O (k) = ~ O (k).

అప్రోచ్ 2 (డైనమిక్ ప్రోగ్రామింగ్)

పై పునరావృతంలో మనం అదే (i, j) ఫంక్షన్ కోసం పదేపదే సంఖ్యా (i, j) అని పిలుస్తున్నట్లు చూడవచ్చు.

కాబట్టి మనం చేయగలిగేది ఏమిటంటే, ప్రతి (i, j) కోసం మేము జవాబులను జ్ఞాపకం చేసుకోగలుగుతాము, తద్వారా ఆ ఫంక్షన్‌ను మళ్లీ పిలవవలసిన అవసరం వచ్చినప్పుడు, మళ్ళీ లెక్కించకుండా మెమరీ నుండి కాష్ చేసిన జవాబును నేరుగా తిరిగి ఇస్తాము. అందువలన చాలా సమయం ఆదా.
మేము ఉపయోగించగల సమాధానాలను డైనమిక్‌గా నిల్వ చేయడానికి హాష్ మ్యాప్ ఇక్కడ కీ వరుస సూచిక మరియు కాలమ్ సూచిక కలయిక అవుతుంది.

ఇక్కడ మనం చూడగలిగే మరో విషయం ఏమిటంటే, ప్రస్తుత అడ్డు వరుస విలువలను కనుగొనడానికి మనకు మునుపటి వరుస విలువలు మాత్రమే అవసరం. అందువల్ల మేము ఒక సమయంలో ఒక వరుస విలువలను మాత్రమే నిల్వ చేయవచ్చు మరియు తదుపరి వరుస యొక్క విలువలను కనుగొనడానికి దాన్ని ఉపయోగించవచ్చు. అందువల్ల మనం ఇక్కడ స్థల సంక్లిష్టతను O (k) కు తగ్గించవచ్చు.

స్పేస్ ఆప్టిమైజ్ చేసిన అల్గోరిథం:
1. మునుపటి వరుస మరియు ప్రస్తుత వరుస కోసం వరుసగా రెండు శ్రేణులను సృష్టించండి.
2. ప్రారంభించండి గత అడ్డు వరుస {1 as.
3. i = 1 నుండి i = వరకు ith వరుస కోసం ఒక లూప్‌ను అమలు చేయండిrowIndex. మరియు మునుపటి అడ్డు వరుస నుండి క్రొత్త వరుస విలువలను ఉత్పత్తి చేసి, దాన్ని నిల్వ చేయండి కుర్ర్ అమరిక.
4. ఇప్పుడు నవీకరించండి గత కేటాయించడం ద్వారా అడ్డు వరుస ప్రస్తు అడ్డు వరుస గత అడ్డు వరుస మరియు ఈ లూప్‌లో అదే విధానాన్ని పునరావృతం చేయండి.
5. నిల్వ చేసిన చివరి వరుసను తిరిగి ఇవ్వండి గత అమరిక.

పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్ కోసం అమలు

మెమోయిజేషన్ ఉపయోగించి సి ++ ప్రోగ్రామ్

#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; 
}

సి ++ ప్రోగ్రామ్ (స్పేస్ ఆప్టిమైజ్డ్ డిపి)

#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):  జ్ఞాపకశక్తి ఒక నిర్దిష్ట మూలకాన్ని ఒకసారి మాత్రమే లెక్కించేలా చేస్తుంది. మరియు హాష్ మ్యాప్ నుండి జవాబులను పొందటానికి స్థిరమైన సమయం పడుతుందని uming హిస్తే, పాస్కల్ యొక్క త్రిభుజం యొక్క ప్రతి విలువను లెక్కించడానికి స్థిరమైన సమయం పడుతుంది.
ఇప్పుడు మనం 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. స్పేస్ ఆప్టిమైజ్ చేసిన డిపిలో మనకు అవసరం అలాగే) తాజా ఉత్పత్తి చేసిన అడ్డు వరుసను నిల్వ చేయడానికి మాత్రమే స్థలం.

అప్రోచ్ 3 (మ్యాథ్స్)

పాస్కల్ యొక్క త్రిభుజంలోని ప్రతి విలువ ద్విపద గుణకం (nCr) అని మనకు తెలుసు. మరియు మనం nCr ను ఇలా వ్రాయవచ్చు:
పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్

ఇప్పుడు మనం గమనించినట్లయితే, వరుస ద్విపద గుణకాలు nC (r-1) మరియు nCr వీటి కారకాలతో విభిన్నంగా ఉంటాయి:
పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్

ఈ విధంగా, పాస్కల్ యొక్క త్రిభుజంలో మేము తరువాతి పదాన్ని వరుసగా మునుపటి పదం నుండి పొందవచ్చు.

అల్గోరిథం:

  1. అడ్డు వరుస యొక్క మొదటి పదాన్ని 1 గా ప్రారంభించండి.
  2. Ith సూచిక కాలమ్ కోసం ఒక లూప్‌ను అమలు చేయండి మరియు తదుపరి పదాన్ని (టర్మ్ (i)), టర్మ్ (i) = టర్మ్ (i-1) * (n-i + 1) / i గా లెక్కించండి.
  3. లెక్కించిన విలువలను జాబితాగా తిరిగి ఇవ్వండి.

పాస్కల్ యొక్క ట్రయాంగిల్ II లీట్‌కోడ్ సొల్యూషన్ కోసం అమలు

సి ++ ప్రోగ్రామ్

#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 లీట్‌కోడ్ సొల్యూషన్ కోసం సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

అలాగే): అడ్డు వరుస యొక్క ప్రతి విలువ స్థిరమైన సమయంలో లెక్కించబడుతుంది.

అంతరిక్ష సంక్లిష్టత 

అలాగే): అవుట్పుట్ను పట్టుకోవడం మినహా అదనపు స్థలం అవసరం లేదు.