约瑟夫问题II

自己遇到了的坑：
1.开始用了ArrayList，结果没有addFirst()方法，于是用add(index,Obiect)
的方法添加到表头，实际上只添加到index-1后。
2.在遍历链表删除报数非1的过程中，不敢在判断报数非1后直接调用remove()方法，感觉
会破坏后面的顺序，采用了比较笨的方法，改变值为-1，下一次遍历的时候根据值来删除
import java.util.*;

public class Joseph {
    public int getResult(int n) {
        // write code here
        /* 新建一个链表，依次将1-n添加到列表中(存储每个值得索引)*/
        LinkedList<Integer> list=new LinkedList<Integer>();
        for(int i=1;i<n+1;i++)
        {
            list.add(i);            
        }       
        /* 报数时的初始步长*/
        int origenStep=2;
        /* 遍历链表，直到只剩一个元素时退出 */
       	while(list.size()>1)
        {
           /* 模拟报数，将报数过程中与origenStep取余值非1的值设为-1，方便后面删除*/
            for(int i=0;i<list.size();i++)
            {            
                if((i+1)%origenStep!=1)
                {
                    list.set(i,-1);     
                }                
            }
            /*报数最大值加1*/
            origenStep++;
            /*再一次遍历链表，将值为-1的对象删除，得到报数一遍后的剩余队伍*/
            Iterator<Integer> iter=list.iterator();
            while(iter.hasNext())
            {
                if(iter.next()==-1)
                {
                    iter.remove();                 
                }        
            }
            /* 去队伍的最后一个人，加入链表头，模拟从最后一个人开始*/
           list.addFirst(list.get(list.size()-1));  
            /* 删除最后一个元素(已经加入表头中)*、         
           list.remove(list.size()-1);            
        }
        /*返回链表的第一个元素值*/
        int num=list.get(0);
        return num;      
    }
}

public static int getResult(int n) {
    // write code here
    if (n < 1) {
        return -1;
    }

    LinkedList<Integer> idList = new LinkedList<>();
    for(int i = 1; i <= n; i += 2){//第一轮偶数全都出局，所以初始化列表只需要奇数就行
        idList.add(i);
    }

    int j = 3;//第二轮开始就是报三个数了
    while(j <= n){
        idList.addFirst(idList.removeLast());//尾部移动到头部

        int len = idList.size();
        int k = 1;
        for(int i = 1; i <= len; i++){//删除时注意列表是在不停缩短的
            if (i % j != 1) {
                idList.remove(i - k);
                k++;
            }
        }

        if(idList.size() <= j){
            return idList.getLast();
        }

        j++;
    }
    
    return 1;
}

//list
int getResult(int n){
	list<int>A;
	for(int i=1;i<=n;++i)A.push_back(i);
	int index,cnt = 2;
	while(A.size()>1){
		index = 0;
		auto it = A.begin();
		while(it != A.end()){
			index = (index + 1)%cnt;
			if(index!=1)it = A.erase(it);
			else it++;
		}
		A.push_front(A.back());
		A.pop_back();
		++cnt;
	}
	return A.back();
} 

//vector
int getResult(int n) {
	vector<int>A;
	for(int i=1;i<=n;++i)A.push_back(i);
	int index,cnt = 2;
	while(A.size()>1){
		index = 0;
		for(int i=0;i<A.size();){
			index = (index+1)%cnt;
			if(index != 1)A.erase(A.begin()+i);
			else ++i;
		}
		A.insert(A.begin(),A.back());
		A.pop_back();
		cnt++;
	}
	return A[0];
}

#用字典来解决约瑟夫问题

 public int getResult(int n) {
        // write code here
        if(n<=2){
            return 1;
        }
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 1;i<=n;i+=2){//第一轮 先淘汰掉偶数  剩下全是奇数
            list.add(i);
        }
        int count = 3;
        while(count<=n){
            int last = list.removeLast();
            list.addFirst(last);
            int k = 1;//这个k用的比较好
            int len = list.size();//保留原来列表长度
            for(int i = 1;i<=len;i++){//接下来列表长度是在变化的
                if(i%count!=1){
                    list.remove(i-k);
                    k++;//所以删除一个元素就让k加1，因为删除元素后面的元素都进行了前移，这样下次再删除时能够删除正确元素
                }
            }
            if(count>=list.size()){
                return list.getLast();
            }
            count++;
        }
        return 1;//这个其实就是为了编译通过，根本不会走到这一步的
    }

class Joseph {
public:
    int getResult(int n)
    {
        if (n <= 2) return 1;
        n >>= 1;
        vector<int> people(n + 1);
        for (int i = 0; i <= n; ++i) people[i] = 1 + (i << 1);
        int last = n;
        int m = 3;
        while (people.size() > 1)
        {
            vector<int> pre, post;
            int curNum = 1;
            post.emplace_back(people[last]);
            for (int i = last + 1; i < people.size(); ++i)
            {
                ++curNum;
                if (curNum == m + 1) curNum = 1;
                if (curNum == 1) post.emplace_back(people[i]);
            }
            for (int i = 0; i < last; ++i)
            {
                ++curNum;
                if (curNum == m + 1) curNum = 1;
                if (curNum == 1) pre.emplace_back(people[i]);
            }
            last = pre.size() - 1;
            pre.insert(pre.end(),post.begin(), post.end());
            swap(pre, people);
            ++m;
        }

        return people[0];
    }
};

