题目
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
- 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
- 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
- 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
给你整数 n ，返回 arr 最后剩下的数字。
示例 1：
输入：n = 9 输出：6 解释： arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]
示例 2：
输入：n = 1 输出：1
解题
此题和剑指 Offer 62：圆圈中最后剩下的数字这个约瑟夫环问题有相似之处,但解法不一样
方法一：建立递归关系
注意不用管左边剩余和右边剩余，f[i]的意思就是轮流换向间隔删除，最终剩余的编号。
class Solution { public: int lastRemaining(int n) { return n==1?1:2*(n/2+1-lastRemaining(n/2)); } };
注意：下面这么写会超时，因为这样从1遍历到n，复杂度为O(N),而上面的方法复杂度为O(logN)
class Solution { public: int lastRemaining(int n) { vector<int> dp(n+1); dp[1]=1; for(int i=2;i<=n;i++){ dp[i]=2*(i/2+1-dp[i/2]); } return dp[n]; } };
方法二：模拟
class Solution { public: int lastRemaining(int n) { int head=1; int step=1; bool left=true; while(n>1){ if(left||n%2==1){ head+=step; } step<<=1; n>>=1; left=!left; } return head; } };
