Leetcode問題解シリーズ--300.Longest Increasing Subsequenceと673.Number of Longest Increasing Subsequenc(c++版)
17584 ワード
タイトルリンク:300.Longest Increasing Subsequence
最长の长男の序列を増やして、これは1本の経典のダイナミックな计画の问题です.一連の数字の最長増長長長長シーケンスの長さを出力することが要求される.
成長サブシーケンスはnums[i]注意点:動的計画を使用する場合、シーケンス長の初期値は1ですか、0ですか. 配列長が0であると判断した場合に注意する.
一.アルゴリズムせっけい
ここには2つの時間複雑度の解法がある.
1.O(n 2 n^2 n 2)の方法.
各配列の値について、前にそれより小さい値があるかどうかを確認し、ある場合は、現在のシーケンス長を前のシーケンス長+1に変更し、最後にlenの最大値、すなわちその配列の最長の長男シーケンス長を出力します.
n個の状態を持つため,各状態遷移にはO(n)が必要であり,全時間複雑度はO(n 2 n^2 n 2)であった.
2.O(nlogn)の方法
二分探索と貪欲アルゴリズムの結合を用いて実現した.問題はサブシーケンスの具体的なシーケンスを出力する必要がなく,出力長だけが必要であるため,増分サブシーケンスの最後の数の最小値を探すたびにresに入れることができ,これが貪欲な考えである.
この長さiの最小値を探すたびに、後でこの数よりも大きな値を探す空間が増えることを保証するので、必ず長男シーケンスを見つけることができます.
一方,検索時に二分検索を用いると,検索の時間的複雑さを低減できる.
従って最後の総時間複雑度はO(nlogn)である
二.コード実装
O(n 2 n^2 n 2)複雑度アルゴリズム例
O(nlogn)複雑度アルゴリズムの例
三.アルゴリズム変形
このアルゴリズムにより,最長男シーケンスの個数を算出することもできる.
タイトルリンク:673.Number of Longest Increasing Subsequence
このとき,第1のO(n 2 n^2 n 2)のアルゴリズムを用いなければならないが,O(nlogn)のアルゴリズムを用いることはできない.O(nlogn)のアルゴリズムは,最長子シーケンスの長さを探し出し,各位置の最小値を保存するだけで,すべてのサブストリングを探し出すことができないからである.
最も長い文字列が何個あるかを統計します.つまり、各位置にどれだけの数字が拡張できるかを見つけます.
したがって、状態ans[i]は、現在のi位置が、最長の増分子シーケンスに達する方法の個数を定義することができる.
次のノードが最初に長さに到達しない場合は、ans[i]+=ans[j]を生成する新しいパスがあることを示します.ノードが最初に最長に到達した場合、前のans[i]はans[i]=ans[j]に到達する道が1つしかないことを示します.
最後に,最大サブシーケンス長に等価な最後の要素のすべての下付きスケールのみが必要であり,これらの最後の数値の下付きスケールのans値を重畳することによって最長サブシーケンスの個数が得られる.
最长の长男の序列を増やして、これは1本の経典のダイナミックな计画の问题です.一連の数字の最長増長長長長シーケンスの長さを出力することが要求される.
成長サブシーケンスはnums[i]
一.アルゴリズムせっけい
ここには2つの時間複雑度の解法がある.
1.O(n 2 n^2 n 2)の方法.
各配列の値について、前にそれより小さい値があるかどうかを確認し、ある場合は、現在のシーケンス長を前のシーケンス長+1に変更し、最後にlenの最大値、すなわちその配列の最長の長男シーケンス長を出力します.
n個の状態を持つため,各状態遷移にはO(n)が必要であり,全時間複雑度はO(n 2 n^2 n 2)であった.
2.O(nlogn)の方法
二分探索と貪欲アルゴリズムの結合を用いて実現した.問題はサブシーケンスの具体的なシーケンスを出力する必要がなく,出力長だけが必要であるため,増分サブシーケンスの最後の数の最小値を探すたびにresに入れることができ,これが貪欲な考えである.
この長さiの最小値を探すたびに、後でこの数よりも大きな値を探す空間が増えることを保証するので、必ず長男シーケンスを見つけることができます.
一方,検索時に二分検索を用いると,検索の時間的複雑さを低減できる.
従って最後の総時間複雑度はO(nlogn)である
二.コード実装
O(n 2 n^2 n 2)複雑度アルゴリズム例
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
int _size = nums.size();
int count = 1;
int len[10000] = {0};
// 1
fill(len,len+_size,1);
for(int i = 1; i < _size; i++){
for(int j = 0; j < i; j++){
if(nums[j] < nums[i]){
len[i] = max(len[i], len[j]+1);
}
}
count = max(count,len[i]);
}
return count;
}
};
O(nlogn)複雑度アルゴリズムの例
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> res;
for(int num:nums){
// res num
auto it = lower_bound(res.begin(), res.end(), num);
// ，
if(it == res.end()){
res.push_back(num);
}
// ， num
else{
*it = num;
}
}
// ，res
// size
return res.size();
}
};
三.アルゴリズム変形
このアルゴリズムにより,最長男シーケンスの個数を算出することもできる.
タイトルリンク:673.Number of Longest Increasing Subsequence
このとき,第1のO(n 2 n^2 n 2)のアルゴリズムを用いなければならないが,O(nlogn)のアルゴリズムを用いることはできない.O(nlogn)のアルゴリズムは,最長子シーケンスの長さを探し出し,各位置の最小値を保存するだけで,すべてのサブストリングを探し出すことができないからである.
最も長い文字列が何個あるかを統計します.つまり、各位置にどれだけの数字が拡張できるかを見つけます.
したがって、状態ans[i]は、現在のi位置が、最長の増分子シーケンスに達する方法の個数を定義することができる.
次のノードが最初に長さに到達しない場合は、ans[i]+=ans[j]を生成する新しいパスがあることを示します.ノードが最初に最長に到達した場合、前のans[i]はans[i]=ans[j]に到達する道が1つしかないことを示します.
最後に,最大サブシーケンス長に等価な最後の要素のすべての下付きスケールのみが必要であり,これらの最後の数値の下付きスケールのans値を重畳することによって最長サブシーケンスの個数が得られる.
class Solution {
public:
int findNumberOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
int _size = nums.size();
int max_len = 1;
int count = 0;
int len[10000] = {0};
int ans[10000] = {0};
fill(ans,ans+_size,1);
fill(len,len+_size,1);
for(int i = 1; i < _size; i++){
for(int j = 0; j < i; j++){
if(nums[j] < nums[i]){
//
if(len[i] == len[j]+1){
ans[i] += ans[j];
}
//
else if(len[i] < len[j]+1){
len[i] = len[j]+1;
ans[i] = ans[j];
}
}
}
max_len = max(max_len,len[i]);
}
for(int i = 0; i < _size; i++){
if(len[i] == max_len) count += ans[i];
}
return count;
}
};