पास्कलको त्रिकोण II लीटकोड समाधान


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन माइक्रोसफ्ट
एरे डायनामिक प्रोग्रामिंग गणित

विषयसूची

समस्या वक्तव्य

यस समस्यामा हामीलाई पास्कल त्रिकोणको रो इंडेक्स (i) दिइयो। हामीले ith प row्क्ति का मानहरू सहित एक रेखीय एरे सिर्जना गर्नुपर्नेछ र फर्काउनु पर्छ। प index्क्ति सूचकांक ० बाट सुरू हुन्छ।
हामीलाई थाहा छ कि पास्कलको त्रिकोण एक त्रिकोण हो जहाँ प्रत्येक नम्बर दुई नम्बरहरूको योग हुन्छ।

पास्कलको त्रिकोण II लीटकोड समाधान

उदाहरणका

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

जस्तो कि हामीलाई थाहा छ कि पास्कलको त्रिकोणमा प्रत्येक मान द्विपक्षीय गुणांक (nCr) हो जहाँ n प the्क्ति हो र r मानको स्तम्भ अनुक्रमणिका हो।

हामीले त्यस्तै समस्याको बारेमा छलफल गरेका थियौं जहाँ हामीले पंक्ति सूची ० बाट सबै प pas्क्तिहरू पास्कलको त्रिकोणको दिइएको पंक्ति सूचकमा फिर्ता गर्नुपर्नेछ। पास्कल ट्राएंगल लेटकोड

तर यस समस्यामा हामी केवल एकल प row्क्ति फर्काउनु पर्छ जसको अनुक्रमणिका दिइन्छ।
यहाँ हामी यस समस्याको समाधानका लागि तीन दृष्टिकोणहरु छलफल गर्नेछौं:

दृष्टिकोण १ (ब्रुट फोर्स रिकर्सन)

हामीलाई थाहा छ कि यस त्रिकोणमा प्रत्येक नम्बर दुई माथिको जोड यो हुन्छ। ie
Num (प ,्क्ति, स्तम्भ) = Num (प .्क्ति -१, स्तम्भ) + Num (प row्क्ति -१, col-1)।
त्यसकारण हामी बारम्बार त्यस प row्क्तिको प्रत्येक स्तम्भ अनुक्रमणिकाका लागि प्रकार्य Num (rowIndex, j) कल गर्न सक्छौं, र बनेको सूची फिर्ता गर्न सक्छौं।

हामी देख्न सक्दछौं कि हामीले Num (i, j) खोज्नका लागि रिकर्सिभ दृष्टिकोण बनाएका छौं। अब त्यहाँ केहि आधार केसहरू छन् जुन ती हुन्:

  • पहिलो प row्क्तिमा मान १ हुनेछ। त्यसैले प row्क्ति = ०, संख्या (प row्क्ति,…) = ०।
  • पहिलो स्तम्भमा मान १ हुनेछ। त्यसैले # कोल ० ०, Num (…, col) = ०।
  • प्रत्येक प row्क्तिको अन्तिम मान १ बराबर हुनेछ। त्यसैले कोलो = प =्क्ति = k, Num (k, k) = ०।

पास्कलको त्रिकोण 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 (२ ^ k): जहाँ k दिइएको पंक्ति सूचकांक हो।
हामी Num (i, j) को Num (i-1, j) + Num (i-1, j-1) को रूपमा रिकर्सन कल गर्दैछौं। यसैले Num खोज्नको लागि समय (n, r) nCr हुनेछ।
हामी दिइएको पंक्ति (k) .ie को सबै स्तम्भ अनुक्रमणिकाका लागि यो रिकर्सिभ प्रकार्य कल गर्दैछौं
kC0 + kC1 + kC2 +…। + kCk = २ ^ के।
त्यसकारण कुल समय जटिलता O (२ ^ k) हुनेछ।

ठाउँ जटिलता 

ठिक छ): हामीलाई ओ (के) स्पेस चाहिन्छ दिईएको प row्क्तिको सबै मानहरू सूचीमा भण्डार गर्न। साथै सबैभन्दा नराम्रो अवस्थामा पनि हाम्रो रिकर्सनलाई रिकर्सिभ कलको लागि ओ (के) स्ट्याक ठाउँ चाहिन्छ। तसर्थ O (k) + O (k) = ~ O (k)।

दृष्टिकोण २ (डायनामिक प्रोग्रामिंग)

माथिको रिकर्सनमा हामी देख्न सक्छौं कि हामी Num (i, j) फंक्शन उही (i, j) को लागि बारम्बार कल गर्दैछौं।

