网易有道2017内推编程题2

红太狼 2022-10-02 15:55 119阅读 0赞

**题目描述：**

小明同学把1到n这n个数字按照一定的顺序放入了一个队列Q中。现在他对队列Q执行了如下程序：  
while (!Q.empty()) //队列不空，执行循环

int x = Q.front(); //取出当前队头的值x

Q.pop(); //弹出当前队头

Q.push(x); //把x放入队尾

x = Q.front(); //取出这时候队头的值

printf("%d\\n", x); //输出x

Q.pop(); //弹出这时候的队头

做取出队头的值操作的时候，并不弹出当前队头。  
小明同学发现，这段程序恰好按顺序输出了1, 2, 3, ..., n。现在小明想让你构造出原始的队列，你能做到吗？\[注：原题样例第三行5有错，应该为3，以下已修正\]

输入描述:  
第一行一个整数T（T ≤ 100）表示数据组数，每组数据输入一个数n（1 ≤ n ≤ 100000），输入的所有n之和不超过200000。

输出描述 :  
对于每组数据，输出一行，表示原始的队列。数字之间用一个空格隔开，不要在行末输出多余的空格.

输入例子1 :  
4  
1  
2  
3  
10

输出例子1 :  
1  
2 1  
2 1 3  
8 1 6 2 10 3 7 4 9 5

**解题思路：**

方案一：

按照取出数据规则，每存一个数据，跳过一个空位置，在下一个空位置放置

方案二：

对比小明取出规则，反正存数据

**代码实现：**

**　　**

1 #include <iostream>
     2 #include <vector>
     3 #include <deque>
     4 using namespace std;
     5 
     6 
     7 int main()
     8 {
     9     int group;
    10     cin >> group;
    11     while (group--)
    12     {
    13         int n;
    14         cin >> n;
    15         
    16 
    17         //赋值方法一
    18         //vector<int>v(n, 0);
    19         //for (int ptr = -1, m = 1; m <= n; ++m)
    20         //{
    21         //    do
    22         //    {
    23         //        ++ptr;//跳过一个
    24         //        if (ptr >= n)
    25         //            ptr = 0;
    26         //    } while (v[ptr] != 0);
    27         //    do
    28         //    {
    29         //        ++ptr;//选择下一个
    30         //        if (ptr >= n)
    31         //            ptr = 0;
    32         //    } while (v[ptr] != 0);
    33         //    v[ptr] = m;            
    34         //}
    35         //赋值方法二
    36         deque<int> v;
    37         for (int i = n; i > 0; --i)
    38         {
    39             v.push_front(i);
    40             int t = v.back();
    41             v.pop_back();
    42             v.push_front(t);
    43         }
    44 
    45 
    46         for (auto a : v)
    47             cout << a << ' ';
    48         cout << endl;
    49     }
    50 
    51     return 0;
    52 }

转载于:https://www.cnblogs.com/zzw1024/p/10983905.html