Треугольник Паскаля | Leetcode Неправильный ответ
https://leetcode.com/problems/pascals-triangle/
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> ret;
for (int i=0; i<numRows; i++) {
vector<int> v;
if (i==0) {
v.push_back(1);
} else {
v.push_back(1) ;
for (int j=0; j<i; j++) {
v.push_back(ret[i-1][j] + ret[i-1][j+1]);
}
}
ret.push_back(v);
}
return ret;
}
};
Когда я запускаю пользовательский тестовый случай:
Input: 3
Output: [[1],[1,1],[1,2,1]]
Expected: [[1],[1,1],[1,2,1]]
Но это не могло быть принято. Результат представления неверен Ответ:
Input: 3
Output: [[1],[1,32753],[1,32754,36704997]]
Expected: [[1],[1,1],[1,2,1]]
Кто-нибудь может сказать мне, что не так?
Решение
Что происходит, когда i является 1?
if (i==0)
{...}
else
{
v.push_back(ret[i-1][j] + ret[i-1][j+1]);
}
ret[0] имеет один элемент, но ret[i-1][j+1] доступ ко второму элементу. Вероятно, он читает какую-то ненужную память и отбрасывает ваши расчеты.
Я бы порекомендовал заполнить треугольник 1по бокам вот так:
1 1 1
1 1 1 1
1 1 2 1 1
Таким образом, края не читаются в неинициализированной памяти.
Другие решения
Других решений пока нет …