പാസ്കലിന്റെ ത്രികോണം II ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ മൈക്രോസോഫ്റ്റ്
അറേ ഡൈനാമിക് പ്രോഗ്രാമിംഗ് മഠം

ഉള്ളടക്ക പട്ടിക

പ്രശ്നം പ്രസ്താവന

ഈ പ്രശ്‌നത്തിൽ ഞങ്ങൾക്ക് പാസ്കൽ ത്രികോണത്തിന്റെ വരി സൂചിക (i) നൽകിയിട്ടുണ്ട്. Ith വരിയുടെ മൂല്യങ്ങൾ അടങ്ങിയ ഒരു ലീനിയർ അറേ ഞങ്ങൾ സൃഷ്ടിക്കുകയും അത് തിരികെ നൽകുകയും വേണം. വരി സൂചിക 0 മുതൽ ആരംഭിക്കുന്നു.
പാസ്കലിന്റെ ത്രികോണം ഒരു ത്രികോണമാണെന്ന് നമുക്കറിയാം, അവിടെ ഓരോ സംഖ്യയും അതിന് മുകളിലുള്ള രണ്ട് അക്കങ്ങളുടെ ആകെത്തുകയാണ്.

പാസ്കലിന്റെ ത്രികോണം II ലീറ്റ്കോഡ് പരിഹാരം

ഉദാഹരണം

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

പാസ്കലിന്റെ ത്രികോണത്തിലെ ഓരോ മൂല്യവും ഒരു ദ്വിമാന ഗുണകം (nCr) ആണെന്ന് നമുക്കറിയാം, ഇവിടെ n വരിയും r എന്നത് ആ മൂല്യത്തിന്റെ നിര സൂചികയുമാണ്.

പാസ്കലിന്റെ ത്രികോണത്തിന്റെ വരി സൂചികയിലേക്ക് വരി സൂചിക 0 ൽ നിന്ന് എല്ലാ വരികളും തിരികെ നൽകേണ്ട സമാനമായ പ്രശ്നം ഞങ്ങൾ ചർച്ചചെയ്തു - പാസ്കൽ ട്രയാംഗിൾ ലീറ്റ്കോഡ്

എന്നാൽ ഈ പ്രശ്‌നത്തിൽ നമുക്ക് സൂചിക നൽകിയ ഒറ്റ വരി മാത്രമേ നൽകേണ്ടതുള്ളൂ.
ഈ പ്രശ്നം പരിഹരിക്കുന്നതിനുള്ള മൂന്ന് സമീപനങ്ങൾ ഞങ്ങൾ ഇവിടെ ചർച്ച ചെയ്യും:

സമീപനം 1 (ബ്രൂട്ട് ഫോഴ്‌സ് ആവർത്തനം)

ഈ ത്രികോണത്തിലെ ഓരോ സംഖ്യയും അതിന് മുകളിലുള്ള രണ്ട് അക്കങ്ങളുടെ ആകെത്തുകയാണെന്ന് നമുക്കറിയാം. അതായത്
സംഖ്യ (വരി, നിര) = സംഖ്യ (വരി -1, നിര) + സംഖ്യ (വരി -1, നിര -1).
അതിനാൽ, ആ വരിയുടെ ഓരോ നിര സൂചികയ്‌ക്കും നമുക്ക് Num (rowIndex, j) എന്ന ഫംഗ്ഷനെ ആവർത്തിച്ച് വിളിക്കാനും രൂപംകൊണ്ട ലിസ്റ്റ് തിരികെ നൽകാനും കഴിയും.

നമുക്ക് കാണാനാകുന്നതുപോലെ, സംഖ്യ (i, j) കണ്ടെത്തുന്നതിനായി ഞങ്ങൾ ആവർത്തന സമീപനം രൂപപ്പെടുത്തിയിട്ടുണ്ട്. അവയ്‌ക്ക് ഇപ്പോൾ ചില അടിസ്ഥാന കേസുകളുണ്ട്:

  • ആദ്യ വരിയിലെ മൂല്യം 1 ആയിരിക്കും. അതിനാൽ വരി = 0, സംഖ്യ (വരി,…) = 0.
  • ആദ്യ നിരയിലെ മൂല്യം 1 ആയിരിക്കും. അതിനാൽ നിര = 0, സംഖ്യ (…, നിര) = 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 എന്നത് നൽകിയിരിക്കുന്ന വരി സൂചികയാണ്.
