算法每日一题——第七天——消除游戏

算法每日一题——第七天——消除游戏"/>

算法每日一题——第七天——消除游戏

原题链接：力扣 

分析:

输入一个n,我们就要对1到n的所有数就行消除。我在看见这道题最开始的想法是将1到n的所有数装到一个数组里面，被消除的数标记为-1，再进行下一次消除时遇见-1就跳过，但是这样写会非常麻烦。

我们先观察上面的样例：

第一次：1，2，3，4，5，6，7，8，9

第二次：2，4，6，8

第三次：2，6

第四次：6

可以发现每次的结果都是一个等差数列，第一次公差为1，第二次公差为2，第三次公差为4。公差的变化规律很容易发现(每次扩大两倍)。那我们就可以思考，是否可以用数列首项，尾项，公差来表示一组数呢？（后面用a1,an,d来分别表示首项，尾项和公差）

如果我们能找出首项和尾项的变化规律，那么我们就可以用他们来表示一组数了。

不难发现以下规律：

从左开始删：有偶数个整数时，a1 = a1 + d ; an = an(不变)

                      有奇数个整数时，a1 = a1 + d ; an = an - d

从右开始删：有偶数个整数时，a1 = a1(不变) ; an = an - d

                      有奇数个整数时，a1 = a1 + d ; an = an - d

找到以上规律，这道题就非常容易了。

接口代码：

int lastRemaining(int n)
{int a1 = 1;int an = n;int d = 1;while(1){if(n == 1)return a1;if(n % 2 == 0)a1 += d;else{a1 += d;an -= d;}d *= 2;n /= 2;if(n == 1)return a1;if(n % 2 == 0)an -= d;else{a1 += d;an -= d;}d *= 2;n /= 2;}   
}