名企笔试：华为2016校招（删数）

1、 题目要求

 

有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

---

 

2、程序分析

 

题目的难点在于，到末尾时要循环至开头继续进行，这样，你很难用求模的思路来解题，第一轮时，利用求模尚且可以找到删除的点，但是循环至开头处以后，之前删掉的点你要做处理，才不会影响到下一轮的求模删点

 

既然问题出在循环上，那么就从循环至开头这个关键点来解题

将数组改造为一个循环链表，头部和尾部相连，这样，就完美的解决了到末尾时循环至开头继续进行这个难点，而解题的思路仍然是求模，来决定哪个点删除，由于是循环链表，因此本质上是没有头和尾的

---

 

3、 示例代码

 

#coding=utf-8

#节点
class Node(object):
    def __init__(self,index):
        self.pre = None
        self.index = index
        self.next = None

#循环链表
class Link():
    def __init__(self,count):
        self.count = count
        self.head = Node(0)
        self.current = self.head
        for i in range(count-1):
            node = Node(i+1)
            self.current.next = node
            node.pre = self.current
            self.current = node

        self.head.pre = self.current
        self.current.next = self.head

    #删除节点,interval是间隔
    def del_node(self,interval):
        self.current = self.head
        while self.count > 1:
            for i in range(interval):
                self.current = self.current.next
            self.delete(self.current)
            self.current = self.current.next

        return self.current.index

    def delete(self,node):
        node.pre.next = node.next
        node.next.pre = node.pre
        self.count -= 1

if __name__ == '__main__':
    link = Link(8)
    print link.del_node(2)