约瑟夫环问题
已知 n 个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出圈;他的下一个人又从 1 开始报数,数到 m 的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。
递归
假设f(n,m)
代表从长度为n的序列中,循环数到m就划掉,最终剩下来的元素
第一次划掉的元素应该就是第m个,但是因为m可能大于n,所以要取模
那么递归公式就是f(n,m)=m%n+f(n-1,m)
,即长度为n-1的序列中剩下的那个位置元素,再偏移我们第一次删除的位置(因为是接着重新数的)
当然,这个结果也可能会大于n,所以要模n
递归这个过程,当序列长度为1是,留下唯一的元素(下标为0)
class Solution {
public:
int lastRemaining(int n, int m) {
return f(n, m);
}
int f(int n, int m) {
if (n == 1) return 0;
int x = f(n - 1, m);
return (m + x) % n;
}
};
int main() {
Solution s;
cout << s.lastRemaining(10, 17);
return 0;
}
时间复杂度O(n)
:需要求解n个函数值
空间复杂度O(n)
:递归深度n,需要O(n)
的栈空间
迭代写法
class Solution {
public:
int lastRemaining(int n, int m) {
// 可以看作是自底向上推,长度为1已经知道了,返回下标为0
int f = 0;
// 一共有n个结果,去掉一个知道的,循环n-1次
// 但是这里i的初值必须注意…为什么初始是2…或者说:%i怎么理解?
for (int i = 2; i <= n; ++i) f = (m + f) % i;
return f;
}
};
模拟
说模拟会超时
标签:数到,return,递归,Offer,int,Solution,62,圆圈,长度 From: https://www.cnblogs.com/yaocy/p/16591635.html