プログラミングの美しさの経典の問題を覚えて、最も長い上昇のサブシーケンスの問題.
**無秩序な整数配列を指定し、その中で最も長い上昇サブシーケンスの長さを見つけます.例:入力:[10,9,2,5,3,7101,18]出力:4説明:最も長い上昇サブシーケンスは[2,3,7101]であり、その長さは4である.**
この問題は、leetcodeを塗ったときに出会ったもので、プログラミングの美しさで出会ったことを思い出して、思い切って携帯電話のPDFをめくって、上の方法で私のコードを一歩一歩コードしました.プログラミングの美しさの構想は3つのステップに分けられる:1.最も基本的なアルゴリズムを提案したのは線形ネスト遍歴であり,各インデックスに対する最長男シーケンスの長さを表すLIS配列を維持することである.それを更新する方法はforです(int i=0;i 2.さらに最適化を考えると、同じ長さのサブシーケンスが複数ある可能性があり、同じ長さですべてのサブシーケンスと比較する必要はありません.これらのサブシーケンスの末尾値が最も小さいシーケンスと比較するだけでいいので、もう1つの配列maxV、maxV[i]を維持する必要があります.長さiのサブシーケンスの最大値を表す最小値(ここでは少し回りますが、よく考えてから下を見ます).この配列があれば、私たちの第2の遍歴は0-iからではなく、遍歴maxVに変更すればいい.maxVの長さはmaxLenまでで、maxLenは肯定<=numsである.size()なので,これで判断回数は減少したが,テーマはO(N^2)の複雑さであり,まだ少し肋骨を見せている.3.maxVの法則を探究してmaxVを研究した後、maxVは増加しなければならないと結論することができます!どうしてですか.imaxV[j]なら話が通じないからです.maxV[3]=3を仮定します.では、maxV[2]の値を求めます.このmaxV[2]は最も役に立たないし、3よりも小さくなければなりません.maxV[3]のこのシーケンスからサブシーケンスを再分割することができるからです.つまり、iでも!!!私がずっとプログラミングの美しさのリングにボタンを入れて、漸進的に心を傾けていたとき、leetcodeの解法が私をひどく目覚めさせた.プログラミングの美しさの方法はテストの用例を通じてすべて4 msを要して、コードの量も十数行を要して、leetcodeの上で第1位の解法は意外にも0 msで通過することができて、最も肝心なのは、そのコードの行数、1桁しかありません!!!プログラミングの美しさは私の心の中の地位が完全に崩れて、后で、leetcodeは私の心の中の神です..プログラミングの美しさ、おじいさん...私はあなたを熟読することを誇りに思ってそんなに長い間..プログラミングの美解法4 ms
leetcode第一解法0 ms
この問題は、leetcodeを塗ったときに出会ったもので、プログラミングの美しさで出会ったことを思い出して、思い切って携帯電話のPDFをめくって、上の方法で私のコードを一歩一歩コードしました.プログラミングの美しさの構想は3つのステップに分けられる:1.最も基本的なアルゴリズムを提案したのは線形ネスト遍歴であり,各インデックスに対する最長男シーケンスの長さを表すLIS配列を維持することである.それを更新する方法はforです(int i=0;i 2.さらに最適化を考えると、同じ長さのサブシーケンスが複数ある可能性があり、同じ長さですべてのサブシーケンスと比較する必要はありません.これらのサブシーケンスの末尾値が最も小さいシーケンスと比較するだけでいいので、もう1つの配列maxV、maxV[i]を維持する必要があります.長さiのサブシーケンスの最大値を表す最小値(ここでは少し回りますが、よく考えてから下を見ます).この配列があれば、私たちの第2の遍歴は0-iからではなく、遍歴maxVに変更すればいい.maxVの長さはmaxLenまでで、maxLenは肯定<=numsである.size()なので,これで判断回数は減少したが,テーマはO(N^2)の複雑さであり,まだ少し肋骨を見せている.3.maxVの法則を探究してmaxVを研究した後、maxVは増加しなければならないと結論することができます!どうしてですか.i
int lengthOfLIS(vector<int>& nums) {
if(nums.empty())
return 0;
int n=nums.size();
vector<int>LIS(n,1);
vector<int>maxV{INT_MIN,nums[0]};
int maxLen=1;
for(int i=1;ivector<int>::iterator iter=lower_bound(maxV.begin(),maxV.end(),nums[i]);
int j=distance(maxV.begin(),iter);
LIS[i]=j;
if(LIS[i]>maxLen){
maxLen=LIS[i];
maxV.push_back(nums[i]);
}else if(maxV[j]>nums[i]){
maxV[j]=nums[i];
}
}
return maxLen;
} leetcode第一解法0 ms
int lengthOfLIS(vector<int>& nums){
vector<int> dp;
for (int i = 0; i < nums.size(); ++i){
auto it = lower_bound(dp.begin(), dp.end(), nums[i]);
if (it == dp.end())
dp.push_back(nums[i]);
else
*it = nums[i];
}
return dp.size();
}