剑指offer 62【Js】

分手后的思念是犯贱 2023-01-23 05:56 17阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]  
很有意思的一道题，暴力超时之后看到了一种巧妙地数学解法。

**约瑟夫环【逆推迭代】**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]

### `逆推公式：当前index = 上轮（index+m）% 剩余个数i` ###

/** * @param {number} n * @param {number} m * @return {number} */
    var lastRemaining = function(n, m) { 
        let index = 0;
        for(let i=2;i<=n;i++){ 
            index = (index+m)%i;
            console.log(index)
        }
        return index;
    };

时间复杂度 On  
空间复杂度O1

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70]: /images/20221004/93f5416523b240b183922c95a10bdde7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0Nsb3VkMTIwOQ_size_16_color_FFFFFF_t_70 1]: /images/20221004/dc20f280174b4353b474cb1e80ac2500.png

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

[剑指 Offer 62. 圆圈中最后剩下的数字][Offer 62.] 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除

Dear 丶/ 2023年10月02日 15:25/ 0 赞/ 26 阅读

相关剑指offer--62. 圆圈中最后剩下的数字

题目描述 0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。例如，0、1、2、3、4这5个数字组成

朱雀/ 2023年02月28日 05:37/ 0 赞/ 176 阅读

相关剑指offer 62【Js】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

分手后的思念是犯贱/ 2023年01月23日 05:56/ 0 赞/ 18 阅读

相关剑指offer 50【Js】

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

不念不忘少年蓝@/ 2022年10月20日 00:52/ 0 赞/ 108 阅读

相关剑指 Offer 62. 圆圈中最后剩下的数字

题目重述 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

深藏阁楼爱情的钟/ 2022年09月15日 13:56/ 0 赞/ 176 阅读

相关剑指Offer-62

题目：请实现两个函数，分别用来序列化和反序列化二叉树。实现 public class Solution62 { public stat

末蓝、/ 2022年06月09日 08:08/ 0 赞/ 179 阅读

相关剑指offer-题62：序列化二叉树

题目描述请实现两个函数，分别用来序列化和反序列化二叉树实验平台：[牛客网][Link 1] -------------------- 解决思路： ![这里

向右看齐/ 2022年05月26日 02:30/ 0 赞/ 174 阅读

相关剑指offer

[https://blog.csdn.net/u012193416/article/details/79253398][https_blog.csdn.net_u0121934

青旅半醒/ 2022年02月20日 16:21/ 0 赞/ 337 阅读

相关剑指offer（js版）

1. 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判

客官°小女子只卖身不卖艺/ 2021年11月23日 07:32/ 0 赞/ 295 阅读

相关剑指offer

[剑指offer][offer] https://www.cnblogs.com/gzshan/p/10910831.html [offer]: https://sun

亦凉/ 2021年09月21日 01:12/ 0 赞/ 403 阅读