链表

100个小朋友成环报数,从1开始,小朋友编号为1-10, 报到含3或者3的倍数时站起来并且之后不会再报, 当最后一个小朋友站起来时,他的编号和报的数字是多少?

1、约瑟夫环问题

100个小朋友成环报数,从1开始,小朋友编号为1-10, 报到含3或者3的倍数时站起来并且之后不会再报, 当最后一个小朋友站起来时,他的编号和报的数字是多少?

1.1、数组下标方案

const arr = Array(10)
const key = 3


const numOfPeopleToLeave = arr.length - 1
let numOfPeopleLeaved = 0
let count = 0
let totalCount = 0
while (numOfPeopleLeaved < numOfPeopleToLeave) {
    for (let i = 0, len = arr.length; i < len; i++) {
        if (arr[i] === 1) {
            continue
        }
        count++
        totalCount++
        if (count === key) {
            arr[i] = 1
            numOfPeopleLeaved++
            count = 0
        }
    }
}
console.log(arr.findIndex((item) => item !== 1) + 1) // 4(第4个人是最后一个)
console.log(totalCount) // 27 最后一个人报的数字

1.2、链表方案

这题一般是要考链表(循环链表)。

如果是单向循环链表的话,对单个链表节点,有:

function Node (next) {
    this.next = next || null
}

每当计数计到3时,将当前node节点的上一个节点的next指向当前node节点的下一个节点,然后继续从1开始计数, 代码就不写了,虽说数据结构上和数组下标方案不同,计数规则的写法上是差不多的,while循环的终止条件可以换成当当前节点next指向null时。

2、合并两个排序链表

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

递归版本:

function merge(pHead1, pHead2) {
    let node = null;
    if (pHead1 === null) {
        return pHead2;
    } else if (pHead2 === null) {
        return pHead1;
    }

    if (pHead1.val >= pHead2.val) {
        node = pHead2;
        node.next = merge(pHead1, pHead2.next);
    } else {
        node = pHead1;
        node.next = merge(pHead1.next, pHead2);
    }
    return node;
}

非递归版本:

function merge(pHead1, pHead2) {
    if (pHead1 === null) {
        return pHead2;
    } else if (pHead2 === null) {
        return pHead1;
    }
    let node = null;
    let startNode = null;
    if (pHead1.val <= pHead2.val) {
        node = pHead1;
        startNode = pHead1;
        pHead1 = pHead1.next;
    } else {
        node = pHead2;
        startNode = pHead2;
        pHead2 = pHead2.next;
    }
    while (pHead1 !== null && pHead2 !== null) {
        if (pHead1.val <= pHead2.val) {
            node.next = pHead1;
            node = pHead1;
            pHead1 = pHead1.next;
        } else {
            node.next = pHead2;
            node = pHead2;
            pHead2 = pHead2.next;
        }
    }
    if (pHead1 !== null) {
        node.next = pHead1;
    } else if (pHead2 !== null) {
        node.next = pHead2;
    }
    return startNode;
}

参考资料

  1. 算法科普:什么是约瑟夫环:https://www.cxyxiaowu.com/1159.html
  2. 合并两个排序的链表——JS递归和非递归版本:https://blog.csdn.net/Jane_96/article/details/99612572

Was this helpful?

0 / 0

发表评论 0

Your email address will not be published. Required fields are marked *