3-26 阿里笔试第二题

[Douc1998]

/**
 * 阿里 3.26 笔试第二题
 * n 个学生围成一圈报数，编号为 1 到 n，学生们从 1 开始依次报数，报到素数的学生出列，剩下的学生继续报。
 * 一直报数报到只剩一个学生时，停止报数，求解这个学生的编号。
 * ======================
 * 解题思路：模拟队列
 */

// 判读素数
function isPrime(num){
    if(num <= 1){
        return false;
    }
    for(let i = 2; i <= Math.sqrt(num); i++){
        if(num % i === 0){
            return false
        }
    }
    return true;
}


function getStudent(n){
    let students = new Array(n).fill(true);
    let num = 1; // 报数号码
    let loc = 0; // 当前报数学生的编号
    while(true){
        if(isPrime(num)){ // 判断素数
            students[loc] = false;
        }
        // 判断是否还剩一个学生
        if(students.filter(item => !!item).length === 1){
            return students.findIndex(item => !!item) + 1
        }
        // 寻找为 true 的下一个学生
        loc = (loc + 1) % n;
        while(!students[loc]){
            loc = (loc + 1) % n;
        }
        num++;
    }
}

console.log(getStudent(4)); // 4
console.log(getStudent(6)); // 4
console.log(getStudent(9)); // 1