[実戦演習]Intel面接問題-入桟出桟順序問題

電話面接でC++、論理がはっきりしている問題を書くと、緊張するとうまく書けず、抜け穴だらけになります.以前はよく完璧なコンパイル環境でコードを書いていましたが、ホワイトボードに変えて書くと逆にうまく書けなくなり、いくつかの基礎的な間違いを犯しました.例えばstackの最初の要素はtop方法で、空がempty方法かどうかを判断し、方法の名前を書き間違えました.後で練習しなければなりません.くだらないことはあまり言わないで,直接テーマを見た.
 
タイトル:2つの配列、長さは同じで、すべてnで、2つの配列はそれぞれinseqとoutseqで、inseqを入桟の順序とするならばを求めて、outseqはその1つの出桟の順序であることができなくて、trueを返すかもしれません
サンプル:
inseq={1,2,3,4,5}outseq={5,4,3,2,1}はtrueを返します.
inseq={1,2,3,4,5}outseq={4,3,2,1,5}はtrueを返します.
inseq={1,2,3,4,5}outseq={2,3,5,1,4}でfalseを返します.
 
解題構想:プロセス全体をシミュレートし、inseqのデータをスタックに1つずつ入れる.スタックトップ要素とアウトスタックシーケンスoutseqが指す要素が同じになるまで、スタックを出てoutseqポインタを後ろに移動し、スタックトップ要素とoutseqポインタが指す要素が異なるまで、スタックに入ります.毎回ループの中で、スタックに入るか、スタックを出るか、いつも1つの動作が実行されなければならない.スタックもスタックに入らないと、必ず何か問題が発生し、直接ループを飛び出して、最後に判断する.コードは次のとおりです.

 1 #include <iostream>

 2 #include <stack>

 3 using namespace std;

 4 

 5 bool islegal(int *inseq, int *outseq, int n){

 6     if(n==0) return true;

 7     if(n==1) return inseq[0]==outseq[0];

 8     stack<int> st;

 9     

10     int i=0,j=0;

11     

12     bool flag = false; //          while         ，        ，         

13     while(j<n){

14         if((st.empty() || (st.top()!= outseq[j])) && i<n){//                        , i<n，   

15             st.push(inseq[i]);

16             i++;

17             flag = true;

18         }

19         if(!st.empty() && st.top()== outseq[j] ){//      ，                  ，   

20             st.pop();

21             j++;

22             flag = true;

23         }

24         if (!flag)

25             break;

26         else

27             flag = false;

28     }

29     if(st.empty() && j==n && i==n)

30         return true;

31     

32     return false; 

33 }

34 

35 int main(){

36     int a[] = {1,2,3,4,5};

37     int b[] = {4,3,5,2,1};

38     cout<<islegal(a,b,5);

39     system("pause");

40     return 0;

41 }