【剣指Offerブラシ問題:JavaScript実現】スタックの圧入・ポップアップシーケンス
4630 ワード
リファレンスリンク
タイトル記述は2つの整数シーケンスを入力し、最初のシーケンスはスタックの圧入順序を表し、2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断します.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
問題を解く構想.は補助スタックを導入し、スタックに押し込まれた要素を補助スタックに順次押し込むと同時に、補助スタックのスタックトップ要素をポップアップスタックのシーケンスと比較し、等しい場合、補助スタックトップ要素をポップアップし、スタック操作を継続する責任を負う. 補助スタックが空の場合、ポップアップシーケンスが合法であることを示します.そうでなければ、合法ではありません.
コード実装
タイトル記述は2つの整数シーケンスを入力し、最初のシーケンスはスタックの圧入順序を表し、2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断します.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
問題を解く構想.
コード実装
function IsPopOrder(pushV, popV)
{
let stack=[];
if(pushV.length==0 || popV.length==0 || pushV.length!=popV.length){
return false;
}
let index=0;
for(let i=0;i<pushV.length;i++){
stack.push(pushV[i]);
while(stack.length>0 && stack[stack.length-1]==popV[index]){
stack.pop();
index++;
}
}
if(stack.length==0){
return true;
}else{
return false;
}
}