パスカルの三角関係
18634 ワード
問題声明
整数numrowsを与えられて、Pascalの三角形の最初のnumrowsを返します.
Pascalのトライアングルでは、それぞれの数値は、示されているように2つ以上の数値の合計である
からの問題文 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
解説
ブルートフォースアプローチ
簡単な方法は2ループを走らせ,内ループにおける二項係数の値を計算することである.
例えば、第1のラインは1、第2のラインは1、第3のラインは11、1を有する.など.行のすべてのエントリは二項係数の値です.行番号行のi番目のエントリの値は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)余剰空間)
Pascal三角形を見ると、すべてのエントリがその2つの値の合計であることがわかります.そこで、以前に生成された2 D配列を作成しました
値.
上記のロジックの小さな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)余剰空間)
このアプローチは、ブルートフォースアプローチに基づいています.i番目のエントリの2項係数をc(line,i)とし、全ての行は値1から始まる.ここでの考えはC ( line , i - 1 )をC ( line , i - 1 )を使って計算することです.これは、(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<vector<int>> result
- loop for line = 1; line <= n; line++
- initialize vector<int> 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<vector<int>> generate(int numRows) {
vector<vector<int>> result;
for (int line = 1; line <= numRows; line++){
vector<int> 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
}
ジャバスクリプト
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<vector<int>> result
Step 2: loop for line = 1; line <= numRows
1 <= 3
true
initialize vector<int> 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<int> 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<int> 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]].
Reference
この問題について(パスカルの三角関係), 我々は、より多くの情報をここで見つけました https://dev.to/_alkesh26/leetcode-pascal-s-triangle-2l0kテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol