孩子们的游戏,圆圈中最后剩下的数字。n 个小朋友,从 0 开始编号到 n-1,每次都删除第 m 个小朋友。其中删除以后从被删除结点的下一个结点开始从 0 开始编号。最后只剩下一个小朋友时游戏结束,这个小朋友的编号是多少?
循环链表模拟游戏过程。可以自己实现循环链表结构,也可以直接是用 C++ 的 list 来模拟循环链表。其中使用链表结构而不是数组结构是因为要保证删除/移动的时间复杂度为O(1)。空间复杂度:O(n);时间复杂度:每次删除 1 个结点,需要删除 n-1 个结点,每删除一个结点需要循环 m 次,则复杂度为 O(n*m)。
注意:分析时间复杂度时要结合使用的语言和数据结构的特性
c++ 中的 list 结构虽然能保证增加和删除节点的操作在常数时间内完成,但获取链表长度的操作确是线性的复杂度。为了避免这样的复杂度,在代码实现时候应该避免使用这个耗时的操作。list 中剩下最后一个结点,也就意味着我们要删除 n-1 个结点,使用 for 循环控制 n-1 次删除操作,而不是检查当前 list 的 size,以保证高效型。
从数学的角度可以让求解更高效,下面将是比较复杂的分析推理过程。最优解,时间复杂度O(n),空间复杂度O(1)。
假设有关于 n 和 m 的函数 f(n, m),表示从 n 个数字,seq=(0,1,..,n-1),开始,每次删除第 m 个数字后最后剩下的数字。
第一次删除操作:
删除的数字为 k = (m-1)%n
剩下的序列为 ,共 n-1 个数字,根据游戏规则重新调整得到序列 seq' = (k+1,...,n-1,0,1,..,k-1),即从被删除的下一个结点开始编号,将 k+1 放到了序列的第一个位置。
值得注意的是 seq' 与 seq 的形式不同,假设有新的关于 n 和 m 的函数 f'(n-1, m),表示从 seq' 开始,每次删除第 m 个数字后最后剩下的数字
综上必然有:f(n,m) = f'(n-1,m)
f' 函数是否与 f 函数有什么关系呢???
对 seq' 重新编号:
seq' | k+1 | k+2 | ... | n-1 | 0 | 1 | ... | k-1 |
y=seq'-k-1 | 0 | 1 | ... | n-k-2 | -k-1 | -k | ... | -2 |
seq''=y%n | 0 | 1 | ... | n-k-2 | n-k-1 | n-k | ... | n-2 |
细节:
seq' 有 n-1 个数,对应编号为 0,..,n-2。k+1 编号为 0,也就是以 k+1 为基准对序列重新编号,那么对于序列中的任意一个数 x,编号为 y = x-(k+1) = x-k-1。
当 x 取 [0,..,k-1] 时,y 为负数,对 n 取模,可以将数映射到 [0,n] 的范围内,并保证新序列依旧有序。
综上:从 f' 函数中的序列 seq' 进行映射 g(x) = (x-k-1)%n,可以得到类似 seq 的序列 seq''=(0,1,..,n-2),是 f(n,m) 的子问题 f(n-1,m)。
g(x) = (x-k-1)%n 的逆映射为 g'(x) = (x+k+1)%n。(可以将这一过程想象成循环移位的过程也就好理解了,原的映射是在 x 的基础上向左边循环移 (k+1)位,那么逆过程就是在原来的基础上向右循环移 (k+1),左移为“减”,右移为“加”)。
根据 g(x) 和 g'(x) 我们可以将 f 和 f' 联系起来
- f(n,m) = f'(n-1,m)
- = g'(f(n-1, m)) ..... f'(n-1,m) = f(n-1,m),参考上文分析
- = [f(n-1, m)+k+1]%n ...... f(n-1,m) 带入 g'
- = [f(n-1, m)+(m-1)%n+1]%n ...... k = (m-1)%n 带入
- = [f(n-1, m)+m]%n
细节,[f(n-1, m)+(m-1)%n 1]%n 的展开:
由题目肯定有:0<=f(n-1, m)<=n-1,可以写成 f(n-1, m)%n,显然有 1 = 1%n
则有:[f(n-1, m)+(m-1)%n 1]%n = [f(n-1, m)%n (m-1)%n 1%n]%n = [f(n-1, m)+(m-1)+1]%n = [f(n-1, m)+m]%n
综上可以得到递归式:
当 n > 1 时: f(n,m) = [f(n-1, m)+m]%n
当 n = 1 时: f(n,m)=0。
接下来的代码就好实现了。
总体思路:将问题抽象成函数表达式,问题拆解,能否找到重叠子问题,递归求解?
注意不合法情况,即边界条件的检查
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <list>
- using namespace std;
- class Solution{
- public:
- int LastRemaining_Solution(int n, int m){
- //return LastRemainingList(n, m);
- return LastRemainingDynamic(n, m);
- }
- // time-O(m*n), spcae-O(n)
- int LastRemainingList(int n, int m){
- if(n <= 0 || m <= 0)
- return -1;
- list<int> children;
- for(int i=0; i<n; i++){// no. from 0 to (n-1)
- children.push_back(i);
- }
- auto it = children.begin(); // no. 0
- for(int k=0; k<n-1; k++){
- // Note: while(children.size() > 1) is not appropriate, because the complexity of children.size() is up to linear
- // until now, it point to the 0-th child
- for(int i=1; i<m; i++){ // loop from th 1-th child to m-1
- it++;
- if(it == children.end())
- it = children.begin();
- }
- // until now, it point to the (m-1)-th child
- it = children.erase(it); // erase will return the following iterator
- if(it == children.end())
- it = children.begin();
- }
- return children.front();
- }
- // time-O(n), space-O(1)
- int LastRemainingDynamic(int n, int m){
- if(n<=0 || m<=0)
- return -1;
- int f = 0; // f[1,m] = 0
- for(int i=2; i<=n; i++){
- // calculate f[i,m]
- f = (f+m)%i;
- }
- return f;
- }
- };
- int main()
- {
- return 0;
- }
来源: http://www.cnblogs.com/fanling999/p/7787213.html