त्यसोभए हामी के गर्न सक्दछौं कि हामी प्रत्येक (i, j) का लागि उत्तरहरू मेमोमाइज गर्न सक्दछौं ताकि जब कुनै कार्यलाई फेरि बोलाउन आवश्यक हुन्छ हामी क्यास उत्तरलाई मेमोरीबाट सीधा पुनः गणना नगरी फर्काउँछौं। यसैले धेरै समय बचत भयो।
गतिशील रूपमा उत्तरहरू भण्डारण गर्न हामी प्रयोग गर्न सक्दछौं ह्यास नक्शा जहाँ कुञ्जी प row्क्ति अनुक्रमणिका र स्तम्भ अनुक्रमणिकाको संयोजन हुनेछ।

एउटा कुरा जुन हामी यहाँ हेर्न सक्छौं त्यो यो हो कि हामीलाई हालको प row्क्तिको मानहरू पत्ता लगाउन केवल अघिल्लो प row्क्ति मानहरू मात्र चाहिन्छ। त्यसकारण हामी एक पटकमा केवल एउटा प row्क्ति मानहरू भण्डारण गर्न सक्छौं र यसलाई अर्को प row्क्तिको मानहरू फेला पार्न प्रयोग गर्न सक्छौं। त्यसैले हामी यहाँ ओ (के) मा जटिलता कम गर्न सक्छौं।

ठाउँ अनुकूलित एल्गोरिथ्म:
१. अघिल्लो प row्क्ति र हालको प row्क्ति क्रमशःका लागि दुई एर्रेहरू सिर्जना गर्नुहोस्।
२. सुरु गर्नुहोस् prev प row्क्ति {१} को रूपमा।
Ith ith पंक्ति को लागी i = १ बाट i =रोइन्डिडेक्स। र अघिल्लो प row्क्तिबाट नयाँ प row्क्ति मान उत्पन्न गर्नुहोस् र यसलाई भण्डार गर्नुहोस् curr एर्रे।
Now. अब अपडेट गर्नुहोस् prev पंक्ति तोक्दै हृदय प row्क्ति prev प row्क्ति र यस लूपमा उही प्रक्रिया दोहोर्याउनुहोस्।
Stored. भण्डार गरिएको अन्तिम प row्क्ति फर्काउनुहोस् prev एर्रे।

पास्कलको त्रिकोण 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 ++ कार्यक्रम (स्पेस अनुकूलित डीपी)

#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 ^ २):  मेमोमाइजेशनले निश्चित गर्दछ कि कुनै खास तत्व एक पटक मात्र गणना गरिएको छ। र यो मान्दै कि हेस नक्शाबाट उत्तरहरू प्राप्त गर्न स्थिर समय लिन्छ यसले पास्कलको त्रिकोणको प्रत्येक मान गणना गर्न स्थिर समय लिन्छ।
अब हामी १ + २ + + + + + + (k + १) = (k + १) (k + २) / २ मानहरू गणना गर्दछौं जुन = ~ O (k ^ २) हो।

ठाउँ जटिलता 

१. साधारण मेमोमाइजेशनले सबै १ + २ + + + ... + (k + १) = (के + १) (के + २) / २ तत्वहरू सबैभन्दा खराब स्थितिमा समात्दछ। त्यो आवश्यक छ O (k ^ २) ठाउँ।
२. अन्तरिक्षमा अनुकूलित डीपी हामीलाई चाहिन्छ ठिक छ) भर्खरको उत्पन्न प row्क्ति भण्डारण गर्न खाली ठाउँ।

दृष्टिकोण ((गणित)

जस्तो कि हामीलाई थाहा छ कि पास्कलको त्रिकोणमा प्रत्येक मान द्विपक्षीय गुणांक (एनसीआर) हो। र हामी एनसीआर निम्नको रूपमा लेख्न सक्छौं:
पास्कलको त्रिकोण II लीटकोड समाधान

अब यदि हामी याद गर्छौं, क्रमिक द्विपक्षीय गुणांक एनसी (r-1) र nCr भिन्नता:
पास्कलको त्रिकोण II लीटकोड समाधान

यस प्रकार हामी अघिल्लो शब्दबाट पास्कलको त्रिकोणमा अर्को पंक्तिमा अर्को शब्द निकाल्न सक्छौं।

एल्गोरिथ्म:

  1. पहिलोको रूपमा प term्क्तिको १ लाई सुरू गर्नुहोस्।
  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 लीटकोड समाधानको लागि जटिलता विश्लेषण

समय जटिलता

ठिक छ): प the्क्तिको प्रत्येक मान स्थिर समयमा गणना गरिन्छ।

ठाउँ जटिलता 

ठिक छ): आउटपुट होल्डिंग बाहेक कुनै अतिरिक्त ठाउँको आवश्यक पर्दैन।