两个环,一个是 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;
}

京公网安备 11010502036488号