网站建设源码,网站开发软件平台有哪些,河南省副厅长,网站展示型推广有哪些这道题在算法课上的一个小故事上有一个类似的#xff0c;就是一个军官打了败仗#xff0c;带着他的几个兵逃到一个山洞#xff0c;他们不想当俘虏想自杀#xff0c;但是军官不想自杀但是又不好意思走#xff0c;于是军官想了个办法#xff0c;他们几个人围成一个圈#…
这道题在算法课上的一个小故事上有一个类似的就是一个军官打了败仗带着他的几个兵逃到一个山洞他们不想当俘虏想自杀但是军官不想自杀但是又不好意思走于是军官想了个办法他们几个人围成一个圈每次枪毙第5个然后从下一个往下数5个最后一个人自杀。只要军官站在第20个的位置上他就可以留到最后然后自己一个人走。
一开始想用循环链表这样就可以按照题目的定义进行循环直到最后剩1个但是用循环链表还得自己写结构体定义最后就用了LinkedListindex表示从哪个位置开始算delete表示要删除的位置最后两个样例过了其他示例超时了。
class Solution {public int lastRemaining(int n, int m) {LinkedListInteger num new LinkedList();for(int i 0;in;i){num.add(i);}int index 0;while(num.size() ! 1){int delete index m-1;int size num.size();delete delete % size;num.remove(delete);indexdelete;}return num.peek();}
} 然后自己又想了一会没思路就直接看题解了题解这个递归都让我看了将近20分钟才看懂但是看懂了就觉得好简单没看懂就一直理解不了。
定义一个递归函数f(int n, int m),他的返回值是一个int表示最后留下的是最后留下的元素的序号对于一个长度为n的序列我们第一次先删除m%n个元素然后递归的求解出剩下的n-1个元素最后会剩下的那个元素的序号记为xint x fn-1, m;
也就是说当我们删除n个元素中第m%n个元素后剩下的n-1个元素如果从第1个开始算最后会剩下第x个元素但是我们不是从第1个开始算的我们是从第m%n个元素开始算的所以最后剩下的是第m%nx个元素以防越界最后再%n也就是第m%nx%n个元素递归必须有终止条件这道题的终止条件就是当n等于1的时候返回第0个元素。
class Solution {public int lastRemaining(int n, int m) {return f(n, m);}public int f(int n, int m){if(n 1){return 0;}int x f(n-1, m);return (m%n x) % n;}
}
