剑指Offer——圆圈中最后剩下的数字(JS实现) |刷题打卡

我心飞翔 分类:javascript

前言

掘金团队号上线,助你 Offer 临门! 点击 查看详情

题目描述

剑指Offer——圆圈中最后剩下的数字(JS实现) |刷题打卡

解题思路

  • 本题属于约瑟夫环问题,属于经典的数学问题
  • 解题的核心思路在于:定义一个下标指针,在于下面的这个式子:
  • head = (head + m - 1)% arr.length;

解题代码

var lastRemaining = function(n, m) {
    let arr = []
    for (let i = 0;i < n;i++) {
        arr.push(i);
    }
    let flag = 0;
    while (arr.length !== 1) {
        flag = (flag + m - 1) % arr.length;
        arr.splice(flag,1);
    }
    
    return arr[0];
};
 

总结

  • 本题属于一种数学题。
  • 关键点在于明确什么是约瑟夫环,以及删除第m个元素的下标是多少。
  • 核心公式:head = (head + m - 1)% arr.length

回复

我来回复
  • 暂无回复内容