问题简述
有m个人围成一圈参与游戏,其中死亡编号为n。从第一个开始报数,喊道n的人"死亡",求出最后一个死亡的人
解决思路
1th
数组:
创建一个初始化为0的数组,下标表示人的编号。0表示玩家仍旧存活,1代表玩家已经被淘汰出游戏 每次在n的编号做一个标记(把0改为1)
然而在带来一个问题!做死亡标记的人可能会对后面n的编号造成影响,当在遍历数组的时候,遇到死亡的玩家是不会有编号的。操作会带来一定的麻烦 我们需要一个变量来记录真正有效的编号 从而"报"我们的编号
2th
链表:
因为数组的插入与删除非常麻烦,我们不能对数组进行删除操作!那么我们可以用循环链表来实现,实现真正的删除,从而让我们报数操作更简单!
但是!问题又来了!我们在删除一个节点操作好像还挺多的,至少需要三个变量
一个变量用于指向删除节点以便free掉节点,一个变量用于遍历,另一个变量放在删除节点的前一节点以便删除操作。而且遍历指针向前走的步数变成n-1,整个操作下来,似乎操作复杂了许多,而且所占内存为原来的两倍。这个方法的逻辑思维比上面仅仅简单一些,但是操作和所占内存增加了!
3th
队列:
还记得上一篇所说的精心准备的数据组织方式能为我们带来处理问题的便利吗?观察问题,我们脑海可以想象出这是一个环,沿着一个方向,每走n步,消失一个节点。直到仅剩一个节点。
我们可以使用两个队列来解决这个问题!
队列具有先进先出( first in first out)的特点,可是我们怎么从一个方向走这个特点引出先进先出的特征呢。这里思维可能会有点绕,我们可以这样理解,我们每次数数会把数过的数扔了,挑出需要的数,但是我们还要再从扔过的数来继续数,直到手中仅剩一个数!
那么从扔过的数继续数的顺序是什么?便是先进先出!最先扔的,最先数!看到这里我们可以总结我们的方法了:
建立两个队列,其中一个队列为空;令一个队列装好我们元素。每次我们从待数数的队列pop三个元素,只有前两个元素会被push进另一个容器,直至数被数完。然后接着从已被放好的元素的队列继续数!直至只剩下一个元素。
这个方法让操作简洁许多,我们只需pop和push两个操作,而且花费内存也只是为数据大小的两倍,遍历次数比方法一要少很多(由于数组中死亡玩家不会被删除的原因)。最重要的是 思维难度一下子减少了许多!我们不必像数组考虑死亡人数导致我们可能会多走操作,也不必像链表那样关心删除和链接等操作,而且这种做法还有可能让我们走的步数改变,进而让思维混乱。
两个队列便让我们的方法更加的接近我们的正常思维,那就是每数n次扔掉一个数!而且delete pop push这三个操作的实现非常简单(delete只要pop但是不push便可以实现)
也许还有更快的算法,不需要我们一个个数出来,这应该需要用到数学知识,反正我不会QAQ
最重要的地方
在解决问题时,一定要关注问题的特性,符合问题中数据的特点来适当的组织我们的数据。选择合适的数据结构,这样更能为我们解决问题带来方便
从今天的案例我们可以知道 “ 精心准备的数据组织方式除了可以提高问题解决效率还可以再说 精心准备的数据组织形式也可以为我们的操作带来方便 ”