[LeetCode]Elimination Game

我们只需要每一次point到当前剩余的第一个数即可。我们每次抹掉一半的数，不是从第一个数开始抹就是从第二个数开始抹(根据剩余的数量是奇数还是偶数来判断)。如果是从第一个数开始抹，我们需要把curr指针移到下一个数，也就是当前数加上当前剩余数每两个之间的差值step即可(我们观察可以得知step是从1开始每次乘以2)。如果是从第二个数开始抹，我们只需要更新step和剩余数即可。重复步骤直到剩余1个数为止。时间复杂度O(log n)，常数空间，代码如下：

	class Solution {
	public:
	int lastRemaining(int n) {
	int step = 1, dir = 1, curr = 1;
	while(n > 1)
	{
	if(dir == 1)
	curr += step;
	else
	{
	if(n % 2)
	curr += step;
	}
	step *= 2;
	n /= 2;
	dir = -dir;
	}
	return curr;
	}
	};

view raw Elimination Game.cpp hosted with ❤ by GitHub