Elimination Game例题
Elimination Game题解
随便写几个小例子查看，发现每次数字个数减少一半，每一层的数之间的间隔相等，然后考虑模拟删除过程，需要记录如下几个变量
- 每一层的第一个数
- 当前层的数字个数
- 当前层每两个数字的间隔
然后依次模拟删除，当个数只剩一个的时候返回，然后考虑第一个数和个数，以及间隔怎么更新。个数就是除二，间隔就是乘二，
然后第一个数，当从左边删除的时候，就是上一层的第一个数加上间隔长度，当从右边删除的时候，需要考虑个数的奇偶性，偶数的话，
跟上一层一致，奇数的话，就是上一层的加上间隔长度，跟从左边更新一致。
代码如下：
class Solution {
public:
int lastRemaining(int n) {
if(n == 1) return 1;
int len = 1;
bool f = 1;
int left = 1;
while(1) {
if(f) {
left = left + len;
} else {
if(n & 1) {
left = left + len;
}
}
n /= 2; len *= 2;
f = !f;
if(n == 1) return left;
}
return 0;
}
};