પાસ્કલનું ત્રિકોણ II લેટકોડ સોલ્યુશન


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન માઈક્રોસોફ્ટ
અરે ડાયનેમિક પ્રોગ્રામિંગ મઠ

વિષયસુચીકોષ્ટક

સમસ્યા નિવેદન

આ સમસ્યામાં અમને પાસ્કલ ત્રિકોણનું રો ઇન્ડેક્સ (i) આપવામાં આવ્યું છે. આપણે ith પંક્તિના મૂલ્યોવાળી રેખીય એરે બનાવવી પડશે અને તેને પરત કરવી પડશે. રો ઇન્ડેક્સ 0 થી શરૂ થાય છે.
આપણે જાણીએ છીએ કે પાસ્કલનો ત્રિકોણ એક ત્રિકોણ છે જ્યાં પ્રત્યેક સંખ્યા તેના ઉપર સીધી બે નંબરોનો સરવાળો છે.

પાસ્કલનું ત્રિકોણ II લેટકોડ સોલ્યુશન

ઉદાહરણ

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

આપણે જાણીએ છીએ કે પાસ્કલના ત્રિકોણનું દરેક મૂલ્ય દ્વિપક્ષી ગુણાંક (એનસીઆર) છે જ્યાં n એ પંક્તિ છે અને r એ મૂલ્યનો સ્તંભ અનુક્રમણિકા છે.

આપણે સમાન સમસ્યા અંગે ચર્ચા કરી છે જ્યાં આપણે પંક્તિ અનુક્રમણિકા 0 થી બધી પંક્તિઓને પાસ્કલના ત્રિકોણની આપેલ પંક્તિ સૂચકાંકમાં પાછા આપવી પડશે. પાસ્કલ ત્રિકોણ લીટકોડ

પરંતુ આ સમસ્યામાં આપણે ફક્ત એક જ પંક્તિ પરત કરવાની છે જેની અનુક્રમણિકા આપવામાં આવી છે.
અહીં આપણે આ સમસ્યાનો ઉકેલ લાવવા માટે ત્રણ અભિગમો પર ચર્ચા કરીશું:

અભિગમ 1 (બ્રુટ ફોર્સ રિકર્ઝન)

આપણે જાણીએ છીએ કે આ ત્રિકોણની દરેક સંખ્યા એ તેની ઉપરની બે સંખ્યાનો સરવાળો છે. એટલે કે
સંખ્યા (પંક્તિ, કોલ) = નમ (પંક્તિ -1, કોલ) + નમ (પંક્તિ -1, કોલ -1)
તેથી આપણે તે પંક્તિના દરેક ક columnલમ અનુક્રમણિકા માટે ફંકશન ન્યુમ (પંક્તિઆન્ડેક્સ, જ) ને વારંવાર કહી શકીએ છીએ અને રચિત સૂચિ પરત કરી શકીએ છીએ.

આપણે જોઈ શકીએ છીએ કે અમે નમ (i, j) ને શોધવા માટે રિકર્સીવ અભિગમ ઘડ્યો છે. હવે તેના માટે કેટલાક બેઝ કેસો છે જે આ છે:

  • પ્રથમ પંક્તિનું મૂલ્ય 1 હશે. તેથી પંક્તિ = 0, સંખ્યા (પંક્તિ,…) = 0.
  • પ્રથમ ક columnલમનું મૂલ્ય 1 હશે. તેથી કોલ = 0, સંખ્યા (…, કોલ) = 0.
  • દરેક પંક્તિનું છેલ્લું મૂલ્ય 1 ની બરાબર હશે. તેથી કોલ = પંક્તિ = કે, નમ (કે, કે) = 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 લેટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (2 ^ કે): જ્યાં કે આપેલું રો ઇન્ડેક્સ છે.
અમે નમ (i, j) ને Num (i-1, j) + Num (i-1, j-1) તરીકે રિકર્ઝન કહી રહ્યા છીએ. આથી નમ (એન, આર) શોધવાનો સમય એનસીઆર રહેશે.
અમે આપેલ પંક્તિના બધા ક columnલમ અનુક્રમણિકા માટે આ રિકર્સીવ ફંક્શનને કહી રહ્યા છીએ
કેસી 0 + કેસી 1 + કેસી 2 +…. + કેસીકે = 2 ^ કે.
તેથી કુલ સમય જટિલતા ઓ (2 ^ કે) હશે.

અવકાશ જટિલતા 

બરાબર): આપેલ પંક્તિના તમામ મૂલ્યોને સૂચિમાં સંગ્રહિત કરવા માટે આપણને ઓ (કે) જગ્યાની જરૂર છે. ખરાબ પરિસ્થિતિમાં પણ, અમારી રિકર્ઝનને રિકરિવ ક callલ માટે ઓ (કે) સ્ટેક સ્પેસની જરૂર પડશે. તેથી ઓ (કે) + ઓ (કે) = ~ ઓ (કે).

અભિગમ 2 (ડાયનેમિક પ્રોગ્રામિંગ)

