Паскаль гурвалжин Leetcode


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Google-ийн Samsung
Array Математик

The Паскаль гурвалжин нь Амазон, Майкрософт болон бусад компаниудаас олон удаа асуудаг Leetcode-ийн маш сайн асуудал юм. бид сөрөг бус бүхэл тоог өгсөн мөр, Эхлээд хэвлэ эгнээ паскаль гурвалжны эгнээ.

Жишээ нь

эгнээ = 5

Паскаль гурвалжин Leetcode

эгнээ = 6

Паскаль гурвалжин Leetcode

Паскаль гурвалжин Leetcode-ийн шийдлийн төрлүүд

  1. Динамик програмчлал

Динамик програмчлал

арга барил

Энэхүү санаа нь бидэнд паскаль гурвалжны эгнээ байгаа бол одоогийн мөрний зэргэлдээ утгыг давтаж нэмж дараагийн мөрийг хялбархан тооцоолох боломжтой гэдгийг ойлгох явдал юм. Паскаль гурвалжин үүсгэх энэхүү давталт процессыг a гэж үзэв динамик програмчлал мөр бүрийг өмнөх мөрөнд үндэслэн байгуулах хандлага.

Паскаль гурвалжин Leetcode-ийн алгоритм

  1. үндсэн тохиолдлуудыг тодорхойлох.
  2. Паскаль гурвалжны эхний мөрийг {1} гэж эхлүүлнэ.
  3. Гаднах гогцоог i = 0-ээс i = хүртэл ажиллуулна мөр, гурвалжингийн мөр бүрийг үүсгэхэд зориулагдсан болно.
  4. Гурвалжингийн мөр тус бүрийн элементийг тооцоолохдоо дотоод давталтыг j = 1-ээс j = {өмнөх мөрний хэмжээ} хүртэл ажиллуулна уу.
  5. эгнээний элементүүдийг тооцоолохдоо дотоод гогцоонд алхам бүр дээр өмнөх эгнээний зэргэлдээ элемент тус бүрийг нэмнэ.
  6. Дотоод давталт дууссаны дараа үүсгэсэн мөрийг гаргана уу.
  7. Тооны гаднах гогцоог гүйцэтгэнэ эгнээ өгөөд дараа нь паскаль гурвалжны мөр бүрийг хэвлэ.

The алгоритм доор харуулав:

Паскаль гурвалжин Leetcode

Хэрэгжүүлэх

Паскаль гурвалжин Leetcode-д зориулсан C ++ програм
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void pascalTriangle(int rows)
{
    if(rows == 0)
    return;
    
    vector <int> rowVector;
    
    for(int i=0;i<rows;i++)
    {
        rowVector.insert(rowVector.begin(),1);
        
        for(int j=1;j<rowVector.size() - 1 ;j++)
        rowVector[j] = rowVector[j]+rowVector[j+1];
        
        for(auto i : rowVector)
        cout<<i<<" ";
        
        cout<<endl;
    }
}
int main()
{
    int rows = 5;
    
    cout<<"The pascal triangle of "<<rows<<" rows is"<<endl;
    pascalTriangle(rows);
    
    
    return 0;
}
The pascal triangle of 5 rows is
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
Паскаль гурвалжин Leetcode-д зориулсан Java програм
import java.io.*;
import java.util.*;

class TutorialCup
{
    static void pascalTriangle(int rows)
    {
        if(rows == 0)
        return;
        
        ArrayList <Integer> rowVector = new ArrayList<>();
        
        for(int i=0;i<rows;i++)
        {
            rowVector.add(0,1);
            
            for(int j=1;j<rowVector.size() - 1 ;j++)
            rowVector.set(j,rowVector.get(j)+rowVector.get(j+1));
            
            Iterator it = rowVector.iterator();
            
            while(it.hasNext())
                System.out.print((Integer)it.next()+" ");
            
            System.out.println();
        }
    }
    public static void main (String[] args) 
    {
        int rows = 5;
    
        System.out.println("The pascal triangle of "+rows+" rows is");
        pascalTriangle(rows);
    }
}
The pascal triangle of 5 rows is
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1

Нарийн төвөгтэй байдлын шинжилгээ

  1. Цаг хугацааны нарийн төвөгтэй байдал: T (n) = O(эгнээ2), хоёр үүртэй гогцоо.
  2. Сансрын нарийн төвөгтэй байдал: A (n) = O (эгнээ2), паскаль гурвалжны мөр тус бүрийг хадгалах зориулалттай.

Ашигласан материал