孩子们的游戏(圆圈中最后剩下的数)--JavaScript

JavaScript三种解法

1.数学公式法（老实讲这个方法我没有仔细研究，参考大神）

2.数组模拟法

思路：用一个数组装上小朋友，【0，1，2，3，4，5】，
从-1开始计数，直到发现那个小朋友，将它出列，将它后面的小朋友放到队伍前，前面的放在后。重新计数。
如 m=4 3出列 新队伍[4,5,0,1,2]

3.环形链表法

思路：将小朋友装入一个头尾衔接的链表。 遇到满足条件的删除节点即可。

//1.数学公式法
function LastRemaining_Solution(n,m){
    if(n==0||m==0)return -1;
    let s=0;
    for(let i=2;i<=n;i++)
    {
        s=(s+m)%i;
    }
    return s ;
}


//2.数组模拟法
function LastRemaining_Solution(n, m)
{
    if(n<1||m<1) return -1
    let kid =[]
    for (let i=0;i<n;i++){
        kid[i] = i
    }
    let count = -1
    while (kid.length>1){
        for (let i=0;i<m;i++){
            count++
            if(count === kid.length) count=0
        }
        kid = kid.slice(count+1,kid.length).concat(kid.slice(0,count))
        count = -1
    }
    return kid[0]
}


//3.环型链表法
function List(val) {
    this.val = val
    this.next = null
}

function LastRemaining_Solution(n, m) {
    if (n < 1 && m < 1) return -1
    let head = new List(0)  //创建头节点
    let node = head
    for (let i = 1; i < n; i++) {
        node.next = new List(i)
        node = node.next
    }
    node.next = head   //头尾衔接
    let count = -1   //从-1计数
    while (head.next !== head) {  //只剩一个节点
        if (++count === m - 2) {   //叠加计数，直到在目标节点的父节点停下
            head.next = head.next.next  //拆链 ，把目标节点父节点的next赋值给目标节点的子节点
            count = -1
        }
        head = head.next
    }
    return head.val
}