首页 > 试题广场 >

环形链表的约瑟夫问题

[编程题]环形链表的约瑟夫问题
  • 热度指数:21722 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数,报到 m 的人离开。
下一个人继续从 1 开始报数。
n-1 轮结束以后,只剩下一个人,问最后留下的这个人编号是多少?

数据范围: 
进阶:空间复杂度 ,时间复杂度
示例1

输入

5,2     

输出

3    

说明

开始5个人 1,2,3,4,5 ,从1开始报数,1->1,2->2编号为2的人离开
1,3,4,5,从3开始报数,3->1,4->2编号为4的人离开
1,3,5,从5开始报数,5->1,1->2编号为1的人离开
3,5,从3开始报数,3->1,5->2编号为5的人离开
最后留下人的编号是3      
示例2

输入

1,1

输出

1
题目说了用环形链表解决,那就先创建环形,然后挨个数就可以了。
class Solution {
public:
    ListNode* createList(int n) {
        ListNode *head = new ListNode(1);
        ListNode *p = head;
        for(int i = 2; i <= n; i++) {
            ListNode *node = new ListNode(i);
            p->next = node;
            p = node;
        }
        p->next = head;
        return head;
    }
    
    int ysf(int n, int m) {
        ListNode *head = createList(n);
        ListNode *p = head, *pre = NULL;
        while(p->next != p) {
            for(int i = 1; i < m; i++) {
                pre = p;
                p = p->next;
            }
            // 删除结点p
            pre->next = p->next;
            delete p;
            p = pre->next;
        }
        return p->val;
    }
};


发表于 2020-10-10 17:13:08 回复(2)
class Solution:
    def ysf(self , n , m ):
        # write code here
        res = [i + 1 for i in range(n)]
        i = 0
        for j in range(n-1):
            i = (i + m - 1) % (n - j)
            del res[i]
        return res[0]
    
    
# 取一个数组,循环删除

发表于 2021-01-17 11:11:07 回复(1)
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        //先用列表记录各个数的下标位置
        if(n==1) return 1;
        List<Integer> list = new ArrayList();
        for(int i = 1;i<=n;i++){
            list.add(i);
        }
        //当前指针正指向的位置
        int cur = 0;
        while(list.size()>1){
            //当前遍历时还剩多少人
            int size = list.size();
            //当前列表要删除元素的下标
            cur = (cur+m-1)%size;
            //删除指定下标元素
            list.remove(cur);
        }
        //返回最后剩下人的下标
        return list.get(0);
    }
}

发表于 2022-07-14 13:36:38 回复(0)
struct Node {
  int val;
  Node* next;
  Node() : val(0), next(nullptr) {}
  Node(int _val) : val(_val), next(nullptr) {}
  Node(int _val, Node* _next) : val(_val), next(_next) {}
};

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
      Node* head = new Node(1), *tail = head; // 头尾指针
      for (int i = 2; i <= n; ++i) {
        Node* node = new Node(i);
        tail = tail->next = node; // 尾插手法
      }
      
      tail = tail->next = head; // 形成环
      for (int i = 0; i < n - 1; ++i) {
        for (int j = 1; j < m - 1; ++j)
          tail = tail->next;
        
        Node* node_to_delete = tail->next;
        tail = tail->next = tail->next->next;
        delete node_to_delete;
      }
      
      return tail->val;
    }
};

发表于 2021-07-13 08:16:34 回复(0)
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        return f(n, m) + 1;
    }
    
    private int f (int n, int m) {
        if (n == 1) {
            return 0;
        }
        
        return (f (n - 1, m) + m) % n;
    }
}

递归解法

因为上述解法经常出现栈溢出的问题,所以这里提供使用list集合的解法:
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        ArrayList<Integer> ysf = new ArrayList<>(); // list集合模拟约瑟夫环
        
        for (int i = 1; i <= n; i++) {
            ysf.add(i); // 装载人
        }
        
        int index = 0;
        
        while (ysf.size() != 1) {
           index = (index + m - 1) % ysf.size(); // 报数 直到指定的数
            ysf.remove(index); // 人出列
            // index = (index + 1) % ysf.size(); // 从出列的下一个人开始数数
            // 因为人出列了,所以这个index这个位置被出列后一个人占了,不需要进行处理了
        }
        
        return ysf.get(0);
    }
}


