題目：每年六一兒童節(jié),牛客都會準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為牛客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0…m-1報數(shù)….這樣下去….直到剩下最后一個小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!^_^)。請你試著想下,哪個小朋友會得到這份禮品呢？(注：小朋友的編號是從0到n-1)

解析：思想是每前進一步就計數(shù)一步，計數(shù)m個，就移除當(dāng)前的元素，然后再回退一步，如此往復(fù)到只剩一個元素為止。代碼邏輯如下（注意：移除的第一個元素不是第0個，而是第m-1個元素）

import java.util.*; public class Solution {public int LastRemaining_Solution(int n, int m) {if(n==0){return -1;}List<Integer> list = new ArrayList<>();for(int i=0;i<n;i++){list.add(i);}int index=-1;int len =0;while (list.size()>1){//一直移除到最后一個元素index=(index+1)%list.size();//索引向前走一步len++;//計數(shù)一次if(len==m){//第m個數(shù)字的時候就開始移除該位置的元素了list.remove(index);index=(index-1)%list.size();//由于剛移除了一個元素，index需要回退一步，然后重新計數(shù)len=0;}}return list.get(0);//最后一個元素就是需要的結(jié)果} }

總結(jié)

以上是生活随笔為你收集整理的《剑指offer》孩子们的游戏---约瑟夫问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。