剑指offer:圆圈中最后剩下的数

题目:

0,1,…n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求出这个圆圈里剩下的最后一个数字。

思路:

1、环形链表模拟圆圈

创建一个n个节点的环形链表,然后每次在这个链表中删除第m个节点;

可以用std::list来模拟环形链表,list本身不是环形结构,因此每当迭代器扫描到链表末尾的时候,需要将迭代器移到链表的头部。

2、分析每次被删除的数字的规律,动态规划

下面来图文讲述第二种数学方法

剑指offer:圆圈中最后剩下的数
f(n,m)表示在0,1,2……,n-1中每次删除第m个数后最后剩下的那个数
参照书本一起食用更佳。