新学期开始了,小哈是小哼的新同桌(小哈是个小美女哦~),小哼向小哈询问QQ号,小哈当然不会直接告诉小哼啦,原因嘛你懂的。所以小哈给了小哼一串加密过的数字,同时小哈也告诉了小哼解密规则。规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数再放到这串数的末尾,再将第5个数删除……直到剩下最后一个数,将最后一个数也删除。按照刚才删除的顺序,把这些删除的数连在一起就是小哈的QQ啦。现在你来帮帮小哼吧。小哈给小哼加密过的一串数是“6
3 1 7 5 8 9 2 4”。
其实解密的过程就像是将这些数“排队”。每次从最前面拿两个,第1个扔掉,第2个放到尾部。具体过程是这样的:刚开始这串数是“6 3 1 7 5 8 9 2 4”,首先删除6并将3放到这串数的末尾,这串数更新为“1 7 5 8 9 2 4 3”。接下来删除1并将7放到末尾,即更新为“5 8 9 2 4 3 7”。再删除5并将8放到末尾即“9 2 4 3 7 8”,删除9并将2放到末尾即“4 3 7 8 2”,删除4并将3放到末尾即“7 8
2 3”,删除7并将8放到末尾即“2 3 8”,删除2并将3放到末尾即“8 3”,删除8并将3放到末尾即“3”,最后删除3。因此被删除的顺序是“6 1 5 9 4 7 2 8 3”,这就是小哈的QQ号码了,你可以加她试试看^_^。
这是《啊哈!算法》中第2章第1节的内容,该题主要是说明队列容器的特性。
从deque的开始位置插入和删除元素的时间是固定的,而不像vector那样是线性时间,所以,如果多数操作发生在序列的起始和结束位置,则应考虑使用deque结构。
#include "stdafx.h" #include <iostream> #include <deque> using namespace std; void Show(deque<int> &values) { for (auto value : values) cout << value << " "; cout << endl; } int _tmain(int argc, _TCHAR* argv[]) { deque<int> values = { 6, 3, 1, 7, 5, 8, 9, 2, 4 }; Show(values); cout << endl; deque<int> s; while (!values.empty()) { s.push_back(values.front()); values.pop_front(); if (values.empty()) break; values.push_back(values.front()); values.pop_front(); } Show(s); system("pause"); return 0; }