โซลูชัน Leetcode Triangle II ของ Pascal


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน ไมโครซอฟท์
แถว การเขียนโปรแกรมแบบไดนามิก คณิตศาสตร์

สารบัญ

คำชี้แจงปัญหา

ในปัญหานี้เราได้รับดัชนีแถว (i) ของสามเหลี่ยมปาสคาล เราต้องสร้างอาร์เรย์เชิงเส้นที่มีค่าของแถว ith และส่งกลับมา ดัชนีแถวเริ่มจาก 0
เรารู้ว่าสามเหลี่ยมของปาสคาลเป็นสามเหลี่ยมที่แต่ละตัวเลขเป็นผลรวมของตัวเลขสองตัวที่อยู่ด้านบน

โซลูชัน Leetcode Triangle II ของ Pascal

ตัวอย่าง

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

ดังที่เราทราบว่าแต่ละค่าในรูปสามเหลี่ยมของปาสคาลเป็นค่าสัมประสิทธิ์ทวินาม (nCr) โดยที่ n คือแถวและ r คือดัชนีคอลัมน์ของค่านั้น

เราได้พูดถึงปัญหาที่คล้ายกันที่เราต้องส่งคืนแถวทั้งหมดจากแถวดัชนี 0 ไปยังดัชนีแถวของสามเหลี่ยมของปาสคาลที่นี่ - Leetcode สามเหลี่ยมปาสคาล

แต่ในปัญหานี้เราต้องส่งคืนแถวเดียวที่ได้รับดัชนี
ในที่นี้เราจะพูดถึงสามแนวทางในการแก้ไขปัญหานี้:

แนวทางที่ 1 (Brute Force Recursion)

เรารู้ว่าแต่ละตัวเลขในสามเหลี่ยมนี้คือผลรวมของตัวเลขสองตัวที่อยู่ด้านบน กล่าวคือ
Num (row, col) = Num (row-1, col) + Num (row-1, col-1)
ดังนั้นเราจึงสามารถเรียกใช้ฟังก์ชัน Num (rowIndex, j) ซ้ำ ๆ สำหรับดัชนีแต่ละคอลัมน์ของแถวนั้นและส่งคืนรายการที่เกิดขึ้น

ดังที่เราเห็นว่าเราได้กำหนดวิธีการเรียกซ้ำสำหรับการค้นหา Num (i, j) ตอนนี้มีบางกรณีพื้นฐานสำหรับสิ่งที่:

  • ค่าในแถวแรกจะเป็น 1 ดังนั้นสำหรับ row = 0, Num (แถว, …) = 0
  • ค่าในคอลัมน์แรกจะเป็น 1 ดังนั้นสำหรับ col = 0, Num (…, col) = 0
  • ค่าสุดท้ายของแต่ละแถวจะเท่ากับ 1 ดังนั้นสำหรับ col = row = k, Num (k, k) = 0

การใช้งานสำหรับโซลูชัน Leetcode ของ Triangle II ของ Pascal

โปรแกรม 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

โปรแกรม Java

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

การวิเคราะห์ความซับซ้อนสำหรับโซลูชัน Leetcode Triangle II ของ Pascal

ความซับซ้อนของเวลา

