孩子们的游戏(圆圈中最后剩下的数)_46
思路： 用链表模拟约瑟夫环，每次要删除的地方应该是当前索引加上要走的步数，由于我们不要转n圈，所以这可以对链表长度取余，1圈内就找到要删除的位置；
public int LastRemaining_Solution(int n, int m) {
if (n<=0||m<0){
return -1;
}
//list模拟约瑟夫环
LinkedList<Integer> list= new LinkedList();
for (int i = 0; i < n; i++) {
list.add(i);
}
int currStartIndex=0;
while (list.size()>1){
int removeIndex=(currStartIndex+m-1)%list.size();
list.remove(removeIndex);
currStartIndex=removeIndex%list.size();
}
return list.peek();
}优化： 由于我们模拟的是一个环，其实这次删除的位置会被环的下一个位置代替，所以从环上看这次要删除的位置就是下一次要删除的位置
public int LastRemaining_Solution(int n, int m) {
if (n<=0||m<0){
return -1;
}
//list模拟约瑟夫环
LinkedList<Integer> list= new LinkedList();
for (int i = 0; i < n; i++) {
list.add(i);
}
int currStartIndex=0;
while (list.size()>1){
currStartIndex=(currStartIndex+m-1)%list.size();
list.remove(currStartIndex);
}
return list.peek();
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/5/12 下，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