public int getResult(int n) {
        Node head, t, p; //p记录上一个节点，t是临时节点
        p = head = t = new Node(1);
        for (int i = 2; i <= n; i++, t = t.next) {
            t.next = new Node(i);
        }
        t.next = head; // 构成环

        for (int k = 2; n != 1; k++) { //k代表级数,当只有一个节点时跳出循环
            t = p;
            final int size = n;
            for (int i = 1, cnt = 1; i <= size; i++, cnt++, t = t.next) { //cnt计数, size代表一圈的Node个数
                if (cnt == 1) {
                    p = t;
                    continue;
                }
                if (cnt == k)
                    cnt = 0;
                p.next = t.next;
                n--;
            }
        }
        return t.val;
    }

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

class Joseph {
public:
    int getResult(int n) {
        list<int> l;
        for(int i = 1; i <= n; ++i)
            l.push_back(i);

        for(int i = 2; i < INT_MAX; ++i)
        {
            if(l.size() == 1)
                	break;
            int j = 1;
            for(auto itr = l.begin(); itr != l.end(); ++j)
            {
                if(j % i != 1)
                    l.erase(itr++);
                else
                   ++itr;
            }
            l.push_front(l.back());
            l.pop_back();
        }
        return l.front();
    }
};

int getResult(int n) {
	vector<int>a(n, 0);
	for (int i = 0; i < n; i++)
		a[i] = i+1;
	vector<int>b;
	int num = 2;
	while (a.size() != 1)
	{
		for (int i = 0; i < a.size(); i++)
		{
			if ((i+1) % num == 1)
			{
				b.push_back(a[i]);
			}
		}
		int tmp = b[b.size() - 1];
		b.pop_back();
		a = b;
		a.insert(a.begin(), tmp);
		b.clear();
		num++;
	}
	return a[0];
	// write code here
}

	/**
	 * 核心数据结构：双链表
	 */
	public int getResult(int n) {
		if (n < 1)
			return -1;
		LinkedList<Integer> list = new LinkedList<Integer>();
		int round = 2, i, curr = 0;
		for (i = 1; i <= n; i++) {
			list.add(i);
		}
		while (list.size() > 1) {
			i = 0;
			while (list.size() > 1 && i < list.size()) {
				curr = (curr + 1) % round;
				if (curr != 1) {
					list.remove(i);
				} else {
					i++;
				}
			}
			round++;// 下一轮的最大报数
			curr = 0;// 表示还未开始报数
			if (list.size() > 1) {// 将最后报数的元素移动到链表首部，即确保每次报数从链表首部开始。
				int last = list.removeLast();
				list.addFirst(last);
			}
		}
		return list.pop();// 返回最后一个元素
	}

import java.util.*;

public class Joseph {
    public int getResult(int n) {
		return ysf(n, 2);
    }
    public int ysf(int n, int m) {
        int tmp = n%m==0 ? n/m : n/m+1;
        if(tmp <= m+1) {
            return (tmp-1)*m+1; //终止条件
        }
        int path = ysf(tmp, m+1); //m+1次时最后一人编号的位置
        return (path-2)*m + 1;
    }
}

class Joseph {
public:
    int getResult(int n) {
        // write code here
        vector<int> joseph;
        for (int i = 1; i <= n; i++) {
            joseph.push_back(i);    // 生成joseph数组
        }
        int m = 2;                // 起始间隔
        while (joseph.size() != 1) {    // 直到只有一个元素为止
            vector<int> tmp;
            tmp.push_back(0);    // 先放一个元素进去，避免第2步头插数组整体后移
            for (size_t i = 1; i <= joseph.size(); i += m) {
                tmp.push_back(joseph[i - 1]);    // 把要保留的元素取出来
            }
            tmp[0] = tmp.back();// 第2步，把最后一个元素放在第一位置
            tmp.erase(tmp.end() - 1);// 去掉最后一个元素
            joseph.swap(tmp);        // 交换
            m++;        // 间隔增1
        }
        return joseph.back();    // 返回唯一的元素
    }
};

# -*- coding:utf-8 -*-
class Joseph:
    def getResult(self, n):
        if n <= 0:
            return -1
        
        con = range(1, n + 1)
        rest = n
       	
        round = 1
        while con:
            start = 1
            for key, person in enumerate(con):
                if start == round + 2:
                    start = 1
                if start != 1:
                    rest -= 1
                    con[key] = -1
                start += 1
            con = [i for i in con if i != -1]
            if rest == 1:
                return con[0]
            con.insert(0, con.pop())
            round += 1

/*
思路:
以n=5举例:
1 2 3 4 5	遍历第1次
1 2 1 2 1
1 3 5		遍历第2次
2 3 1
==>5

(1)每次遍历的个数不同，用两个变量控制
count计数器，len更新每次链表长度
(2)三个迭代器控制删除，起始位置
cur:当前位置
next:链表删除会使cur失效，next用来记忆cur位置
last:用来更新每次遍历的初始位置
*/
class Joseph {
public:
	int getResult(int n) {
		// write code here
		list<int> circle;
		for (int i = 1; i <= n; i++)
		{
			circle.push_back(i);
		}

		list<int>::iterator cur, next, last = circle.begin();
		int count, len, m = 1;
		while (circle.size() > 1)
		{
			len = circle.size();
			count = 1;
			m++;
			cur = last;
			while (count <= len)	//遍历1次
			{
				for (int i = 0; i < m; i++)
				{
					next=++cur;
					if (next == circle.end()) next = circle.begin();
					cur--;
					if (i != 0) circle.erase(cur);
					else last = cur;
					cur = next;
					count++;
					if (count > len) break;		//if (count >= len) error!!!
				}
			}
		}

		return circle.front();
	}
};