详见：https://leetcode.com/problems/elimination-game/description/
C++：
方法一：
class Solution {
public:
int lastRemaining(int n) {
return help(n, true);
}
int help(int n, bool left2right)
{
if (n == 1)
{
return 1;
}
if (left2right)
{
return 2 * help(n / 2, false);
}
else
{
return 2 * help(n / 2, true) - 1 + n % 2;
}
}
};
方法二：
class Solution {
public:
int lastRemaining(int n) {
return n==1?1:2*(1+n/2-lastRemaining(n/2));
}
};
方法三：
class Solution {
public:
int lastRemaining(int n) {
int base = 1, res = 1;
while (base * 2 <= n)
{
res += base;
base *= 2;
if (base * 2 > n)
{
break;
}
if ((n / base) % 2 == 1)
{
res += base;
}
base *= 2;
}
return res;
}
};
详见：https://www.cnblogs.com/grandyang/p/5860706.html
原文：https://www.cnblogs.com/xidian2014/p/8849486.html