حل مثلث باسكال II ليت كود


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون Microsoft
مجموعة البرمجة الديناميكية الرياضيات

المشكلة بيان

في هذه المسألة حصلنا على مؤشر الصف (i) لمثلث باسكال. علينا إنشاء مصفوفة خطية تحتوي على قيم الصف i وإعادتها. يبدأ فهرس الصف من 0.
نعلم أن مثلث باسكال مثلث حيث يمثل كل رقم مجموع العددين الموجودين فوقه مباشرة.

حل مثلث باسكال II ليت كود

مثال

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

كما نعلم أن كل قيمة في مثلث باسكال هي معامل ذي الحدين (nCr) حيث n هي الصف و r هي فهرس العمود لتلك القيمة.

لقد ناقشنا مشكلة مماثلة حيث يتعين علينا إعادة جميع الصفوف من فهرس الصف 0 إلى فهرس صف معين لمثلث باسكال هنا - مثلث باسكال ليت كود

لكن في هذه المشكلة ، علينا فقط إرجاع صف واحد يتم تقديم فهرسه.
سنناقش هنا ثلاث طرق لحل هذه المشكلة:

المقاربة 1 (القوة الغاشمة العودية)

نعلم أن كل رقم في هذا المثلث هو مجموع العددين الموجودين فوقه مباشرة. بمعنى آخر
عدد (صف ، عمود) = رقم (صف -1 ، عمود) + رقم (صف -1 ، عمود -1).
لذلك يمكننا بشكل متكرر استدعاء الدالة Num (rowIndex، j) لكل فهرس عمود لذلك الصف ، وإرجاع القائمة المشكلة.

كما نرى ، قمنا بصياغة نهج تعاودي لإيجاد Num (i، j). الآن هناك بعض الحالات الأساسية لذلك وهي:

  • ستكون القيمة في الصف الأول 1. لذلك بالنسبة للصف = 0 ، العدد (الصف ، ...) = 0.
  • ستكون القيمة في العمود الأول 1. لذا بالنسبة إلى العمود = 0 ، العدد (... ، العمود) = 0.
  • ستكون القيمة الأخيرة لكل صف مساوية لـ 1. لذلك بالنسبة إلى col = row = k ، Num (k، k) = 0.

تنفيذ حل Pascal's Triangle II Leetcode

برنامج 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

تحليل التعقيد لحل باسكال المثلث الثاني ليت كود

تعقيد الوقت

يا (2 ^ ك): حيث k هو فهرس الصف المحدد.
نحن ندعو العودية لـ Num (i، j) كـ Num (i-1، j) + Num (i-1، j-1). ومن ثم سيكون وقت العثور على Num (n ، r) هو nCr.
نحن نسمي هذه الوظيفة العودية لجميع فهرس العمود للصف المحدد (k) .ie
kC0 + kC1 + kC2 +…. + kCk = 2 ^ ك.
ومن ثم سيكون التعقيد الزمني الإجمالي O (2 ^ k).

تعقيد الفضاء 

نعم): نحتاج إلى مساحة O (k) لتخزين جميع قيم الصف المحدد في قائمة. أيضًا في أسوأ الأحوال ، ستحتاج العودية إلى مساحة مكدس O (k) للمكالمة العودية. ومن ثم O (ك) + O (ك) = ~ O (ك).

النهج 2 (البرمجة الديناميكية)

في العودية أعلاه ، يمكننا أن نرى أننا ندعو الدالة Num (i ، j) لنفس (i ، j) بشكل متكرر.

لذا ما يمكننا فعله هو أنه يمكننا حفظ الجواب لكل (i، j) بحيث كلما دعت الحاجة إلى استدعاء هذه الوظيفة مرة أخرى ، نعيد الإجابة المخزنة مؤقتًا مباشرة من الذاكرة دون الحساب مرة أخرى. وبالتالي توفير الكثير من الوقت.
لتخزين الإجابات التي يمكننا استخدامها بشكل ديناميكي خريطة التجزئة حيث سيكون المفتاح هو مزيج من فهرس الصف وفهرس العمود.

هناك شيء آخر يمكننا رؤيته هنا وهو أننا نحتاج فقط إلى قيم الصف السابق لإيجاد قيم الصف الحالي. لذلك يمكننا تخزين قيم صف واحد فقط في كل مرة واستخدامها للعثور على قيم الصف التالي. ومن ثم يمكننا تقليل التعقيد المكاني إلى O (k) هنا.

خوارزمية الفضاء الأمثل:
1. قم بإنشاء صفيفين للصف السابق والصف الحالي على التوالي.
2. تهيئة السابق صف كـ {1}.
3. قم بتشغيل حلقة للصف ith من i = 1 إلى i =RowIndex. وإنشاء قيم صف جديدة من الصف السابق وتخزينها فيه تيار مجموعة مصفوفة.
4. الآن التحديث السابق صف عن طريق التخصيص حمار صف ل السابق صف وكرر نفس العملية في هذه الحلقة.
5. أعد الصف الأخير المخزن في السابق مجموعة مصفوفة.

تنفيذ حل Pascal's Triangle II Leetcode

برنامج C ++ باستخدام Memoization

#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 ++ (مساحة محسَّنة DP)

#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

برنامج Java باستخدام Memoization

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

برنامج جافا (مساحة محسنة DP)

#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):  من شأن Memoization التأكد من أن عنصرًا معينًا يتم حسابه مرة واحدة فقط. وبافتراض أن جلب الجواب من خريطة التجزئة يستغرق وقتًا ثابتًا ، فإنه يستغرق وقتًا ثابتًا لحساب كل قيمة لمثلث باسكال.
الآن ننتهي بحساب 1 + 2 + 3 + ... + (ك + 1) = (ك + 1) (ك + 2) / 2 قيم وهي = ~ O (ك ^ 2).

تعقيد الفضاء 

1. يحفظ الحفظ البسيط جميع العناصر 1 + 2 + 3 +… + (k + 1) = (k + 1) (k + 2) / 2 في أسوأ الحالات. قد يتطلب ذلك يا (ك ^ 2) الفضاء.
2. في الفضاء الأمثل DP نحن بحاجة حسنا) مساحة فقط لتخزين أحدث صف تم إنشاؤه.

النهج 3 (رياضيات)

كما نعلم أن كل قيمة في مثلث باسكال هي معامل ذي الحدين (nCr). ويمكننا كتابة nCr على النحو التالي:
حل مثلث باسكال II ليت كود

الآن إذا لاحظنا أن المعاملات ذات الحدين المتتالية nC (r-1) و nCr تختلف حسب عامل:
حل مثلث باسكال II ليت كود

وبالتالي ، يمكننا اشتقاق الحد التالي على التوالي في مثلث باسكال ، من الحد السابق.

الخوارزمية:

  1. قم بتهيئة الفصل الدراسي الأول من الصف كـ 1.
  2. قم بتشغيل حلقة للعمود المفهرس وحساب المصطلح التالي (المصطلح (i)) مثل المصطلح (i) = المصطلح (i-1) * (n-i + 1) / i
  3. إرجاع القيم المحسوبة كقائمة.

تنفيذ حل Pascal's Triangle II Leetcode

برنامج 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

تحليل التعقيد لحل باسكال المثلث الثاني ليت كود

تعقيد الوقت

نعم): يتم حساب كل قيمة للصف في وقت ثابت.

تعقيد الفضاء 

نعم): لا توجد مساحة إضافية مطلوبة بخلاف الاحتفاظ بالإخراج.