剣指offer-スタックの圧入、ポップアップシーケンス(pythonとc++)
8780 ワード
タイトルの説明
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
【考え方】補助的なスタックを借りて、スタックの順序を遍歴して、まず最初にスタックに入れて、ここは1で、それからスタックの上の要素がスタックの順序の最初の要素であるかどうかを判断して、ここは4で、明らかに1≠4なので、私たちはスタックを押し続けて、等しい後にスタックを出て、スタックの1つの要素を出て、スタックの順序を1位後ろに移動して、等しくないまで、このように循環等圧スタックの順序ループが完了し、補助スタックが空でない場合、ポップアップシーケンスがスタックのポップアップ順序ではないことを示す.
例:
インスタック1,2,3,4,5
出桟4,5,3,2,1
まず1は補助スタックに入り,このときスタックトップ1≠4はスタック2に続く.
このときスタックトップ2≠4は、スタック3に進みます
このときスタックトップ3≠4は、スタック4に進みます
このときスタックトップ4=4で、スタック4を出て、ポップアップシーケンスが1桁後ろに、このとき5で、補助スタックの中は1,2,3
このときスタックトップ3≠5は、スタック5に進み続ける
このときスタックトップ5=5で、スタック5を出て、ポップアップシーケンスが1桁後ろに、このとき3で、補助スタックの中は1,2,3
….
順番に実行し、最後の補助スタックは空です.空でない場合は、ポップアップシーケンスがスタックのポップアップ順序ではありません.
これは私が見たこの問題の最もはっきりした説明です.
下は直接コードをつけて、上は理解して、コードを見るのは簡単だと思います.
python
c++
コードの実现は何の区别もなくて、主に考え方です!!!
2つの整数シーケンスを入力します.最初のシーケンスはスタックの圧入順序を表します.2番目のシーケンスがスタックのポップアップ順序である可能性があるかどうかを判断してください.スタックに押し込まれたすべての数字が等しくないと仮定します.例えば、シーケンス1,2,3,4,5は、あるスタックの押し込み順序であり、シーケンス4,5,3,2,1は、そのスタックシーケンスに対応するポップアップシーケンスであるが、4,3,5,1,2は、そのスタックシーケンスのポップアップシーケンスであることは不可能である.(注:この2つのシーケンスの長さは等しい)
【考え方】補助的なスタックを借りて、スタックの順序を遍歴して、まず最初にスタックに入れて、ここは1で、それからスタックの上の要素がスタックの順序の最初の要素であるかどうかを判断して、ここは4で、明らかに1≠4なので、私たちはスタックを押し続けて、等しい後にスタックを出て、スタックの1つの要素を出て、スタックの順序を1位後ろに移動して、等しくないまで、このように循環等圧スタックの順序ループが完了し、補助スタックが空でない場合、ポップアップシーケンスがスタックのポップアップ順序ではないことを示す.
例:
インスタック1,2,3,4,5
出桟4,5,3,2,1
まず1は補助スタックに入り,このときスタックトップ1≠4はスタック2に続く.
このときスタックトップ2≠4は、スタック3に進みます
このときスタックトップ3≠4は、スタック4に進みます
このときスタックトップ4=4で、スタック4を出て、ポップアップシーケンスが1桁後ろに、このとき5で、補助スタックの中は1,2,3
このときスタックトップ3≠5は、スタック5に進み続ける
このときスタックトップ5=5で、スタック5を出て、ポップアップシーケンスが1桁後ろに、このとき3で、補助スタックの中は1,2,3
….
順番に実行し、最後の補助スタックは空です.空でない場合は、ポップアップシーケンスがスタックのポップアップ順序ではありません.
これは私が見たこの問題の最もはっきりした説明です.
下は直接コードをつけて、上は理解して、コードを見るのは簡単だと思います.
python
# -*- coding:utf-8 -*-
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
if not pushV or len(pushV) != len(popV):
return False
stack = []
for i in pushV:
stack.append(i)
while len(stack) and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if len(stack):
return False
return True
c++
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV)
{
if(pushV.size()==0)
return false;
int index=0; //popV
stack<int> s;
//
for(int i=0;i<pushV.size();i++)
{
s.push(pushV[i]);
while(s.empty()==false && s.top()==popV[index] && index<popV.size())
{
s.pop();
index++;
}
}
//
if(s.empty()==true)
return true;
else
return false;
}
}
コードの実现は何の区别もなくて、主に考え方です!!!