পাস্কালের ত্রিভুজ দ্বিতীয় লাইটকোড সমাধান  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক মাইক্রোসফট
আলগোরিদিম বিন্যাস আইনসংগ্রহ ডায়নামিক প্রোগ্রামিং সাক্ষাত্কার সাক্ষাৎকারের প্রস্তুতি লেটকোড LeetCodeSolutions ম্যাথ

সুচিপত্র

সমস্যা বিবৃতি  

এই সমস্যায় আমাদের পাস্কাল ত্রিভুজটির সারি সূচক (i) দেওয়া হয়েছে। আমাদেরকে একটি রৈখিক অ্যারে তৈরি করতে হবে যা ইথ সারিটির মান রয়েছে এবং এটি ফিরিয়ে আনতে হবে। সারি সূচকটি 0 থেকে শুরু হয়।
আমরা জানি যে পাস্কালের ত্রিভুজটি একটি ত্রিভুজ যেখানে প্রতিটি সংখ্যা সরাসরি তার উপরে দুটি সংখ্যার যোগফল।

পাস্কালের ত্রিভুজ দ্বিতীয় লাইটকোড সমাধান

উদাহরণ

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

যেমন আমরা জানি যে পাস্কালের ত্রিভুজের প্রতিটি মান একটি দ্বিপদী সহগ (এনসিআর) যেখানে n হল সারি এবং r হল সেই মানটির কলাম সূচক।

আমরা অনুরূপ সমস্যাটি নিয়ে আলোচনা করেছি যেখানে আমাদের পাসকালের ত্রিভুজটির প্রদত্ত সারি সূচকে সারি সূচক 0 থেকে সমস্ত সারিটি ফিরে আসতে হবে - পাস্কাল ত্রিভুজ লেটকোড

তবে এই সমস্যায় আমাদের কেবলমাত্র একক সারিতে ফিরে যেতে হবে যার সূচি দেওয়া হয়েছে।
এখানে আমরা এই সমস্যার সমাধানের জন্য তিনটি পন্থা আলোচনা করব:

পন্থা 1 (ব্রুট ফোর্স পুনরাবৃত্তি)  

আমরা জানি যে এই ত্রিভুজের প্রতিটি সংখ্যা হ'ল সরাসরি তার উপরে দুটি সংখ্যার যোগফল। অর্থাত্
সংখ্যা (সারি, করল) = সংখ্যা (সারি -1, করল) + নুম (সারি -1, কল -1)
সুতরাং আমরা বারবার এই সারির প্রতিটি কলাম সূচীর জন্য নুন (ক্রাউড ইন্ডেক্স, জে) ফাংশনটি কল করতে পারি এবং গঠিত তালিকাটি ফিরে আসতে পারি।

আরো দেখুন
টাউন জজ লেটকোড সমাধানটি সন্ধান করুন

যেমন আমরা দেখতে পাচ্ছি আমরা নুম (আই, জে) সন্ধানের জন্য পুনরাবৃত্ত পদ্ধতিটি তৈরি করেছি। এখন এর জন্য কয়েকটি বেস কেস রয়েছে:

  • প্রথম সারিতে মান 1 হবে। সুতরাং সারি = 0, সংখ্যা (সারি,…) = 0।
  • প্রথম কলামে মান হবে ১। সুতরাং কল = 1, সংখ্যা (…, কল) = 0 এর জন্য।
  • প্রতিটি সারির শেষ মান 1 এর সমান হবে So সুতরাং কল = সারি = কে, নুম (কে, কে) = 0 for

পাস্কালের ত্রিভুজ 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

পাস্কলের ত্রিভুজ তৃতীয় লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (2 ^ কে): যেখানে কে প্রদত্ত সারি সূচক।
আমরা Num (i, j) এর জন্য Num (i-1, j) + Num (i-1, j-1) হিসাবে পুনরাবৃত্তি বলছি। সুতরাং Num (n, r) সন্ধানের জন্য সময় এনসিআর হবে।
প্রদত্ত সারি (কে) .ie এর সমস্ত কলাম সূচীর জন্য আমরা এই পুনরাবৃত্ত ফাংশনটি বলছি
কেসি 0 + কেসি 1 + কেসি 2 +…। + কেসিকে = 2 ^ কে।
সুতরাং মোট সময়ের জটিলতা ও (2 ^ কে) হবে।

স্পেস জটিলতা ity 

ঠিক আছে): প্রদত্ত সারির সমস্ত মান একটি তালিকায় সংরক্ষণ করার জন্য আমাদের ও (কে) স্থানের প্রয়োজন। এছাড়াও সবচেয়ে খারাপ ক্ষেত্রে আমাদের পুনরাবৃত্তির পুনরাবৃত্তির কলের জন্য ও (কে) স্ট্যাক স্পেসের প্রয়োজন হবে। সুতরাং ও (কে) + ও (কে) = ~ ও (কে)।

আরো দেখুন
ভাল জুড়ির সংখ্যা লেটকোড সমাধান

