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

【剑指 Offer 】62. 圆圈中最后剩下的数字

时间:2023-04-16 10:12:52浏览次数:44  
标签:下标 数字 删除 Offer int 存活 62 圆圈

【题目】

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

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

 

示例 1:

输入: n = 5, m = 3
输出: 3

示例 2:

输入: n = 10, m = 17
输出: 2

 

限制:

    1 <= n <= 10^5
    1 <= m <= 10^6

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

 

【思路】

约瑟夫环问题,我们直到最后一个情况下,存活数的下标一定是0,逆推找存活数在初始情况下的下标,就可以得到存活数。

每次删去的都是n%m位的数,根据方程f(n) = (f(n-1)+m)%n

推导出f(n)的结果,即为存活数的下标,也就是结果。

 

 

【代码】

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/End1ess/p/17322583.html

相关文章

  • 【剑指 Offer】 57 - II. 和为s的连续正数序列
    【题目】输入一个正整数target,输出所有和为target的连续正整数序列(至少含有两个数)。序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。 示例1:输入:target=9输出:[[2,3,4],[4,5]]示例2:输入:target=15输出:[[1,2,3,4,5],[4,5,6],[7,8]] 限制:   1<=target......
  • kuangbin专题一 简单搜索 起火迷宫(UVA-11624)
    Fire!DescriptionJoeworksinamaze.Unfortunately,portionsofthemazehavecaughtonfire,andtheownerofthemazeneglectedtocreateafireescapeplan.HelpJoeescapethemaze.GivenJoe’slocationinthemazeandwhichsquaresofthemazeareo......
  • 剑指 Offer 64. 求1+2+…+n
    题目链接:剑指Offer64.求1+2+…+n方法:逻辑运算符短路原则解题思路例如:对于表达式\(A&&B\),若\(A\)为\(false\),那么就不会计算\(B\);代码classSolution{public:intsumNums(intn){n&&(n+=sumNums(n-1));returnn;}};复杂度......
  • 集成电路IC(4Gbit)IS46TR16256BL-125KBLA1动态随机存取存储器
    IS46TR16256BL-125KBLA14GBitDDR3SDRAM提供紧凑型BGA-96封装的高速SDRAM。IS46TR16256BL具有256Mx16结构,电源电压为1.45V或1.3V,最大时钟频率为800MHz。该SDRAM具有8个内部银行并发操作和8nBit预取架构。IS46TR16256BL是电信和网络、汽车和工业嵌入式计算的理想选择。应用汽车;......
  • 剑指 Offer 60. n个骰子的点数
    题目链接:剑指Offer60.n个骰子的点数方法:动态规划解题思路\(n=1\)时可能的和为\([1,6]\),其概率为\(dp[1][]=[1/6,1/6,1/6,1/6,1/6,1/6]\)\(n=2\)时对于第一个骰子为\(1\)时,第二个骰子可以为\([1,6]\),其可以构成的和为\([2,7]\),分别为其中的和\([i+......
  • 【剑指 Offer 】14- I. 剪绳子
    【题目】给你一根长度为n的绳子,请把绳子剪成整数长度的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1]...k[m-1]。请问k[0]*k[1]*...*k[m-1]可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。示例1:输入:......
  • 【剑指 Offer】 66. 构建乘积数组
    【题目】给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B[i]的值是数组A中除了下标i以外的元素的积,即B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。示例:输入:[1,2,3,4,5]输出:[120,60,40,30,24]来源:力扣(LeetCode)链接:https://leetc......
  • Codeforces Round 628 (Div. 2) A-D
    CodeforcesRound628(Div.2)A.EhAbAnDgCdvoidsolve(){intn=read();for(inti=1;i*i<=n;i++){intg=__gcd(i,n-i);if(g*g+i*(n-i)==n*g){cout<<i<<""<<n-i<<endl;bre......
  • Codeforces Round 862 (Div. 2)
    Preface补题ing这场思路挺顺的,早上上课的时候口胡了前5题下午都一发写过了然后想了30min的F1也Rush出来了,不过F2还是有点仙的做不动A.WeNeedtheZeroSB题,首先判断是否所有数的异或和等于\(0\)若不为\(0\)且\(n\)为偶数则无解,否则答案就是这个异或和本身#include<cstdio......
  • 用 Go 剑指 Offer 56 - I. 数组中数字出现的次数
    一个整型数组nums里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。示例1:输入:nums=[4,1,4,6]输出:[1,6]或[6,1]示例2:输入:nums=[1,2,10,4,1,4,3,3]输出:[2,10]或[10,2]限制:2<=nums.length......