孩子们的游戏(圆圈中最后剩下的数)_JAVA_中等
孩子们的游戏(圆圈中最后剩下的数)
http://www.nowcoder.com/questionTerminal/f78a359491e64a50bce2d89cff857eb6
- 设有n个同学，数为m，则最后一位排除的为f(n,m)，第一位排除的为m%n
- f(n,m)第一次处理之后，第一位排除的同学为m%n，剩余n-1位同学，而n-1位同学若是从0开始，则最后一位排除的就是f(n-1,m),而此时却是从m%n开始，则最后一位排除的就是(f(n-1,m) + m%n) % n
- 则f(n,m) = (f(n-1,m) + m) % n
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n < 1) {
return -1;
}
int cache = 0;
for(int i = 2; i <= n; i++) {
cache = (cache + m ) % i;
}
return cache;
}
}
字节跳动公司福利 1377人发布
查看24道真题和解析