约瑟夫问题I

# -*- coding:utf-8 -*-
class node:
    def __init__(self,x):
        self.val = x
        self.next = None
class Joseph:
    def getResult(self,n, m):
            head = node(1)
            phead = head
            cishu = n-1
            n -= 1
            while n!= 0:
                head.next = node(head.val+1)
                head = head.next
                n -= 1
            head.next = phead
            shanchu = 0
            while cishu != shanchu:
                count = 1
                while count != m:
                    phead = phead.next
                    count += 1
                phead.val = phead.next.val
                phead.next = phead.next.next
                shanchu += 1
            return phead.val   
循环链表，不过感觉比较麻烦，不过好理解点

class Joseph {
public:
    int getResult(int n, int m) {
        list<int> circle;
        // 初始状况
        for(int i = 1;i <= n;++i){
            circle.push_back(i);
        }//for
        list<int>::iterator cur = circle.begin();
        while(circle.size() > 1){
            // 数到m的人出局
            for(int i = 0;i < m - 1;++i){
                ++cur;
                if(cur == circle.end()){
                    cur = circle.begin();
                }//if
            }// for
            // 因为删除数到m的人要记录下一个人的地址
            list<int>::iterator next = ++cur;
            if(next == circle.end()){
                next = circle.begin();
            }//if
            --cur;
            // 删除数到m的人
            circle.erase(cur);
            // 从下一个人继续开始
            cur = next;
        }//while
        return circle.front();
    }
};

public int getResult(int n, int m) {
        int x = 0;
        for (int i = 1; i < n; i++) {
            x = (x + m) % (i + 1);
        }
        return x + 1;
    }

	public int getResult(int n, int m)
	{
		// write code here
		ArrayList<Integer> list = new ArrayList<>();
		for (int i = 1; i < n + 1; i++)
			list.add(i);
		int r = 0;
		while (list.size() > 1)
		{
			int k = (r + m) % list.size();
			if (k == 0)
				r = list.size() - 1;
			else
				r = k - 1;
			list.remove(r);
		}
		return list.get(0);
	}

import java.util.*;
/*
思路：因为本题的知识点是链表，因此想到可以用链表来做,至于数学方法，我真的不想用那个，第一我推不清楚，第二不符合题目考点吧
*/
public class Joseph {
    public int getResult(int n, int m) {
        LinkedList<Integer> list =new LinkedList<Integer>();
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        int count=0;
        while(list.size()>1){
            int goal =(count+m-1)%list.size();
            list.remove(goal);
            count =goal%list.size();//这里要注意的，就是count！=goal/////count=goal%list.size()，因为前面删了一个，size变了,不过测试例子检查不出来
        }
        return list.get(0);
    }
}

    public int getResult(int n, int m) {
        // write code here
    	/*
    	 * 存在递推公式：
    	 * f(n,m)表示n个人报数m的离开，最后留下来的人的初始号码
    	 * f(n,m) = (f(n-1,m)+m)%n;
    	 */
    	if(n < 1 || m < 1){
    		return -1;
    	}
    	int last = 0;
    	if(n == 1){
    		return last;//最后一轮出局的人肯定是最后轮的第0个，要找到其初始号码
    	}
    	for(int i = 2; i <= n; i++){
    		last = (last + m) % i;//最后出来的人在倒数第i轮的号码是last
    	}
    	return last+1;//注意编号是1-n编号的，而算法是从0~n-1排序的
    }

class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        vector<int>a(n);
            int j=0;
            for(int i=0;i<n;i++)
                a[i]=i+1;
        for(int i=0;a.size()!=1;i=(++i)%a.size())
        {
            j++;
            if(j==m)
            {
                j=0;
                a.erase(a.begin()+i);
                i--;
            }
        }
        return a[0];
    }
};
创建一个数组1、2、3...n;,每次删除一个元素，最后剩下的就是需要的结果

    //链表
    int getResult(int n, int m) {
        ListNode *head = new ListNode(1),*p = head;
        for(int i=2;i<=n;++i){
            ListNode *node = new ListNode(i);
            p->next = node;
            p = p->next;
        }
        p->next = head;
        while(p->next->val!=p->val){
            int cnt = m;
            while(--cnt){
                p = p->next;
            }
            p->next = p->next->next;
        }
        return p->val;
    }

