题目地址：
https://leetcode.com/problems/elimination-game/
给定一个长 n n n数组 A A A，里面是 1 , 2 , . . . , n 1,2,...,n 1,2,...,n。第一轮从最左边开始依次删去 A [ 0 , 2 , 4 , . . . ] A[0,2,4,...] A[0,2,4,...]，接下来一轮从最右边开始依次删去 A [ n − 1 , n − 3 , . . . ] A[n-1,n-3,...] A[n−1,n−3,...]（如果 A [ n − 1 ] A[n-1] A[n−1]已经被删掉了，那就是从 A [ n − 2 ] A[n-2] A[n−2]开始），这样循环往复，直到剩下最后一个数字为止。问最后剩下的是几。
题目里要求的是左右循环的顺序删数，设这样删数最后剩余的数是 f ( n ) f(n) f(n)，设右左循环的顺序删数最后剩下的数是 g ( n ) g(n) g(n)。那么第一轮删数完成之后，还剩下 2 , 4 , 6 , . . . , n / 2 ∗ 2 2,4,6,...,n/2*2 2,4,6,...,n/2∗2（这里的除法是整除），接下来就是右左循环删了，我们从左向右重新标号，为 1 , 2 , . . . , n / 2 1,2,...,n/2 1,2,...,n/2，也就是 2 → 1 , 4 → 2 , . . . , n / 2 ∗ 2 → n / 2 2\to 1,4\to 2,...,n/2*2\to n/2 2→1,4→2,...,n/2∗2→n/2，而后者剩下的元素就是 g ( n / 2 ) g(n/2) g(n/2)，并且由对称性有 f ( n ) + g ( n ) = n + 1 f(n)+g(n)=n+1 f(n)+g(n)=n+1，所以 f ( n ) = n / 2 + 1 − f ( n / 2 ) f(n)=n/2+1-f(n/2) f(n)=n/2+1−f(n/2)初始 f ( 1 ) = 1 f(1)=1 f(1)=1。代码如下：
public class Solution {
public int lastRemaining(int n) {
return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
}
}
时空复杂度 O ( log n ) O(\log n) O(logn)。