পদ্ধতির 2 (ডায়নামিক প্রোগ্রামিং 

উপরের পুনরাবৃত্তিতে আমরা দেখতে পাচ্ছি যে আমরা বার বার বার (i, j) এর জন্য Num (i, j) ফাংশনটি কল করছি।

সুতরাং আমরা যা করতে পারি তা হ'ল আমরা প্রতিটি (i, j) এর জন্য উত্তরগুলি স্মরণ করতে পারি যাতে যখনই আবার সেই ফাংশনটি কল করার প্রয়োজন হয় আমরা আবার কোনও গণনা না করে সরাসরি ক্যাশ উত্তরটি মেমরি থেকে ফিরিয়ে দেব। এভাবে অনেক সময় সাশ্রয় হচ্ছে।
গতিশীলভাবে আমরা যে উত্তরগুলি ব্যবহার করতে পারি তা সঞ্চয় করার জন্য হ্যাশ মানচিত্র যেখানে কীটি সারি সূচক এবং কলাম সূচকের সংমিশ্রণ হবে।

আরও একটি জিনিস যা আমরা এখানে দেখতে পাচ্ছি তা হ'ল বর্তমান সারিটির মান সন্ধানের জন্য আমাদের কেবল পূর্ববর্তী সারির মানগুলির প্রয়োজন। অতএব আমরা একসাথে কেবল একটি সারি মান সংরক্ষণ করতে পারি এবং পরের সারির মানগুলি খুঁজে পেতে এটি ব্যবহার করতে পারি। সুতরাং আমরা এখানে ও (কে) এর স্পেস জটিলতা হ্রাস করতে পারি।

স্থানটি অনুকূলিতকরণ করা অ্যালগরিদম:
1. যথাক্রমে পূর্ববর্তী সারি এবং বর্তমান সারির জন্য দুটি অ্যারে তৈরি করুন।
2. সূচনা পূর্ববর্তী সারিটি {1} হিসাবে}
৩. আই = সারিতে আই = 3 থেকে আই = এর জন্য একটি লুপ চালানসারি ইনডেক্স। এবং পূর্ববর্তী সারি থেকে নতুন সারি মান উত্পন্ন করে এটিকে সংরক্ষণ করুন কার্ল অ্যারে।
4. এখন আপডেট পূর্ববর্তী সারি দ্বারা নির্ধারিত ইতর লোক সারি থেকে পূর্ববর্তী সারি এবং এই লুপ একই প্রক্রিয়া পুনরাবৃত্তি।
৫. সঞ্চিত শেষ সারিটি ফিরিয়ে দিন পূর্ববর্তী অ্যারে।

পাস্কালের ত্রিভুজ 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

পাস্কলের ত্রিভুজ তৃতীয় লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (কে ^ 2):  স্মৃতিচারণ নিশ্চিত করে যে কোনও নির্দিষ্ট উপাদানকে কেবল একবার গণনা করা হয়। এবং ধরে নিই যে হ্যাশ ম্যাপ থেকে উত্তর আনতে ধ্রুব সময় লাগে এটি প্যাসকের ত্রিভুজটির প্রতিটি মান গণনা করতে ধ্রুব সময় নেয়।
এখন আমরা 1 + 2 + 3 +… + (কে + 1) = (কে + 1) (কে + 2) / 2 মানগুলি গণনা করি যা = ~ ও (কে ^ 2)।

আরো দেখুন
সাজানো অ্যারেগুলি লেটকোড সমাধানটি মার্জ করুন

স্পেস জটিলতা ity 

1. সাধারণ স্মৃতিচিহ্নগুলি সবচেয়ে খারাপ অবস্থায় সমস্ত 1 + 2 + 3 +… + ((কে + 1) = (কে + 1) (কে + 2) / 2 উপাদানগুলিকে ধারণ করবে। যে প্রয়োজন হবে ও (কে ^ 2) স্থান।
২. স্পেসে অপ্টিমাইজড ডিপি আমাদের দরকার ঠিক আছে) স্থানটি সর্বশেষতম উত্পন্ন সারিটি সংরক্ষণ করতে।

পদ্ধতি 3 (গণিত)  

যেমনটি আমরা জানি যে পাস্কালের ত্রিভুজের প্রতিটি মান একটি দ্বিপদী সহগ (এনসিআর)। এবং আমরা এনসিআর এইভাবে লিখতে পারি:
পাস্কালের ত্রিভুজ দ্বিতীয় লাইটকোড সমাধান

এখন যদি আমরা লক্ষ্য করি, ক্রমাগত দ্বিপদী সহগগুলি এনসি (আর -1) এবং এনসিআর এর উপাদানগুলির দ্বারা পৃথক হয়:
পাস্কালের ত্রিভুজ দ্বিতীয় লাইটকোড সমাধান

সুতরাং, আমরা পাশ্বিকের ত্রিভুজের একটি পরের শব্দটি পূর্ববর্তী শব্দ থেকে প্রাপ্ত করতে পারি।

অ্যালগরিদম:

  1. সারিটির প্রথম শব্দটি 1 হিসাবে শুরু করুন।
  2. ইথ ইনডেক্সড কলামের জন্য একটি লুপ চালনা করুন এবং পরবর্তী শব্দ (টার্ম (i)) হিসাবে, পদ (i) = পদ (i-1) * (এন-আই + 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

পাস্কলের ত্রিভুজ তৃতীয় লেটকোড সমাধানের জন্য জটিলতা বিশ্লেষণ

সময় জটিলতা

ঠিক আছে): সারির প্রতিটি মান স্থির সময়ে গণনা করা হয়।

স্পেস জটিলতা ity 

ঠিক আছে): আউটপুট ধরে রাখার জন্য অতিরিক্ত কোনও স্থানের প্রয়োজন নেই।