O (2 ^ k): โดยที่ k คือดัชนีแถวที่กำหนด
เรากำลังเรียกการเรียกซ้ำสำหรับ Num (i, j) เป็น Num (i-1, j) + Num (i-1, j-1) ดังนั้นเวลาในการค้นหา Num (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 (การเขียนโปรแกรมแบบไดนามิก)

ในการเรียกซ้ำด้านบนเราจะเห็นว่าเรากำลังเรียกใช้ฟังก์ชัน Num (i, j) สำหรับฟังก์ชันเดียวกัน (i, j) ซ้ำ ๆ

ดังนั้นสิ่งที่เราทำได้คือเราสามารถบันทึก ans สำหรับแต่ละอัน (i, j) ได้ดังนั้นเมื่อใดก็ตามที่จำเป็นต้องเรียกใช้ฟังก์ชันนั้นอีกครั้งเราจะส่งคืนคำตอบที่แคชโดยตรงจากหน่วยความจำโดยไม่ต้องคำนวณอีก จึงช่วยประหยัดเวลาได้มาก.
สำหรับการจัดเก็บคำตอบแบบไดนามิกเราสามารถใช้ได้ แผนที่แฮช โดยที่คีย์จะเป็นการรวมกันของดัชนีแถวและดัชนีคอลัมน์

อีกสิ่งหนึ่งที่เราสามารถเห็นได้ที่นี่คือเราต้องการเฉพาะค่าแถวก่อนหน้าเพื่อค้นหาค่าของแถวปัจจุบัน ดังนั้นเราจึงสามารถจัดเก็บค่าแถวได้ครั้งละหนึ่งค่าและใช้เพื่อค้นหาค่าของแถวถัดไป ดังนั้นเราสามารถลดความซับซ้อนของพื้นที่เป็น O (k) ได้ที่นี่

อัลกอริทึมที่ปรับให้เหมาะสมกับพื้นที่:
1. สร้างอาร์เรย์สองแถวสำหรับแถวก่อนหน้าและแถวปัจจุบันตามลำดับ
2. เริ่มต้น prev แถวเป็น {1}
3. เรียกใช้ลูปสำหรับแถว ith จาก i = 1 ถึง i =แถวดัชนี. และสร้างค่าแถวใหม่จากแถวก่อนหน้าและเก็บไว้ใน สกุลเงิน แถว
4. ตอนนี้อัปเดต prev แถวโดยกำหนด ตูด แถวไปที่ prev แถวและทำซ้ำขั้นตอนเดียวกันในลูปนี้
5. ย้อนกลับแถวสุดท้ายที่เก็บไว้ใน prev แถว

การใช้งานสำหรับโซลูชัน Leetcode ของ Triangle II ของ Pascal

โปรแกรม 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+" ");
    }
}

โปรแกรม Java (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

การวิเคราะห์ความซับซ้อนสำหรับโซลูชัน Leetcode Triangle II ของ Pascal

ความซับซ้อนของเวลา

O (k ^ 2):  การท่องจำจะช่วยให้แน่ใจว่าองค์ประกอบเฉพาะจะถูกคำนวณเพียงครั้งเดียว และสมมติว่าต้องใช้เวลาคงที่ในการดึง ans จากแผนที่แฮชต้องใช้เวลาคงที่ในการคำนวณแต่ละค่าของสามเหลี่ยมของปาสคาล
ตอนนี้เราจบการคำนวณ 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. ในพื้นที่ที่เหมาะสม DP ที่เราต้องการ ตกลง) เว้นวรรคเพื่อจัดเก็บแถวที่สร้างล่าสุดเท่านั้น

แนวทางที่ 3 (คณิตศาสตร์)

ดังที่เราทราบว่าแต่ละค่าในรูปสามเหลี่ยมของปาสคาลเป็นสัมประสิทธิ์ทวินาม (nCr) และเราสามารถเขียน nCr เป็น:
โซลูชัน Leetcode Triangle II ของ Pascal

ทีนี้ถ้าเราสังเกตเห็นว่าสัมประสิทธิ์ทวินามต่อเนื่อง nC (r-1) และ nCr แตกต่างกันไปตามปัจจัยของ:
โซลูชัน Leetcode Triangle II ของ Pascal

ดังนั้นเราสามารถหาพจน์ถัดไปในรูปสามเหลี่ยมของปาสคาลจากคำก่อนหน้า

ขั้นตอนวิธีการ:

  1. เริ่มต้นเทอมแรกของแถวเป็น 1
  2. รันลูปสำหรับคอลัมน์ที่จัดทำดัชนีและคำนวณเทอมถัดไป (term (i)) เป็น, term (i) = term (i-1) * (n-i + 1) / i
  3. ส่งคืนค่าจากการคำนวณเป็นรายการ

การใช้งานสำหรับโซลูชัน Leetcode ของ Triangle II ของ Pascal

โปรแกรม 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

โปรแกรม Java

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

การวิเคราะห์ความซับซ้อนสำหรับโซลูชัน Leetcode Triangle II ของ Pascal

ความซับซ้อนของเวลา

ตกลง): ค่าแต่ละแถวจะคำนวณตามเวลาคงที่

ความซับซ้อนของอวกาศ 

ตกลง): ไม่จำเป็นต้องมีพื้นที่เพิ่มเติมนอกเหนือจากการถือเอาท์พุท