1、题目：环形单链表的约瑟夫问题

普通思路：时间复杂度O（n × m)

代码：

class Node:    def __init__(self,value):        self.value = value        self.next = Nonedef test(head,m):    if not head or head.next == head or m < 2:        return head    # last = head    # while last.next != head:    #     last = last.next    count = 2    node = head    while node.next != node:        if count == m:            # last = node.next            node.next = node.next.next            count = 1        node = node.next        count += 1    head.next = None    # head = node    return nodehead = Node(1)head.next = Node(2)head.next.next = Node(3)head.next.next.next = Node(4)head.next.next.next.next = Node(5)head.next.next.next.next.next = Node(6)head.next.next.next.next.next.next = Node(7)head.next.next.next.next.next.next.next = headm = 3test(head,m)

题目思路：时间O（n)：

　　每隔m个删除，超过n的大小，则取余来删除。

def delNum(arr,m):    if len(arr) < 1 or m < 1:        return    if len(arr) == 1:        return arr[0]    count = 0    while len(arr) != 1:        count += m        if count >= len(arr):            count %= len(arr)        print('删除:',arr[count])        arr.pop(count)    print(arr[0])arr = [0,1,2,3,4,5,6,7,8,9]m = 3delNum(arr,m-1)

 

递归思路：

从1人环的0计算到10人环，结果为4。转化公式：

 

由图知，10人环中最后入海的是4号，现由其在1人环中的对应编号0来求解。

公式：其中，m为报数值，i为第几轮。

 代码1：从n个数中求出最后只留下的值

def LastRemaining_Solution(self, n, m):        # write code here        if n <= 1 or m <= 0:            return -1        last = 0        for i in range(2,n+1):            last = (last + m) % i        return last

 代码2：忽略这个代码

class Node:    def __init__(self,value):        self.value = value        self.next = Nonedef josephus(head,m):    last = head    n = 1    while last.next != head:        last = last.next        n += 1    fn = 0    for i in range(2,n+1):        fn = (fn + m) % i    last = head    if fn > 1:        for i in range(fn-1):            last = last.next    pre = last.next     last.next = None    pre.next = pre    return prehead = Node(1)head.next = Node(2)head.next.next = Node(3)head.next.next.next = Node(4)head.next.next.next.next = Node(5)head.next.next.next.next.next = Node(6)head.next.next.next.next.next.next = Node(7)head.next.next.next.next.next.next.next = headm = 3josephus(head,m)

 

题目二：

　　题目思路：时间O（n)：

　　　　每隔m个删除，超过n的大小，则取余来删除。

　　代码：

def delNum(arr):    if len(arr) < 1:        return     if len(arr) == 1:        return arr[0]    count = 0    i = 1    while len(arr) != 1:        count += i        if count >= len(arr):            count %= len(arr)        print('删除:',arr[count])        arr.pop(count)        i += 1    print(arr[count])arr = [0,1,2,3,4,5,6,7,8,9]delNum(arr)