（java实现）

题目描述：

有一个数组a[N]顺序存放0~N-1，要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。以8个数(N=7)为例:｛0，1，2，3，4，5，6，7｝，0->1->2(删除)->3->4->5(删除)->6->7->0(删除),如此循环直到最后一个数被删除。

输入描述：

每组数据为一行一个整数n(小于等于1000)，为数组成员数,如果大于1000，则对a[999]进行计算。

输出描述：

一行输出最后一个被删掉的数的原始下标位置。

示例1：

输入

8

输出

6

问题分析：

思路一：使用数组。然后进行计数标记。使用该方法容易出错，在计数结束后，默认下一个是未删除（即为0）；

思路二：使用队列。使用该方法，可以避免上一个错误，但要熟悉队列的操作。

相关知识：

见末尾。

参考代码：

思路一实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            int n = input.nextInt();
            int[] arr = new int[n];
            int count = 1;
            int tmp = 0;
            int index = 0;
            while (count<n)
            {
                //步数不为2，跳过，否则删除
                while (tmp<2)
                {
                    if (0 == arr[index])
                    {
                        tmp++;
                    }
                    index = (index+1+n)%n;  //jump to next
                }
                // delete
                tmp = 0;
                while (0 != arr[index])//容易默认下一个就是0
                {
                    index = (index+1+n)%n;
                }
                arr[index] = count++;
                index = (index+1+n)%n;

            }
            while (0 != arr[index])
            {
                index = (index+1+n)%n;
            }
            System.out.println(index);
        }
    }
}

思路二实现：

import java.util.*;
public class Main {

    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        while (input.hasNext())
        {
            int n = input.nextInt();
            Queue<Integer> queue = new LinkedList<Integer>();
            for (int i=0; i<n; i++)
            {
                queue.add(i);
            }
            int count = 1;
            int tmp = 0;
            int data;
            while (count < n)
            {
                while (tmp<2)
                {
                    data = queue.element();
                    queue.remove();
                    queue.add(data);
                    tmp++;
                }
                tmp=0;
                queue.remove();
                count++;
            }
            System.out.println(queue.element());
        }
    }
}

相关

java队列（queue & deque）方法简介
1、boolean add(E e) 
向队列尾中添加一个元素，成功返回true，失败返回false 
add 在队列满时会抛出IllegalStateException: Queue full异常 
2、boolean offer(E e) 
向队列尾中添加一个元素，成功返回true，失败返回false 
offer 在队列满时，则返回false

3、E remove() 
除队列头一个元素，并返回 
remove 队列为空时会抛出NoSuchElementException异常 
4、E poll() 
移除队列头一个元素，并返回 
poll 队列为空时，返回null

5、E element() 
获取队列头一个元素，不移除 
element 在队列为空时会抛出NoSuchElementException异常 
6、E peek() 
获取队列头一个元素，不移除 
peek 在队列为空时，返回null

7、void push(E e) 
往队列头添加一个元素，没有返回值 
deque中，如果队列满了，会自动扩容

8、E pop() 
移除队列头一个元素，并返回 
pop 队列为空时，抛出NoSuchElementException异常

9、void put(E e) 
队列尾添加一个元素，无返回值 
如果队列已满，则阻塞，直到队列有空间

10、E take() 
从队列头移除一个元素，并返回 
如果队列为空，则阻塞，直到队列中有元素

offer，add 区别：
一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
poll，remove 区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

例子

import java.util.LinkedList;
import java.util.Queue;
public class Main {
    public static void main(String[] args) {
        //add()和remove()方法在失败的时候会抛出异常(不推荐)
        Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element="+queue.element()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("peek="+queue.peek()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
    }
}