剣指Offer-21.スタックの圧入、ポップアップシーケンス(Javascript)
4387 ワード
21.スタックの圧入、ポップアップシーケンス
「剣指Offer」ブラシのタイトルGitHubリンク
テーマリンク
テーマの説明
2つの整数系列を入力し、1番目のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込む数字はすべて等しくないと仮定する.例えば、シーケンス1,2,3,4,5は、あるスタックの圧入順序であり、シーケンス4,5,3,2,1は、このスタックシーケンスに対応する1つのポップアップシーケンスであるが、4,3,5,1,2は、このスタックシーケンスのポップアップシーケンスであることが不可能である.(注意:この2つのシーケンスの長さは等しい)
問題を解く構想
1つの配列を追加的に使用してスタックの役割を果たし、その後、スタックシーケンスのポップアップをシミュレートする.
pusshVサイクルを順番にこの配列に押し込んで、popVの要素と比較して、ポップアップ、popVの元素を後に移動して、比較を続けて、popVの元素が現在のスタックの最後の要素と一致しないまで、次のサイクルを行います.
このように、ループ終了後の配列には要素がなく、ポップアップシーケンスが正しいことを示しています.要素が残っている場合は、そのポップアップシーケンスが正しくないことを説明する.
コード
「剣指Offer」ブラシのタイトルGitHubリンク
テーマリンク
テーマの説明
2つの整数系列を入力し、1番目のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込む数字はすべて等しくないと仮定する.例えば、シーケンス1,2,3,4,5は、あるスタックの圧入順序であり、シーケンス4,5,3,2,1は、このスタックシーケンスに対応する1つのポップアップシーケンスであるが、4,3,5,1,2は、このスタックシーケンスのポップアップシーケンスであることが不可能である.(注意:この2つのシーケンスの長さは等しい)
問題を解く構想
1つの配列を追加的に使用してスタックの役割を果たし、その後、スタックシーケンスのポップアップをシミュレートする.
pusshVサイクルを順番にこの配列に押し込んで、popVの要素と比較して、ポップアップ、popVの元素を後に移動して、比較を続けて、popVの元素が現在のスタックの最後の要素と一致しないまで、次のサイクルを行います.
このように、ループ終了後の配列には要素がなく、ポップアップシーケンスが正しいことを示しています.要素が残っている場合は、そのポップアップシーケンスが正しくないことを説明する.
コード
function IsPopOrder(pushV, popV)
{
// write code here
var len = pushV.length;
if(len == 0){
return false;
}
var stack=[];
for(var i=0,j=0; i<len; i++){
stack.push(pushV[i]);
while(j < len && stack[stack.length-1] == popV[j]){
stack.pop();
j++;
}
}
if(stack.length == 0){
return true;
}else{
return false;
}
}