LeetCode - треугольник Паскаля

Постановка задачи

Дано целое число NUMROWS , вернуть первые числа Треугольник Паскаля .

В Треугольник Паскаля , каждое число – это сумма двух чисел непосредственно над ним, как показано:

Заявление о проблеме, взятое из: https://leetcode.com/problems/pascals-triangle

Пример 1:

Input: numRows = 5
Output: [ [1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1] ]

Пример 2:

Input: numRows = 1
Output: [[1]]

Ограничения:

- 1 <= numRows <= 30

Объяснение

Подход грубой силы

Простой метод состоит в том, чтобы запустить две петли и рассчитать значение биноминального коэффициента во внутренней петле.

Например, первая строка имеет 1 , вторая строка имеет 1 1 , третья строка имеет 1 2 1 ,.. и так далее. Каждая запись в линии является значением биномиального коэффициента. Значение записи ITH в линии номера строки C (Line, I). Значение можно рассчитать с помощью следующей формулы.

C(line, i) = line! / ( (line-i)! * i! )

Небольшой фрагмент C ++ из приведенной выше логики:

void printPascal(int n)
{
    for (int line = 0; line < n; line++){
        for (int i = 0; i <= line; i++)
            cout <<" "<< binomialCoefficient(line, i);
        cout <<"\n";
    }
}

int binomialCoefficient(int n, int k)
{
    int result = 1;

    if (k > n - k)
        k = n - k;

    for (int i = 0; i < k; ++i){
        result *= (n - i);
        result /= (i + 1);
    }

    return result;
}

Поскольку мы генерируем коэффициент для каждой итерации Временная сложность приведенной выше проблемы – O (n^3) Анкет

Оптимизированное решение (O (n^2) Время и O (n^2) дополнительное пространство)

Если мы посмотрим на треугольник Паскаля, мы увидим, что каждая запись – это сумма двух значений над ним. Таким образом, мы создали 2D -массив, в котором хранится ранее сгенерированные значения.

Небольшой фрагмент C ++ из приведенной выше логики:

for (int line = 0; line < n; line++) {
    for (int i = 0; i <= line; i++) {
        if (line == i || i == 0)
            arr[line][i] = 1;
        else
            arr[line][i] = arr[line - 1][i - 1] + arr[line - 1][i];
        cout << arr[line][i] << " ";
    }
    cout << "\n";
}

Оптимизированное решение (O (n^2) Время и O (1) дополнительное пространство)

Этот подход основан на подходе грубой силы. Биномиальный коэффициент это Вход может быть представлен как C (линия, я) и все строки начинаются со значения 1. Идея здесь состоит в том, чтобы рассчитать C (линия, я) используя C (линия, я – 1) Анкет Это может быть рассчитано во время O (1), используя следующее.

C(line, i)     = line! / ( (line - i)! * i! )
C(line, i - 1) = line! / ( (line - i + 1)! * (i - 1)! )

So using the above approach we  can change the formula as below:
C(line, i)     = C(line, i - 1) * (line - i + 1) / i

C(line, i) can be calculated from C(line, i - 1) in O(1) time.

Давайте проверим алгоритм:

- initialize vector> result

- loop for line = 1; line <= n; line++
  - initialize vector temp
  - set C = 1

  - loop for i = 1; i <= line; i++
    - temp.push_back(C)
    - C = C * (line - i) / i

  - result.push_back(temp)

- return result

C ++ Решение

class Solution {
public:
    vector> generate(int numRows) {
        vector> result;

        for (int line = 1; line <= numRows; line++){
            vector temp;
            int C = 1;

            for (int i = 1; i <= line; i++){
                temp.push_back(C);
                C = C * (line - i) / i;
            }

            result.push_back(temp);
        }

        return result;
    }
};

Голанг раствор

func generate(numRows int) [][]int {
    var result [][]int

    for line := 1; line <= numRows; line++ {
        var temp []int
        C := 1

        for i := 1; i <= line; i++ {
            temp = append(temp, C);
            C = C * (line - i) / i;
        }

        result = append(result, temp)
    }

    return result
}

JavaScript Solution

var generate = function(numRows) {
    var result = [];

    for(let line = 1; line <= numRows; line++){
        var temp = [];
        let C = 1;

        for(let i = 1; i <= line; i++){
            temp.push(C);
            C = C * (line - i) / i;
        }

        result.push(temp);
    }

    return result;
};

Давайте сушат наш алгоритм, чтобы увидеть, как работает решение.

Input: numRows = 3

Step 1: initialize vector> result

Step 2: loop for line = 1; line <= numRows
        1 <= 3
        true

        initialize vector temp

        C = 1

        loop for i = 1; i <= line
        1 <= 1
        true

        temp.push_back(C);
        temp = [1]

        C = C * (line - i) / i;
        C = 1 * (1  - 1) / 1
        C = 0

        i++
        i = 2

        loop for i <= line
        2 <= 1
        false

        result.push_back(temp)

        result = [[1]]

        line++
        line = 2

Step 3: loop for line <= numRows
        2 <= 3
        true

        initialize vector temp

        C = 1

        loop for i = 1; i <= line
        1 <= 2
        true

        temp.push_back(C);
        temp = [1]

        C = C * (line - i) / i
        C = 1 * (2  - 1) / 1
        C = 1 * 1 / 1

        i++
        i = 2

        loop for i <= line
        2 <= 2
        true

        loop for i <= line
        2 <= 2
        true

        temp.push_back(C);
        temp = [1, 1]

        C = C * (line - i) / i
        C = 1 * (2  - 2) / 1
        C = 1 * 0 / 1
        C = 0

        i++
        i = 3

        loop for i <= line
        3 <= 2
        false

        result.push_back(temp)

        result = [[1], [1, 1]]

        line++
        line = 3

Step 4: loop for line <= numRows
        3 <= 3
        true

        initialize vector temp

        C = 1

        loop for i = 1; i <= line
        1 <= 3
        true

        temp.push_back(C);
        temp = [1]

        C = C * (line - i) / i
        C = 1 * (3 - 1) / 1
        C = 1 * 2 / 1
        C = 2

        i++
        i = 2

        loop for i <= line
        2 <= 3
        true

        temp.push_back(C);
        temp = [1, 2]

        C = C * (line - i) / i
        C = 2 * (3 - 2) / 2
        C = 2 * 1 / 2
        C = 1

        i++
        i = 3

        loop for i <= line
        3 <= 3
        true

        temp.push_back(C);
        temp = [1, 2, 1]

        C = C * (line - i) / i
        C = 1 * (3 - 3) / 3
        C = 1 * 0 / 3
        C = 0

        i++
        i = 4

        loop for i <= line
        4 <= 3
        false

        result.push_back(temp)
        result = [[1], [1, 1], [1, 2, 1]]

        line++
        line = 4

Step 5: loop for line <= numRows
        4 <= 3
        false

Step 6: return result

So the result is [[1], [1, 1], [1, 2, 1]].

Оригинал: “https://dev.to/_alkesh26/leetcode-pascal-s-triangle-2l0k”