孩子们的游戏
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6
两个环,一个是 arrayHelper 维护的遍历真实数组的环,一个是 countOfChild 报数的环
//有两个环,这两个环会搞混,这样就蒙了, 有一个一直向前的指针 i ,这个是遍历数组的,只和n有关系,然后还有一个与m有关的环计数器,主要是表演就是她,每次环到了时候要做很多的工作。 // 所以这里用 for 循环不好重置再循环回来,用 while,还有一个循环结束的计数器。 public int LastRemaining_Solution(int n,int m){ if(n<1 || m<1){ return -1; } int [] array=new int[n]; int arrayHelper=0; int surviorChild=n;//幸存的孩子人数 int countOfChild=0;//孩子报数计数器 int res=-1; while(surviorChild>1){ if(arrayHelper>n-1){//又回到起点,数组环归零操作 arrayHelper=0; } if(array[arrayHelper]==-1){ //无效坑位不用报数,但是数组真实指针还是要前移的 arrayHelper++; continue; } if(countOfChild==m-1){ //谁报到了m-1,,总结工作,报数环归零操作 array[arrayHelper]=-1;//领盒饭(liwu) countOfChild=-1; //报数归零,报数是从0开始的,这是下一个循环的前一位,所以置-1 surviorChild--;//幸存者减1 } arrayHelper++; //该下一个孩子报数了 countOfChild++;//报数 } for(int i=0;i<array.length;i++){ if(array[i]!=-1){ res=i; break; } } return res; }