首页 > 其他分享 >约瑟夫环(动态规划):剑指 Offer 62. 圆圈中最后剩下的数字

约瑟夫环(动态规划):剑指 Offer 62. 圆圈中最后剩下的数字

时间:2023-05-31 09:56:53浏览次数:68  
标签:数字 删除 Offer int 剩下 约瑟夫 62 圆圈

题目描述:

0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

 解题思路:动态规划

 

 

 

 

根据状态转移方程的递推特性,无需建立状态列表 dp ,而使用一个变量 x 执行状态转移即可。

class Solution{
    public int lastRemaining(int n,int m){
        int x=0;
        for(int i=2;i<=n;i++){
            x=(x+m)%i;
        }
        return x;
    }
}

 

标签:数字,删除,Offer,int,剩下,约瑟夫,62,圆圈
From: https://www.cnblogs.com/zhz123567/p/17445193.html

相关文章

  • 约瑟夫环问题-hebust
    约瑟夫环问题-hebust约瑟夫环问题约瑟夫环是一个数学的应用问题:已知n个人(以编号a,b,c…分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。输入格式:固定为2行,第一行为m,......
  • 剑指 Offer 61. 扑克牌中的顺子
    题目描述:从若干副扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为0,可以看成任意数字。A不能视为14。 限制:数组长度为5 数组的数取值为[0,13].  方法:排序+遍历 classSolutio......
  • 剑指 Offer 58 - I. 翻转单词顺序
    题目描述:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"Iamastudent.",则输出"student.aamI"。  方法:分割+倒序  classSolution{publicStringreverseWords(Strings){......
  • poj 2362(剪枝)
    题意:给定一堆不定长度的小棒子,问他们能否构成一个正方形。解题思路:最开始写的时候把题意弄错了,以为只要能够从中取出一部分构成矩形即可。。。。这里注意一下几个剪枝的地方:1)要把所有的棒子都用上且组成正方形,那么sum%4=0;2)如果棒子长度小于4,肯定是不行的3)如果棒子中有长度大于s......
  • 剑指 Offer II 039. 直方图最大矩形面积
    题目链接:剑指OfferII039.直方图最大矩形面积方法:单调栈解题思路以直方图中的某一条为高的最大(面积)矩形的宽度为\(r-l+1\),其中\(r\)表示在其右边第一个小于(或等于)当前高度的下标,\(l\)表示在其左边第一个小于当前高度下标。\(l\),\(r\)可以利用单调栈在\(O(1)......
  • 动态规划:剑指 Offer 60. n个骰子的点数
    题目描述:把n个骰子扔在地上,所有骰子朝上一面的点数之和为s。输入n,打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案,其中第i个元素代表这n个骰子所能掷出的点数集合中第i小的那个的概率。 方法:动态规划     classSolution{pub......
  • upc 6621: HSI(数学期望,数学推导能力)
    6621:HSI时间限制:1Sec  内存限制:128MB提交:544  解决:112[提交][状态][讨论版][命题人:admin]题目描述Takahashiisnowcompetinginaprogrammingcontest,buthereceivedTLEinaproblemwheretheanswerisYESorNO.Whenhecheckedthedetaileds......
  • 剑指 Offer 06. 从尾到头打印链表
    剑指Offer06.从尾到头打印链表</br></br>题目:输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。示例:输入:head=[1,3,2]输出:[2,3,1]限制:0<=链表长度<=10000</br></br>思路一:使用reverse函数完成链表的逆序打印。我们通过遍历将链表中的值插......
  • 剑指 Offer 57 - II. 和为s的连续正数序列
    题目描述:输入一个正整数target,输出所有和为target的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。 方法:滑动窗口(双指针) classSolution{publicint[][]findContinuousSequence(inttarget){inti=1,j......
  • 【蓝桥杯集训·每日一题】AcWing 3625. 幂次方
    写在前面本人CSDN博客主页:这里一、题目1、原题链接3625.幂次方2、题目描述对任意正整数N,计算XNmod233333的值。输入格式共一行,两个整数X和N。输出格式共一行,一个整数,表示XNmod233333的值。数据范围1≤X,N≤109输入样例:25输出样例:32二、解题报告1、思路分析(1)快速幂模板题......