有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。 java
时间: 2023-06-09 21:04:24 浏览: 110
好的,我明白了。这个问题可以使用环形链表来模拟圆圈的情况。具体的解法如下:
1.先创建一个带有 n 个节点的环形链表,编号从 1 到 n。
2.从第一个节点开始遍历链表,同时计数,如果当前节点是第 3 个需要退出的节点,则将该节点从链表中删除。
3.重复步骤 2 直到链表中只剩下一个节点为止,该节点即为最后留下的节点。
Java 代码实现如下:
```
public static int getLastRemaining(int n) {
// 创建链表
Node head = new Node(1);
Node cur = head;
for (int i = 2; i <= n; i++) {
cur.next = new Node(i);
cur = cur.next;
}
cur.next = head; // 形成环
// 模拟报数和删除节点
int count = 0;
while (head.next != head) {
count++;
if (count == 3) {
count = 0;
cur.next = head.next; // 删除当前节点
} else {
cur = cur.next;
}
head = cur.next;
}
return head.val;
}
// 定义链表节点类
static class Node {
int val;
Node next;
public Node(int val) {
this.val = val;
}
}
```
这段代码可以求解 n 个人围成一圈数到3留下的那个人的编号。
阅读全文