编辑于 2021-06-22 14:09:40 回复(0)
function ysf( n ,  m ) {
    if (n < 1 || m < 1) return null;
    let last = 0;
    for (let i = 2; i <= n; i++) last = (last + m) % i;
    return last + 1;
}

发表于 2021-04-18 16:01:35 回复(0)
约瑟夫环问题 时间复杂度:O(n)  空间:O(1)
/*
解设:  f(n,m) 表示 n 个编号,报号到 m 的最终那个编号
则: 为了方便取模,编号序列从 0 开始 即
1  2  3  4  5  6  ...  ,k-1,  k,  k+1, k+2  ... n
初始序列状态:
0  1  2  3  4  5  ...  ,k-2,  k-1   k, k+1  ... n-1
即 seq1 = [0,1,2...n-1]
递推:
那么 f(n,m) 与 f(n-1,m)有啥关系呢?
1. 假设第一轮取第 m 个数取到编号为 k 的序列, 即 k = (m-1) % n
2. 则取完后,f(n-1, m)的起点状态变化为:
0    1    2    3    4    5    ...  ,  k-2,    k-1,     k,   k+1   ...,n-2
k+1 k+2   k+3 k+4  k+5  k+6   ...  ,  n-1,    0  ,     1,   2     ...,k-1
设 seq2 = [k+1, k+2,..., 0, 1, 2, ..., k-1]
则 从seq1 映射到 seq2 函数为: g(x) = (x+k+1) % n  //根据地址里的序列变换到另一个序列
f(n,m,seq1) 表示 n 个元素,取第 m 个位置的,以seq1序列为内容的值,f对最终选取的位置与seq无关
= f(n-1, m, seq2)
= f(n-1, m, g(seq1))
= g(f(n-1, m, seq1)) 
//不管是序列seq1还是序列seq2,选择的第 m 个位置(地址)一定是相同的,所以可以先选位置,再交换空间内容
即
f(n,m) = g( f(n-1, m) )
	   = (f(n-1,m) + k + 1) % n         when k = (m-1) % n
f(1,m) = 0 // 1 个元素,选第 m 个元素一定是 0 (默认seq1顺序,不带seq形参)
*/
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     *///for循环搞定
    int ysf(int n, int m) {
        int ans = 0, k;
        for(int i = 1; i<n; ++i){
            k = (m-1)%(i+1);
            ans = (ans + k + 1)%(i+1);
        }
        return ans+1;
    }

};

编辑于 2021-04-16 22:47:52 回复(0)
import java.util.*;
public class Solution {
    public int ysf (int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        for (int i=1;i<=n;++i){
            list.addLast(i);
        }
        int curr = 0;
        while (list.size() > 1){
            int size = list.size();
            int pos = (curr+m-1)%size;
            list.remove(pos);
//            // 当只剩下最后一个时候,令cur==0
//             if(size-1==1)
//                 curr=0;
//             else      //其实注释掉的这部分没有也可以,因为及时最后size为0了,curr为1,可是便立即结束了循环,不会边界溢出的
                curr=pos;
        }
        return list.get(0);
    }
}

发表于 2021-04-10 20:24:17 回复(0)
import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    public int ysf (int n, int m) {
        // write code here
        ArrayList<Integer> ysf = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            ysf.add(i);
        }
        int curr = 0;//当前位置
        while(ysf.size() > 1){
            int size = ysf.size();
            int removePos = (curr + m - 1) % size;//当前要被删除的节点的位置
            ysf.remove(removePos);
            curr = removePos % (size - 1); //当前起点的位置。如果删除的是最后一个重置curr为0。      
        }
        return ysf.get(0);
    }
}
// 1 2 3 4 5 -> 1 3 4 5 -> 1 3 5 -> 3 5 -> 3


发表于 2021-03-06 07:52:42 回复(0)
知道这么个思路,还推了半天的公式,还WA了几次才推出来……
class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int ysf(int n, int m) {
//         if(n==1)
//             return 0;
        int x=0; //编号从0开始
        for(int i=2;i<=n;++i)
            x=(x+m)%i;
        return x+1;
    }
};
发表于 2021-07-09 20:06:46 回复(0)
int ysf(int n, int m ) {
    // write code here
    int s = 0;
    for (int i = 2; i <= n; ++i)
        s = (s + m) % i;
    return s+1;
}