思路：hh代码减了又减，这样我自己很满意了。我用vector（就是数组）来存放每个人
的编号，vector[0]=1,依次递增，数到m的元素删除，最后剩下的元素的值就是其最开
始的编号。p这个参数是上次删除的元素的位置。其实很好记： (m+p-1)%n
最简单的思路： 下面把第一次删除一个后的数组进行演示，
(k+1,...,n-1,0,1,...k-1)转换为(0~n-2)的形式，  k+1对应0  k+2对于1  ...  k-1对应n-2 可以得到这样的递推关系式：x=（x+k+1）%n;这里的n是上一次的总人数，k=(m-1)%n;
所以从最后一个剩下的人开始推算，那么就是（last+m）%2；这里的“2”是因为倒数
第一次数数的时候还剩两个人。
class Joseph {
public:
    int getResult(int n, int m) {
        vector<int> ya;
        for(int i=0;i<n;i++)
            ya.push_back(i+1);
        return  Ysf(ya,n,m,0);
    }
    int Ysf(vector<int> &ya,int n,int m,int p)
        {
        if(n==1)
            return ya.front();
        else
        {
            ya.erase(ya.begin()+(m+p-1)%n);
             return Ysf(ya,n-1,m,(m+p-1)%n);
        }     
    }
};

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        if(n == 1) return 1;
        if(m < 1 ) return 0;
        
        int pos = 1;
        for(int i=2;i<=n; i++){
            pos = (pos + m -1)%i + 1;
        }
        return pos;
    }
}

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        // write code here
        if(n == 1) {
            return 1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1; i<= n; i++) {
            list.add(i);
        }
        int index = 0;
        while(list.size() != 1) {
            index = (m + index - 1) % list.size();
            list.remove(index);
            
        }
        return list.get(0);
    }
}

//方法二：
import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {

        if(n<=0||m<=0)
              return -1;
        int s=0;
        for(int i=2;i<=n;i++)
            s=(s+m)%i;
        return s+1;
    }
}

if(n<=0||m<=0)
           return -1;
        int s=0;
        for(int i=2;i<=n;i++)
            s=(s+m)%i;
        return s+1;

渣渣用队列来做的 想不出递归 大神勿喷
class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        queue<int> q;
        int i = 1,j = m,k;
        while(i <= n)
            {
            q.push(i);
            i++;
        }
        while(q.size()>1)
            {
            while(j > 1)
                {
                k = q.front();
                q.pop();
                q.push(k);
                j--;
            }
            q.pop();
            j = m;
        }
        return q.front();
    }
};

/*
 * 使用链表真实模拟踢除过程即可
 */
import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        // write code here
        LinkedList<Integer> list = new LinkedList<Integer>();
        for (int i = 1; i <= n; i ++) {
            list.add(i);
        }
        
        int bt = 0;
        while (list.size() > 1) {
            int delPos = (bt + m - 1) % list.size();
            list.remove(delPos);
            bt = delPos % list.size();
        }
        
        return list.get(0);
    }
}

使用了队列这个数据结构

class Joseph {
  public:
    int getResult(int n, int m) {
        // write code here
        queue<int> qu;
        stack<int> st;
        int count = 0, pNum = 0;
        for (int i = 1; i <= n; i++) {
            qu.push(i);
        }
        while (count != n) {
                pNum++;
            if (pNum != m) {             
                qu.push(qu.front());
                qu.pop();
            } else {
                st.push(qu.front());
                qu.pop();
                pNum=0;
                count++;
            }
        }
        return st.top();
    }
};

class Joseph {
public:
    int getResult(int n, int m) {
        // write code here
        if(n<1||m<1)
            return 0;
        list<int>numbers;
        for(int i=1;i<=n;++i)
            numbers.push_back(i);
        list<int>::iterator current=numbers.begin();
        while(numbers.size()>1)
        {
            for(int i=1;i<m;++i)//向后移动m次
            {
                current++;
                if(current==numbers.end())
                    current=numbers.begin();
            }
            //在删除current节点时要记录下current的下一个节点
            list<int>::iterator next=++current;//这里不能写成current+1,因为只有顺序存储结构的迭代器才有加法操作
            if(next==numbers.end())
                next=numbers.begin();
            numbers.erase(--current);
            current=next;
        }
        return *current;
    }
};


//用环形链表模拟圆圈，用list模拟环形链表
//list的底层是链表，vector的底层是数组，因此list在删除的时候要提前记录好待删除元素的下一个位置
//每次在对迭代器做完移动操作完之后都要判断迭代器是否走到了numbers的末尾，若走到了numbers的末尾，要把迭代器返回numbers的开始位置

import java.util.*;

public class Joseph {
    public int getResult(int n, int m) {
        //初始化队列
        Queue<Integer> queue = new LinkedList<>();
        //向队列中添加元素
        for (int i=1; i<=n; i++){
            queue.offer(i);
        }
        //判断队列的元素是否为1
        while (queue.size() != 1){
            //向队列尾部添加队列前m-1个元素，同时删除队列前m-1个元素
            for (int i=1; i<m; i++){
                queue.offer(queue.poll());
            }
            //删除队列第m个元素
            queue.poll();
        }
        //如果队列只有1个元素，输出元素，不删除队列元素
        return queue.peek();
    }
}

 public int LastRemaining_Solution(int n, int m) {
        if(m<=0)return -1;
        ArrayList<Integer> child = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            child.add(i);
        }
        int size=n;
        int start=0;//下一轮索引开始位置
        for(int i=0;i<size;i++){
            if (n==1)break;
            start=m%n-1==-1?(n-1 +start)%n:(m%n-1+start)%n;
            System.out.println(child.get(start));
            child.remove(start);
            n--;
        }
        return child.get(0);
    }