Num (i, j) നുള്ള ആവർത്തനത്തെ Num (i-1, j) + Num (i-1, j-1) എന്ന് വിളിക്കുന്നു. അതിനാൽ സംഖ്യ (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 (ഡൈനാമിക് പ്രോഗ്രാമിംഗ്)

മുകളിലുള്ള ആവർത്തനത്തിൽ‌, ഞങ്ങൾ‌ അതേ (i, j) നം (i, j) ഫംഗ്ഷനെ ആവർത്തിച്ച് വിളിക്കുന്നുവെന്ന് കാണാം.

അതിനാൽ നമുക്ക് ചെയ്യാൻ കഴിയുന്നത് ഓരോന്നിനും (i, j) ഉത്തരം ഓർമ്മപ്പെടുത്താം എന്നതാണ്, അതിനാൽ ആ ഫംഗ്ഷനെ വീണ്ടും വിളിക്കേണ്ട ആവശ്യമുള്ളപ്പോഴെല്ലാം കാഷെ ചെയ്ത ഉത്തരം വീണ്ടും കണക്കാക്കാതെ മെമ്മറിയിൽ നിന്ന് നേരിട്ട് നൽകും. അങ്ങനെ ധാരാളം സമയം ലാഭിക്കുന്നു.
നമുക്ക് ഉപയോഗിക്കാവുന്ന ഉത്തരങ്ങൾ ചലനാത്മകമായി സംഭരിക്കുന്നതിന് ഹാഷ് മാപ്പ് വരി സൂചികയുടെയും നിര സൂചികയുടെയും സംയോജനമായിരിക്കും കീ.

നിലവിലെ വരിയുടെ മൂല്യങ്ങൾ കണ്ടെത്തുന്നതിന് ഞങ്ങൾക്ക് മുമ്പത്തെ വരി മൂല്യങ്ങൾ മാത്രമേ ആവശ്യമുള്ളൂ എന്നതാണ് ഇവിടെ കാണാൻ കഴിയുന്ന ഒരു കാര്യം. അതിനാൽ ഞങ്ങൾക്ക് ഒരു സമയം ഒരു വരി മൂല്യങ്ങൾ മാത്രമേ സംഭരിക്കാനും അടുത്ത വരിയുടെ മൂല്യങ്ങൾ കണ്ടെത്താനും ഇത് ഉപയോഗിക്കാൻ കഴിയൂ. അതിനാൽ നമുക്ക് ഇവിടെ സ്ഥല സങ്കീർണ്ണത O (k) ആയി കുറയ്ക്കാൻ കഴിയും.

സ്പേസ് ഒപ്റ്റിമൈസ് ചെയ്ത അൽഗോരിതം:
1. മുമ്പത്തെ വരിയിലും നിലവിലെ വരിയിലും യഥാക്രമം രണ്ട് അറേകൾ സൃഷ്ടിക്കുക.
2. സമാരംഭിക്കുക മുമ്പത്തേത് വരി {1 as ആയി.
Ith വരിയിൽ i = 3 മുതൽ i = വരെ ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുകrowIndex. മുമ്പത്തെ വരിയിൽ നിന്ന് പുതിയ വരി മൂല്യങ്ങൾ സൃഷ്ടിച്ച് അതിൽ സംഭരിക്കുക curr അറേ.
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+" ");
    }
}

ജാവ പ്രോഗ്രാം (സ്പേസ് ഒപ്റ്റിമൈസ് ചെയ്ത ഡിപി)

#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):  ഒരു പ്രത്യേക ഘടകം ഒരു തവണ മാത്രമേ കണക്കാക്കൂ എന്ന് മെമ്മൈസേഷൻ ഉറപ്പാക്കും. ഹാഷ് മാപ്പിൽ നിന്ന് ഉത്തരം ലഭിക്കുന്നതിന് നിരന്തരമായ സമയമെടുക്കുന്നുവെന്ന് കരുതുക, പാസ്കലിന്റെ ത്രികോണത്തിന്റെ ഓരോ മൂല്യവും കണക്കാക്കാൻ നിരന്തരമായ സമയമെടുക്കും.
ഇപ്പോൾ നമ്മൾ 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)), term (i) = term (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 ലീറ്റ്കോഡ് പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

ശരി): വരിയുടെ ഓരോ മൂല്യവും സ്ഥിരമായ സമയത്താണ് കണക്കാക്കുന്നത്.

ബഹിരാകാശ സങ്കീർണ്ണത 

ശരി): Hold ട്ട്‌പുട്ട് കൈവശം വയ്ക്കുകയല്ലാതെ അധിക സ്ഥലം ആവശ്യമില്ല.