پاسکل کا مثلث II لیٹکوڈ حل


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون مائیکروسافٹ
لڑی متحرک پروگرامنگ ریاضی

مسئلہ یہ بیان

اس پریشانی میں ہمیں پاسکل مثلث کا رو انڈیکس (i) دیا گیا ہے۔ ہمیں ایک لکیری سرنی بنانی ہے جس میں آٹ قطار کی اقدار ہوں گی۔ صف انڈیکس 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 = قطار = 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) جگہ کی ضرورت ہے۔ نیز بدترین صورتحال میں بھی ہماری تکرار کو recursive کال کے لئے O (K) اسٹیک اسپیس کی ضرورت ہوگی۔ لہذا O (k) + O (k) = ~ O (k)۔

نقطہ نظر 2 (متحرک پروگرامنگ)

مندرجہ بالا تکرار میں ہم دیکھ سکتے ہیں کہ ہم N (i، j) فنکشن کو اسی (i ، j) کے لئے بار بار بلا رہے ہیں۔

تو ہم کیا کرسکتے ہیں کہ ہم ہر ایک (i ، j) کے جوابات یادداشت میں لائیں تاکہ جب بھی اس فنکشن کو دوبارہ فون کرنے کی ضرورت پیش آئے تو ہم بغیر کسی حساب کتاب کے कैش جواب کو میموری سے براہ راست واپس کردیں۔ اس طرح بہت وقت بچایا جا رہا ہے۔
متحرک طور پر ان جوابات کو ذخیرہ کرنے کے لئے جو ہم استعمال کرسکتے ہیں ہیش کا نقشہ جہاں کلید صف انڈیکس اور کالم انڈیکس کا امتزاج ہوگی۔

ایک اور چیز جو ہم یہاں دیکھ سکتے ہیں وہ یہ ہے کہ موجودہ صف کی اقدار کو تلاش کرنے کے لئے ہمیں صرف پچھلی صف کی قدروں کی ضرورت ہے۔ لہذا ہم ایک وقت میں صرف ایک ہی صف اقدار کو اسٹور کرسکتے ہیں اور اگلی صف کی قدر تلاش کرنے کے ل. اس کا استعمال کرسکتے ہیں۔ لہذا ہم یہاں O (k) کی جگہ کی پیچیدگی کو کم کرسکتے ہیں۔

خلائی مواقع الگورتھم:
1. بالترتیب پچھلی صف اور موجودہ صف کے لئے دو ارے بنائیں۔
2. شروع کرنا سابقہ قطار بطور {1}.
3. I = 1 سے i = میں ith قطار کے ل a ایک لوپ چلائیںصف انڈیکس. اور پچھلی صف سے صف کی نئی قدریں تیار کریں اور اسے اسٹور کریں curr سرنی۔
4. اب اپ ڈیٹ کریں سابقہ تفویض کرکے قطار دہرائیں قطار سے سابقہ اس لوپ میں قطار اور ایک ہی عمل کو دہرائیں۔
5. میں ذخیرہ شدہ آخری قطار واپس کریں سابقہ سرنی۔

پاسکل کے مثلث 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; 
}

سی ++ پروگرام (اسپیس کو بہتر بنایا ہوا ڈی پی)

#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) ہے۔ اور ہم این سی آر کو اس طرح لکھ سکتے ہیں:
پاسکل کا مثلث 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 لیٹ کوڈ حل کے لئے پیچیدگی کا تجزیہ

وقت کی پیچیدگی

ٹھیک ہے): قطار کی ہر ایک قیمت کا مستقل وقت میں حساب کیا جاتا ہے۔

خلائی پیچیدگی 

ٹھیک ہے): آؤٹ پٹ کے انعقاد کے علاوہ کسی بھی اضافی جگہ کی ضرورت نہیں ہے۔