首页 > 其他分享 >剑指Offer-62-圆圈中最后剩下的数字

剑指Offer-62-圆圈中最后剩下的数字

时间:2022-08-16 15:11:06浏览次数:72  
标签:数到 return 递归 Offer int Solution 62 圆圈 长度

约瑟夫环问题

已知 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

相关文章

  • 阿里工作8年,肝到P7就剩这份学习笔记了,已助朋友拿到10个Offer
    在阿里工作了8年,工作压力大,节奏快,但是从技术上确实得到了成长,尤其是当你维护与大促相关的系统的时候,熬到P7也费了不少心思,小编也是个爱学习的人,把这几年的工作经验整理成......
  • 2022-8-16 剑指offer-二叉树
    剑指OfferII053.二叉搜索树中的中序后继难度中等57收藏分享切换为英文接收动态反馈给定一棵二叉搜索树和其中的一个节点 p ,找到该节点在树中的中序后继。如果......
  • 洛谷 P6242 【模板】线段树 3 吉司机线段树 区间取最小值 维护历史最大值和区间和
    题目背景本题是线段树维护区间最值操作与区间历史最值的模板。题目描述给出一个长度为 nn 的数列 AA,同时定义一个辅助数组 BB,BB 开始与 AA 完全相同。接下来......
  • 洛谷P2622 关灯问题II引发的关于DP实现形式及后效性的思考
      动态规划要求已经求解的子问题不受后续阶段的影响,即无后效性。而在这种递推的实现方式中,后面枚举的状态可能更新前面已经枚举过的状态。也就是说,这种递推的实现方式是......
  • 【WPF】XDG0062 必须使“Setter.Property”具有非 null 值。
    编译环境vs2022.net6.0在样式中给附加属性设置触发条件。显示XDG0062错误,但是代码能正常编译和运行。   编辑环境中运行后,能正常运行   解决方法......
  • 62
    search搜索   shareholder股东fifteen十五ill病的twelve十二practise练习produce生产point要点traffic交通explain解释their他们的 ......
  • 剑指 Offer 07. 重建二叉树
    1.题目:输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例1:  Input:pre......
  • AcWing周赛62-64 中比较有意思的小题题解
    AcWing周赛62-64(选讲)感觉比较思维4502.集合操作https://www.acwing.com/problem/content/4505/根据题意,肯定要使得所取的最大值最大,平均值最小。又因为每次放进来的的......
  • [POI2006]Pro-Professor Szu & ZLOJ 练习62 B
    writtenon2022-08-09题目不难,但是需要总结一下。题意很明确,就不过多阐述了。读完题目后,很明显可以建反图,然后就会有两种方法。第一种方法是直接拓扑排序找环,这种方式......
  • P8245 [COCI2013-2014#3] PAROVI & ZLOJ 练习62 D
    writtenon2022-08-09一道有趣的计数题。首先题面中最引人注目的就是两个整数的数据范围。很显然,暴力的思路,枚举所有数,找出每一位上每一种数字的个数这种方法是不可行......