[关闭]
@songpfei 2016-03-23T12:13:10.000000Z 字数 1731 阅读 956

火车进站

OJ_算法


题目描述:

描述 给定一个正整数N代表火车数量,0 < N<10,接下来输入火车入站的序列,一共N辆火车,每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。
知识点
输出 有多组测试用例,每一组第一行输入一个正整数N(0< N<10),第二行包括N个正整数,范围为1到9。
输出 输出以字典序排序的火车出站序列号,每个编号以空格隔开,每个输出序列换行,具体见sample。
样例 3 1 2 3
样例输出 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1

分析:给定一个正整数N代表火车数量,0

样例输入:

3

1 2 3

样例输出:

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

解答:
  其实核心就是一个栈,对于第K个数,在第K个数进栈之前,前面的 K-1 个数要么全部出去了,要么都在栈里面,要么部分在栈里面部分出去了。那么可以假想,在第K个数入栈之前,依次从栈里面出去 0个、1个、2个……栈.size()个,然后把第K个入栈,再对于 K+1个同样实施这样的方法——这就是个递归了。

  出去了的保存在一个队列里面,没出站的保存在栈里面,最后一辆车处理完了递归结束并输出。

代码如下:

  1. #include<iostream>
  2. #include<stack>
  3. #include<vector>
  4. #include<algorithm>
  5. using namespace std;
  6. void train_out_orders(vector<int>& train, stack<int> s, vector<int> out, int cur_train, int n, vector<int*> &all_train_orders)
  7. {
  8. for (int i = s.size(); i >= 0; i--)
  9. {
  10. stack<int> stack_temp(s);
  11. vector<int> out_temp(out);
  12. for (int j = 1; j <= i; j++)//堆栈中,可以先出栈[0,s.size()个]到out_temp中,然后第cur_train辆车进站
  13. {
  14. out_temp.push_back(stack_temp.top());
  15. stack_temp.pop();
  16. }
  17. stack_temp.push(train[cur_train]);//第cur_train辆车进站
  18. if (cur_train == n - 1) //保存结果
  19. {
  20. int *train_out_temp = new int[n];
  21. int i;
  22. for (i = 0; i < out_temp.size(); i++)//已经出栈的车
  23. train_out_temp[i] = out_temp[i];
  24. for (; i < n; i++)//还在栈里边的车依次输出
  25. {
  26. train_out_temp[i] = stack_temp.top();
  27. stack_temp.pop();
  28. }
  29. all_train_orders.push_back(train_out_temp);
  30. }
  31. else
  32. train_out_orders(train, stack_temp, out_temp, cur_train+1, n, all_train_orders);
  33. }
  34. }
  35. int main()
  36. {
  37. int n;
  38. vector<int*> all_train_orders;
  39. vector<int> out_temp;
  40. stack<int> s;
  41. cin >> n;
  42. vector<int> train_in(n, 0);
  43. for (int i = 0; i < n; i++)
  44. cin >> train_in[i];
  45. train_out_orders(train_in, s, out_temp, 0, n, all_train_orders);
  46. for (size_t i = 0; i < all_train_orders.size(); i++)
  47. {
  48. for (int j = 0; j < n - 1; j++)
  49. cout << all_train_orders[i][j] << " ";
  50. cout << all_train_orders[i][n - 1] << endl;
  51. }
  52. return 0;
  53. }

参考文献1:http://www.cnblogs.com/jiayith/p/4414226.html(本文主要源自此文献)
参考2:http://blog.csdn.net/suifeng50/article/details/47070655(这个更简洁,但没有看懂)

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注