约瑟夫环——递推公式详解(leetcode 1823. 找出游戏的获胜者)

约瑟夫环——递推公式详解(leetcode 1823. 找出游戏的获胜者)

约瑟夫环问题

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知 n 个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从第一个人开始报数,数到 k 的那个人出圈;他的下一个人又从 1 开始报数,数到 k 的那个人又出圈;依此规律重复下去,直到剩余最后一个胜利者。

题目:1823. 找出游戏的获胜者

详解

解法有两种,模拟和递推;模拟往往是人们最容易想到的,可用多种数据结构来解决,代码放在了文末,本文着重讲解递推解法

问题

举个例子:n=10,k=3;总人数10人,数到3的人淘汰;

把这些人简单用编号表示 0 1 2…

表解

约瑟夫环——递推公式详解(leetcode 1823. 找出游戏的获胜者)_第1张图片

  • 看表,第一行是报数次序,最多报到3,所以3的那一列的编号都是报到3的,这些编号都会被淘汰。

  • 第二行,重新编号,意思是淘汰某人后,以此人的下一个人为起始,重新从0开始编号,这样做的原因后续来说。

  • 接下来的n-1行分别是,淘汰某人后的实际编号顺序

  • 现在来重新理解第二行,以淘汰第4人举例,淘汰后的实际人员编号为3 4 6 7 9 0,他们重新编号后的新编号分别对应 0 1 2 3 4。

  • 可以发现,每淘汰一个人后,相当于所有人向前移动k个单位

  • 重新编号的意义:

    0 1 2 3 4 5 6 7 8 9 淘汰一个后

    0 1   3 4 5 6 7 8 9 可见,若仍按这些编号组成一个环,之后就总需要考虑2号的空位问题,如何才能避免已经产生的空位对报数所造成的影响呢?答案:将这些号码重新编号,同时可以建立一种有确定规则的映射

    原始 0 1 2 3 4 5 6 7 8 9

    旧环 0 1   3 4 5 6 7 8 9

    新环 7 8   0 1 2 3 4 5 6

    新编的环有这么一个优势: 相比于旧环中2与4之间在数学运算上的不连续性,新环8和0之间在对9取余的运算中是连续的,也就是说根本不需要单独费心设计用以记录并避开已产生的空位(如 编号2)的机制 ,新环的运算不受之前遗留结果的掣肘。同时只要能将新环与旧环的映射关系逆推出来,就能利用在新环中的编号对应的旧环中的编号

    • 映射关系

    新环编号=(旧环编号-k)%旧总人数 得到的,所以旧环编号可以通过逆推得到:旧环编号=(新环编号+k)%旧总人数;

    还记得前面说的,每淘汰一个人后,相当于所有人向前移动k个单位吗,与这里的公式相呼应,(旧环编号-k)就是向前移动k个单位,那么(新环编号+k)不就是新环向后移动k个单位吗,不就正好还原回了旧环吗。如:

    原始 0 1 2 3 4 5 6 7 8 9

    旧环 0 1   3 4 5 6 7 8 9

    新环 7 8   0 1 2 3 4 5 6

    • 递推公式
      f ( n , k ) = ( f ( n − 1 , k ) + k )   m o d   n f(n,k)=(f(n-1,k)+k)\,mod\ n f(n,k)=(f(n1,k)+k)mod n

    f(n,k)表示,n个人,每报到k时淘汰此人,最终剩下的那个人的编号

    终于,通过这个公式我们现在用递归来进行解题,递归的出口是n=1,只剩下一个人,通过此人,可以通过递归的返回值,一层一层进行回代找到此人的实际编号。

  • 特别注意:为什么图解中的编号要从0开始呢?其实也与我们的递推关系有关,假设我们从1开始编号,k为奇数,那么当递归走到出口回代时,根据旧环编号=(新环编号+k)%旧总人数,知此时留下的最后一个人的上一次编号是(1+k)%2=0,即出现了0编号,出现了我们意想不到的编号,无法解答问题。所以根据取余的特性,编号要从0开始;如果非要从1开始也不是不可以,但代码实现就会有所不同。

递归解法

//编号从0开始
int f(int n, int k) {
     
    if (n == 1) return 0;
    return (f(n - 1, k) + k) % n;	
    //或
    //return n==1? 0:(f(n - 1, k) + k) % n;
}
int findTheWinner(int n, int k) {
     
    return f(n, k) + 1;		//这里需要注意:若题目给的编号是从1开始,最后的返回结果就需要+1,若从0开始就不用+1
}
//编号从1开始
int f(int n, int k) {
     
    if (n == 1) return 1;
    return ((f(n - 1, k) + k-1) % n)+1;	//相比上面的就会繁琐一些
}
int findTheWinner(int n, int k) {
     
    return f(n, k);		//这里需要注意:若题目给的编号是从1开始,最后的返回结果就需要+1,若从0开始就不用+1
}

迭代解法

int findTheWinner(int n, int k) {
     	//迭代其实就是从后往前推
    int value = 0;
    for (int i = 2; i <= n; i++)	//这里为什么要从2开始,还是要看递归,因为在递归回代的第一层n就是2
        value = (value + k) % i; 
    return value + 1;
}

模拟解法

此篇博文是在代码完成之后所写,而代码又是使用Cpp来写,所以我也就直接粘了过来,C用户及其他语言用户也可以理解自行编写相应代码。见谅!

//法一:利用list来进行快速的删除,当遍历到尾是要注意重新更改迭代器的指向,避免迭代器失效,整体类似一循环链表。
class Solution {
     
public:
	int findTheWinner(int n, int k) {
     
		list<int> li;
		//O(N)
		for (int i = 1; i <= n; i++) {
     
			li.push_back(i);
		}
		int cur = 1;
		auto it = li.begin();

		for (int i = 0; i < n - 1; i++) {
     
			cur = (k - 1)%li.size();	//对于k>>n的优化
			while (cur--) {
     
				if (it == li.end())
					it = li.begin();
				it++;
				
			}
			if (it == li.end())
				it = li.begin();
			auto tmp = ++it;
			li.erase(--it);
			it = tmp;
		}

		return li.front();
	}

};


//法二:利用双端队列,先全部入队、然后不断出队,对于没有报到k的再入队
class Solution {
     
public:
	int findTheWinner(int n, int k) {
     
		deque<int> de;

		for (int i = 1; i <= n; i++) {
     
			de.push_back(i);
		}
		int cur = 1;
		while (de.size() != 1) {
     
			cur = (k - 1) % de.size();
			while (cur--) {
     
				de.push_back(de.front());
				de.pop_front();
			}
			de.pop_front();

		}

		return de.front();
	}
};

//法三:vector数组
class Solution {
     
public:
	int findTheWinner(int n, int k) {
     
		vector<int> v(n);
		for (int i = 0; i < n; i++) {
     
			v[i] = i + 1;
		}

		int d = k - 1;
		int index = 0;
		while (v.size()>1)
		{
     
			int pos = (index + d) % v.size();
			v.erase(v.begin() + pos);
			index = pos;

		}
		return v[0];
	}
};
以上三种都是模拟,只是各自使用了不用的数据结构

你可能感兴趣的