列表 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

    提示：

    1 <= n <= 109

    1. class Solution {
    2.     public int lastRemaining(int n) {
    3.         int step = 1;       //记录步数
    4.         int head = 1;       //记录当前数列头部，也是后面结果
    5.         boolean left = true;
    6.         while (n > 1) {
    7.             //当从左边删除或者数列长度是奇数时我们需要移动首部（首部要被消除）
    8.             if (left || (n & 1) == 1) {
    9.                 head += step;       //加上移动的步数
    10.             }
    11.             left = !left;           //取反
    12.             n /= 2;                 //数列长度减半
    13.             step *= 2;              //因为是隔一个数字删，删完每个相隔就会乘以2
    14.         }
    15.         return head;
    16.     }
    17. }