剑指 小朋友圆圈
数字在升序数组中出现的次数
http://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2
通过环形链表模拟，解决这道题，时间复杂度O(mn),如果m,n太大，时间太长。
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
result=head=ListNode(0)
i=0
if n==0 or m==0:
return -1
while i<n:
node=ListNode(i)
head.next=node
head=head.next
i+=1
head.next=result.next
print(result)
count=1
p=result.next
pre=ListNode(-1)
while pre.val!=p.val:
while count<m:
pre=p
p=p.next
count+=1
pre.next=p.next
p=pre.next
count=1
return p.val if p.val else -1约瑟夫环问题, 当只有一个元素的时候，输出的元素是0，一直往上回溯的话，把当前0的坐标映射过去就可以得到结果。那么n-1轮的结果映射到n轮，需要(f(n-1)+m)%第n轮的数组长度。
# -*- coding:utf-8 -*-
class Solution:
def LastRemaining_Solution(self, n, m):
# write code here
# if n<=0 or m<=0:
# return -1
# x=0
# for i in range(2,n+1):
# x=(x+m)%i
# return x
if n<=0 or m<=0:return -1
if n==1:return 0
return ((self.LastRemaining_Solution(n-1,m)+m)%n)%(1e7+9)
