LeetCode Elimination Game There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list. Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers. We keep repeating the steps again, alternating left to right and right to left, until a single number remains. Find the last number that remains starting with a list of length n. Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
Output:
6

---

本题介绍了一个消除游戏，就是1~n排列了n个数，先从左往右每隔一个数消除一个（包含1），然后从右往左每隔一个数消除一个（包含最后一个数），如此循环，直到只剩一个数，要求输出这个数。 我一开始以为这是个模拟题，直接用STL的双向链表list模拟了，代码如下： [cpp] class Solution { public: int lastRemaining(int n) { list<int> l; for (int i = 1; i <= n; i++)l.push_back(i); while (l.size() != 1) { list<int>::iterator it = l.begin(); while (it != l.end()) { it = l.erase(it); if (it != l.end())++it; } if (l.size() == 1)break; list<int>::reverse_iterator rit = l.rbegin(); while (rit != l.rend()) { rit = list<int>::reverse_iterator(l.erase(–(rit.base()))); if (rit != l.rend())++rit; } if (l.size() == 1)break; } return *l.begin(); } }; [/cpp] 很不幸，本代码提交TLE，超时了。 网上查题解，这个人讲得比较清楚。一开始1,2,3,4,5,6,7,8,…,n，第一次从左往右消除之后，剩余2,4,6,8…,n，其实就相当于2*(1,2,3,4,…n/2)。但是这个时候我们要对1,2,3,4,…n/2从右往左消除了，那么从右往左和从左往右消除得到的结果有什么规律呢，他们的结果应该是呈镜像对称的，也就是说如果长度为n/2的话，如果从左往右的结果为x，那么从右往左的结果就应该是n/2+1-x；同理如果从右往左的结果是y的话，那么从左往右的结果就应该是n/2+1-y。 代码实现为： [cpp] class Solution { public: int lastRemaining(int n) { return n == 1 ? 1 : 2 * (n / 2 + 1 – lastRemaining(n / 2)); } }; [/cpp] 本代码提交AC，用时49MS。]]>