啊哈算法之巧用队列解密QQ号
简述
本算法摘选自啊哈磊所著的《啊哈!算法》第二章第一节的题目——使用队列来解密举例中按照规则加密的QQ号。文中代码使用C语言编写,博主通过阅读和理解,重新由Java代码实现了一遍,意在深刻理解队列这一数据结构的特性和操作方法,并希望能够在这种数据结构的帮助之下,解决其他的类似的能够用队列来解决的问题。
算法题目
给一串加密过的数字,这串数字是美女的QQ号经过某种加密算法得到的,加密规则是这样的:首先将第1个数删除,紧接着将第2个数放到这串数的末尾,再将第3个数删除并将第4个数放到这串数的末尾,再将第5个数……直到剩下最后一个数,将最后一个数也删除,按照刚才删除的顺序,把这些删除的数连在一起就是加密之前的QQ号。现在希望你能够使用一种算法,解答出美女未加密之前的QQ号码。
解答思路
假设给定一个数组array存储这串数字,开始时array[0]删除掉并打印出来,于此同时后面的数字全部往前挪动一个位置,接着array[1]拿出来,array[2]及其以后的位置再往前挪动一个位置,再把array[1]的值加到数组的末尾去,显然,这种思想是对的,但是效率太低下了,能不能有种更好的思路来解决这种问题?
其实解密的过程就像排队一样,前面的先出来(删除),然后每次都有前面的数值往后排(插入到队尾),我们就将这种队形看做是一个队列,再引入两个整型变量head和tail作为队列的辅助指针,head用来指向队列的队首,tail用来指向队列的队尾(最有一个值)的下一个位置(没值),这样可以看到,当队首队尾相等时,说明队列为空。
从队列的角度我们再来看,假设QQ有9个数并放置在数组array构成的队列中,数组从0开始,那么head就指向了array[0]的位置,array[0, 8]共9个数就是有效的数字串,那么tail就指向了array[9]的位置。现在如果要从队列中删除一个数字,head++就实现了,这样head到tail之前仍然是我们想要的数字串;把新增的数字n放到末尾也很简单,只需要array[tail]=n然后tail++就行了,这样指针head和tail之间仍然是我们的数字串,理解起来应该很简单,下面我们通过代码来实现。
代码实现
1 public static void main(String[] args) { 2 3 // 假设如下9位QQ号 4 int[] qq = {6,3,1,7,5,8,9,2,4}; 5 6 // 使用数组模拟队列 7 int[] queue = new int[64]; 8 for(int i = 0; i < qq.length; i++) { 9 queue[i] = qq[i]; 10 } 11 12 // 头指针在数组第一个位置,尾指针在QQ号所在的最后一个位置即9 13 int head = 0, tail = 9; 14 15 while(head < tail) { 16 // 打印队首并将队首出队 17 System.out.print(queue[head] + " "); 18 head++; 19 20 // 将新队首的数添加到队尾,队尾指针再后移 21 queue[tail] = queue[head]; 22 tail++; 23 24 // 将队首出队 25 head++; 26 } 27 }
这里,我们大可以把队列进行封装处理,如下:
1 /** 2 * 自定义队列 3 */ 4 class MyQueue { 5 /** 6 * 数据列表 7 */ 8 int[] data = new int[64]; 9 /** 10 * 头指针 11 */ 12 int head; 13 /** 14 * 尾指针 15 */ 16 int tail; 17 18 public MyQueue() {} 19 20 public MyQueue(int head, int tail) { 21 this.head = head; 22 this.tail = tail; 23 } 24 }
大家可以试着将封装的队列类引入到上面的程序中来完成这个算法,比较简单这里就不再写了。
学习总结
队列是一种特殊的线性结构,它是由三个基本元素(一个数组,一个头指针和一个尾指针)封装成的一个结构体,它只允许在队列的首部(head)进行删除操作,这称之为“出队”,只允许在队列尾部(tail)进行插入操作,这称之为“入队”,当队列中没有元素时(即head==tail)则称之为空队列,队列的这种特性我们简单称为“先进先出(First In First Out, FIFO)”原则。
参考资料
1、《啊哈!算法》/ 啊哈磊著. 人民邮电出版社
相关文章