剑指offer:圆圈中最后剩下的数
题目:
0,1,…n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字,求出这个圆圈里剩下的最后一个数字。
思路:
1、环形链表模拟圆圈
创建一个n个节点的环形链表,然后每次在这个链表中删除第m个节点;
可以用std::list来模拟环形链表,list本身不是环形结构,因此每当迭代器扫描到链表末尾的时候,需要将迭代器移到链表的头部。
2、分析每次被删除的数字的规律,动态规划
下面来图文讲述第二种数学方法
f(n,m)表示在0,1,2……,n-1中每次删除第m个数后最后剩下的那个数
参照书本一起食用更佳。