ઉપરના રિકર્ઝનમાં આપણે જોઈ શકીએ છીએ કે આપણે સમાન (i, j) માટે Num (i, j) ફંક્શનને વારંવાર કહી રહ્યા છીએ.

તો આપણે શું કરી શકીએ કે આપણે દરેક (i, j) માટેના જવાબોને યાદ કરી શકીએ જેથી કરીને જ્યારે પણ તે ફંક્શનને ફરીથી બોલાવવાની જરૂર પડે ત્યારે આપણે ફરીથી કેલક ન કા .ીને સીધા જ મેમરીમાંથી કેશ્ડ જવાબ પાછા આપીશું. આમ ઘણો સમય બચત થાય છે.
અમે ઉપયોગ કરી શકીએ તેવા જવાબો ગતિશીલ રીતે સંગ્રહિત કરવા માટે હેશ નકશો જ્યાં કી પંક્તિ અનુક્રમણિકા અને ક columnલમ અનુક્રમણિકાનું સંયોજન હશે.

એક વધુ વસ્તુ જે આપણે અહીં જોઈ શકીએ છીએ તે છે કે વર્તમાન પંક્તિના મૂલ્યો શોધવા માટે આપણને પહેલાનાં પંક્તિનાં મૂલ્યોની જ જરૂર છે. તેથી આપણે એક સમયે ફક્ત એક જ પંક્તિનાં મૂલ્યો સંગ્રહિત કરી શકીએ છીએ અને તેનો ઉપયોગ આગામી પંક્તિના મૂલ્યો શોધવા માટે કરી શકીએ છીએ. તેથી આપણે અહીં જગ્યા (ઓ) ની જટિલતા ઘટાડી શકીએ છીએ.

જગ્યા optimપ્ટિમાઇઝ એલ્ગોરિધમ:
1. અનુક્રમે પાછલી પંક્તિ અને વર્તમાન પંક્તિ માટે બે એરે બનાવો.
2. પ્રારંભ prev row 1} તરીકે પંક્તિ.
3. આઇ = 1 થી i = સુધી ith પંક્તિ માટે લૂપ ચલાવોrowIndex. અને પાછલી પંક્તિથી નવી પંક્તિનાં મૂલ્યો બનાવો અને તેને સંગ્રહિત કરો curr એરે.
4. હવે અપડેટ કરો prev સોંપીને પંક્તિ વર્તમાન પંક્તિ prev આ લૂપમાં પંક્તિ અને પુનરાવર્તન કરો.
5. સ્ટોર કરેલી છેલ્લી પંક્તિ પરત કરો prev એરે.

પાસ્કલના ત્રિકોણ 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; 
}

સી ++ પ્રોગ્રામ (સ્પેસ optimપ્ટિમાઇઝ ડીપી)

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

જાવા પ્રોગ્રામ (સ્પેસ ઓપ્ટિમાઇઝ્ડ ડી.પી.)

#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 લેટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (કે ^ 2):  સંસ્મરણો એ સુનિશ્ચિત કરશે કે કોઈ વિશિષ્ટ તત્વની ગણતરી ફક્ત એક જ વાર કરવામાં આવે છે. અને એમ ધારીને કે હેશ નકશામાંથી જવાબો મેળવવા માટે સતત સમય લે છે, તે પાસ્કલના ત્રિકોણના દરેક મૂલ્યની ગણતરી કરવામાં સતત સમય લે છે.
હવે આપણે 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. જગ્યામાં optimપ્ટિમાઇઝ ડીપીની અમને જરૂર છે બરાબર) ફક્ત નવીનતમ પેદા કરેલ પંક્તિ સંગ્રહિત કરવા માટે જગ્યા.

અભિગમ 3 (ગણિત)

આપણે જાણીએ છીએ કે પાસ્કલના ત્રિકોણનું દરેક મૂલ્ય દ્વિપક્ષી ગુણાંક (એનસીઆર) છે. અને આપણે એનસીઆર આ પ્રમાણે લખી શકીએ:
પાસ્કલનું ત્રિકોણ II લેટકોડ સોલ્યુશન

હવે જો આપણે નોંધ્યું, અનુગામી દ્વિપક્ષીય ગુણાંક એનસી (આર -1) અને એનસીઆર આના પરિબળ દ્વારા અલગ પડે છે:
પાસ્કલનું ત્રિકોણ II લેટકોડ સોલ્યુશન

આમ, આપણે પહેલાનાં શબ્દથી, પાસ્કલના ત્રિકોણમાં, એક પછીની ટર્મ મેળવી શકીએ છીએ.

એલ્ગોરિધમ:

  1. પંક્તિની પ્રથમ અવધિ 1 તરીકે પ્રારંભ કરો.
  2. Ith અનુક્રમિત ક columnલમ માટે લૂપ ચલાવો અને આગામી શબ્દ (શબ્દ (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 લેટકોડ સોલ્યુશન માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

બરાબર): પંક્તિના દરેક મૂલ્યની ગણતરી સતત સમયમાં કરવામાં આવે છે.

અવકાશ જટિલતા 

બરાબર): આઉટપુટ હોલ્ડ કરવા સિવાય કોઈ વધારાનું સ્થાન જરૂરી નથી.