LeetCode Solutions (161 серия деталей)
Это является частью серии объяснений решения LeetCode ( index ). Если вам понравилось это решение или нашли его полезным, Пожалуйста, нравится Этот пост и/или upvote Мое решение по сообщению на форумах LeetCode Анкет
Задача leetcode #118 (легко): Треугольник Паскаля
Описание:
( прыгнуть в : Идея решения Код : JavaScript | Python | Java | C ++
Дано целое число NUMROWS , вернуть первое NUMROWS из треугольника Паскаля.
В «Треугольнике Паскаля» каждое число – это сумма двух чисел непосредственно над ним, как показано:
Примеры:
| Вход: | |
| Выход: | [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] |
| Вход: | |
| Выход: | [[1]] |
Ограничения:
1
Идея:
( Прыгните к : Описание задачи Код : JavaScript | Python | Java | C ++
Для этой проблемы мы можем сделать практически, как говорят нам инструкции. Мы переоценим строительство Треугольник Паскаля ( ans ), ряд по ряду. Когда мы создаем каждый новый ряд , мы должны изначально заполнить его 1 с Так что нам не нужно беспокоиться о логике заполнения клеток края, которые имеют только одно число выше.
Тогда мы можем начать с J для каждого ряд и повторить процесс суммирования значения текущей ячейки, пока мы не достигнем средней точки ( mid ). Поскольку треугольник является симметричным, мы можем на самом деле заполнить обе половины ряда одновременно, пока мы работаем внутрь.
Как только мы достигнем конца последнего ряда, мы сможем вернуть ANS Анкет
- Сложность времени: O (n) куда N это нездоровые турнир Треугольный номер
- Сложность пространства: O (1)
Код JavaScript:
( Прыгните к : Описание задачи Идея решения
var generate = function(numRows) {
let ans = new Array(numRows)
for (let i = 0; i < numRows; i++) {
let row = new Uint32Array(i+1).fill(1),
mid = i >> 1
for (let j = 1; j <= mid; j++) {
let val = ans[i-1][j-1] + ans[i-1][j]
row[j] = val, row[row.length-j-1] = val
}
ans[i] = row
}
return ans
};
Код Python:
( Прыгните к : Описание задачи Идея решения
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = [None] * numRows
for i in range(numRows):
row, mid = [1] * (i + 1), (i >> 1) + 1
for j in range(1, mid):
val = ans[i-1][j-1] + ans[i-1][j]
row[j], row[len(row)-j-1] = val, val
ans[i] = row
return ans
Код Java:
( Прыгните к : Описание задачи Идея решения
class Solution {
public List> generate(int numRows) {
List> ans = new ArrayList>(numRows);
for (int i = 0; i < numRows; i++) {
List row = new ArrayList<>(i+1);
while (row.size() <= i) row.add(1);
int mid = i >> 1;
for (int j = 1; j <= mid; j++) {
int val = ans.get(i-1).get(j-1) + ans.get(i-1).get(j);
row.set(j, val);
row.set(row.size()-j-1, val);
}
ans.add(row);
}
return ans;
}
}
C ++ Код:
( Прыгните к : Описание задачи Идея решения
class Solution {
public:
vector> generate(int numRows) {
vector> ans(numRows);
for (int i = 0; i < numRows; i++) {
vector row(i+1, 1);
int mid = i >> 1;
for (int j = 1; j <= mid; j++) {
int val = ans[i-1][j-1] + ans[i-1][j];
row[j] = val;
row[row.size()-j-1] = val;
}
ans[i] = row;
}
return ans;
}
};
LeetCode Solutions (161 серия деталей)
Оригинал: “https://dev.to/seanpgallivan/solution-pascal-s-triangle-154d”