剑指Offer 45圆圈中最后剩下的数字

题目描述

0，1。。。n-1这n个数字排成圈；从数字0开始报数（报数开始为1），报道m时，把它踢出去，然后继续从1报数，最后会剩下谁

思路

模拟游戏过程，直接建一个循环列表，一个一个报数，不过显然这种方法比较复杂；
不一个一个报数了，直接开上帝模式，指挥下一个出去

公式的啦，数学之美；

想法进阶

首先循环链表是最模拟的情况，一个一个来，一个一个报数，最后出结果，在人的索引上不会出现问题，但是你需要指针来进行删除，加入有add和remove方法就好了；那么假设用数组或者LinkedList这种不循环的数据结构，模k就显得很重要；你需要关心的就是索引的位置，数组可以利用比如元素=-1，就当成删除；LinkedList呢，自带remove，但是你需要想明白索引；如果有这么一个循环链表，还有remove方法，这道题简直不要太简单；
下面给出的事循环链表和LinkedList的解法；

代码

//完全模拟报数的过程
   static public int LastRemaining_Solution(int n, int m) {
        if (n==0) {
            return -1;
        }
        ListNode node = new ListNode(0);
        ListNode head = node;
        for (int i = 1; i < n; i++) {
            node.next = new ListNode(i);
            node=node.next;
        }
        node.next = head;
        int current = 1;
        ListNode start = head;      //当前报数的这个人
        ListNode back =  head;      //当前报数的前一个；
        while (start!=start.next)
        {
            while (current<m)
            {
                back = start;
                start=start.next;
                current++;
            }
            back.next = start.next;     //相当于从循环中扔了出去；
            start = back.next;
            current = 1;
        }
        return  start.val;
    }

static public int LastRemaining_Solution2(int n , int m)
  {
      LinkedList<Integer> linkedList = new LinkedList();
      for (int i = 0; i < n; i++) {
          linkedList.add(i);
      }
int current = 0;            //当前报数（0~m-1）
      int index = 0;              //当前位置的索引
      while (linkedList.size()>1)
      {
          while (current<m-1)
          {
              index++;
              index %=linkedList.size();
              current++;
          }
          linkedList.remove(index);
          current=0;
      }
      return linkedList.peek();
  }

然后我们发现实际上不用模拟过程，直接找到下一个的位置即可；于是就可以修改代码为：

static public int LastRemaining_Solution2(int n , int m) {
       LinkedList<Integer> linkedList = new LinkedList();
       for (int i = 0; i < n; i++) {
           linkedList.add(i);
       }
       int index = 0;              //当前位置的索引
       while (linkedList.size()>1)
       {
           index = (index+m-1)%linkedList.size();
           linkedList.remove(index);
       }
       return linkedList.peek();
   }

最后就是公式法了
这里写图片描述

收获

编程编程
慢慢慢慢来；

2017-04-08