b站评论看到的,拿过来一粘贴就过了。
发表于 2022-07-16 17:23:04 回复(0)
import java.util.*;
public class Solution {
    public int ysf (int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<>();
        for (int i=1;i<=n;++i){
            list.addLast(i);
        }
        int curr = 0;
        while (list.size() > 1){
            int size = list.size();
            int pos = (curr+m-1)%size;
            list.remove(pos);
            curr = pos % (size-1);    // 若删除的是最后一个,重置curr为0
        }
        return list.get(0);
    }
}

发表于 2021-02-23 15:43:12 回复(0)
环形链表,占个地方😀😀
import java.util.*;


public class Solution {

    static class Ring{
        // 单向环形链表
        class RingNode{
            int val;
            RingNode next;

            public RingNode(int val){
                this.val = val;
                this.next = null;
            }
        }

        public RingNode head = null;
        public RingNode tail = null;
        public RingNode cur = null;

        // 添加元素
        public void add(int val){
            if(head == null){
                head = new RingNode(val);
                head.next = head;
                cur = head;
                tail = head;
            }else{
                // 新添加的元素放在循环链表的末尾
                tail = new RingNode(val);
                tail.next = head;
                cur.next = tail;
                cur.next.next = head;
                cur = cur.next;
            }
        }

        // 删除元素
        public boolean delete(int m){
            // 循环链表中只剩余一个元素
            if(head.next == head){
                return false;
            }

            // 确定待删除的元素
            RingNode todel = cur;
            for(int i = 1; i < m; i++){
                cur = todel;// cur移动到待删除的元素的前一个位置
                todel = todel.next;
            }

            // 待删除的元素为从当前节点开始的第二个指针
            if(head == todel){
                // 待删除的节点是头指针
                head = head.next;
                tail.next = head;
                cur = head;
            }else if(tail == todel){
                // 待删除的节点是尾指针
                RingNode p = head;
                while(p.next != tail){
                    p = p.next;
                }
                tail = p;
                tail.next = head;
                cur = head;
            }else{
                // 待删除的节点不是头尾指针
                cur.next = todel.next;
                cur = todel.next;
            }

            return true;
        }
    }

    /**
     *
     * @param n int整型
     * @param m int整型
     * @return int整型
     */
    public int ysf (int n, int m) {

        Ring ring = new Ring();
        // 添加元素到队列中
        for(int i = 0; i < n; i++){
            ring.add(i + 1);
        }
        // 将当前节点重新定位到头结点
        ring.cur = ring.head;
        // 循环删除
        while(ring.delete(m));

        return ring.head.val;
    }
}


发表于 2020-09-28 12:37:48 回复(1)
逗号相隔的数据怎么输入 如5,2              cstdio
编辑于 2024-03-01 19:22:06 回复(0)
/**
 * 
 * @param n int整型 
 * @param m int整型 
 * @return int整型
 */
int ysf(int n, int m ) {
    // write code here
    struct ListNode *head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *p = head;
    head->val = 1;
    for (int i = 2; i <= n; i++) {
        struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
        p->next = node;
        p = node;
        p->val = i;
    }
    p->next = head;
    
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m - 1; j++) {
            head = head->next;
        }
        struct ListNode *q = head->next;
        head->next = q->next;
        free(q);
        head = head->next;
    }
    
    return head->val;
}

发表于 2021-09-18 00:20:35 回复(0)
typedef  struct ListNode ListNode;
 ListNode*buynode(int x)
 {
        ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
        newnode->val=x;
        newnode->next=NULL;
        return newnode;
 }
ListNode*createlist(int n)
{
    ListNode*phead=buynode(1);
    ListNode*ptail=phead;
    for(int i=2;i<=n;i++)
    {
        ptail->next=buynode(i);
        ptail=ptail->next;
    }
    ptail->next=phead;
    return phead;
 }
int ysf(int n, int m ) {
    // write code here
    ListNode*head=createlist(n);
    int count =1;
    ListNode*pcur=head;
    ListNode*prev=  NULL;
    while(pcur->next!=pcur)
    {
        if(count==m)
        {
        prev->next=pcur->next;
        free(pcur);
        pcur=prev->next;
        count=1;
        }
        else{
            prev=pcur;
            pcur=pcur->next;
            count++;
        }
    }
    return pcur->val;
}
编辑于 2024-03-10 11:18:56 回复(0)
public int ysf (int n, int m) {
    // write code here
    ListNode p1=new ListNode(1) ,p2=p1;
    for(int i=2;i<=n;i++){
        p2.next=new ListNode(i);
        p2=p2.next;
    }
    p2.next=p1;
    while(p2.next!=p2){
        for(int i=1;i<m;i++){
            p2=p2.next;
        }
        p2.next=p2.next.next;
    }
    return p2.val;
}

编辑于 2024-03-09 16:36:49 回复(0)
#include <stdlib.h>
typedef struct ListNode ListNode ;
//创建节点
ListNode* CreatNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));

    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
//创建链表
ListNode* CreatList(int n)
{
    //先创建头节点
    ListNode* head = CreatNode(1);
    ListNode* ptail = head;
    //循环创建剩余节点,连接至已有节点后
    for (int i=2; i<=n; i++) {
        ListNode* newnode = CreatNode(i);
        ptail->next = newnode;
        //尾节点后移
        ptail = ptail->next;
    }
    //将链表连接成环
    ptail->next = head;
    //return head;
    return ptail; //为防止prev->next为空
}

int ysf(int n, int m ) {
    //创建循环链表
    ListNode* prev = CreatList(n);
    ListNode* pcur = prev->next;
    //ListNode* prev = NULL;
    int count = 1;
    //若节点个数大于1,继续执行删除
    while(pcur->next != pcur)
    {
        //逢m就删除
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            //重新再喊
            count = 1;
        }
        else 
        {
            //不是m,继续喊
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    return pcur->val;
}

发表于 2024-01-24 16:13:10 回复(0)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 *
 * @param n int整型
 * @param m int整型
 * @return int整型
 */

 typedef struct ListNode ListNode;
 ListNode*buyNode (int x)
 {
    ListNode* newnode=(ListNode*)malloc(sizeof(ListNode));
    newnode ->val=x;
    newnode->next=NULL;
    return newnode;
 }
ListNode * creatlist(n)
{
    ListNode *head,*tail;
    int i=1;//这里只可以使用1不可以使用0原因后边需要使用i来赋值;
    head=tail=buyNode (i++);
    while (i<=n)
    {
      tail->next=buyNode (i++);

      tail=tail->next;
     
    }
    tail->next=head;
    return head;
}
int ysf(int n, int m ) {
    ListNode *l=creatlist(n);
     ListNode *head,*cur,*prev;
     prev=head=cur=l;  
     int i=1;
    while (cur->next!=cur)
    {
        if(i==m)
        {
          prev->next=cur->next;
          free(cur);
          cur=prev->next;
          i=1;
        }
        else
        {
            prev=cur;
          cur=cur->next;
          i++;
        }
    }
    return cur->val;
    // write code here
}
编辑于 2023-12-30 12:11:15 回复(0)
struct ListNode* a()
{
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    
    if (node == NULL)
    {
        perror("a->malloc->NULL");
        return NULL;
    }
    return node;
}

int ysf(int n, int m ) {
    // write code here
    struct ListNode* head = a();//头节点
    struct ListNode* prev = NULL;//尾结点

    for (int i = 1; i < n; i++)
    {
        struct ListNode* p = a();
        if (prev == NULL)
        {
            head->next = p;
            prev = p;
        }
        else 
        {
            prev->next = p;
            prev = p;
        }
    }
    
    struct ListNode* tmp = head;
    int i = 1;

    while (tmp)
    {
        tmp->val = i++;
        tmp = tmp->next;
    }

    //让尾结点的next指向头结点
    prev->next = head;

    int j = 1;
    struct ListNode* node = head;
    struct ListNode* pf = NULL;

    while (node->next != node)
    {
        if (j == m)
        {
            pf->next = node->next;
            free(node);
            node = pf->next;
            j = 1;
        }
        else
        {
            pf = node;
            node = pf->next;
            j++;
        }
    }


    return node->val;

}

发表于 2023-11-03 16:20:55 回复(0)