算法：消除游戏

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

一、问题描述

二、基础解法

总结

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题描述

给定一个从1 到 n 排序的整数列表。 首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。 第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。 我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 返回长度为 n 的列表中，最后剩下的数字。

输入:
n = 9,
1 2 3 4 5 6 7 8 9 （1,3,5,7,9被删除）
2 4 6 8 （8,4被删除）
2 6 （2被删除）
6 （剩余6）

输出:
6

二、基础解法

解题思路：

这个题目的关键，就在于以下几个地方：

1、删除的顺序，相邻两次是相反的

2、正序删除时，第一个元素是必删；倒序删除时，第一个元素删不删，是分场景的，如果剩余的数字数量是奇数，则删，偶数，则不删。如果是偶数，首位元素不动，如果是奇数，则首位元素移动。举个例子，第一轮删完之后，剩余是2468，则下次删除时会删掉4和8，首位元素2不动；第一轮删完之后，剩余是246，则下次删除时会删掉2和6，首位元素向后移动，指向4

3、每次删除一半元素，剩余的元素数量为上次遗留总数的一半，如果上次遗留数量是奇数，则删除的数字为一半+1，可以用右移操作，也可以用对2取整，后者更方便理解。

4、步长的变化，可以通过几组简单的数据去总结一下规律，举个例子：

1 2 3 4 5 6 7 8 9 10 11 12 13 ? 初始步长1, 步长为相邻两个元素间的差值
2 4 6 8 10 12 ? ?删掉1 3 5 7 9 11 13, 剩下的元素间, 步长变为2
2 6 10 ? ?删掉12 8 4, 剩下2 6 10, 剩下的元素间, 步长变为4
6 ? ?删掉2 10, 剩下一个元素, 步长不再计算

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ? 初始步长1, 步长为相邻两个元素间的差值
2 4 6 8 10 12 14 16 ?删掉1 3 5 7 9 11 13 15, 剩下的元素间, 步长变为2
2 6 10 14 ? 删掉16 12 8 4, 剩下2 6 10 14, 剩下的元素间, 步长变为4
6 14 ? 删掉2 10, 剩下6 14, 剩下的元素间, 步长变为8

代码示例：

public void test() {
    int n = 9;
    // 初始方向为从左至右
    boolean left = true;
    // 剩余数字数量, 初始值为最大的n
    int remaining = n;
    // 初始步长是1, 由于未删除任何一个元素, 所以每个元素间差值是1
    int step = 1;
    // 初始位置指向左边第一个元素
    int head = 1;
    // 当剩余数字大于等于2个时, 继续删除
    while (remaining > 1) {
        if (left) {
            // 从左到右删除时, 第一个元素必删, 所以head必定向后移动
            head = head + step;
        } else if (remaining % 2 == 1) {
            // 从右到左时, 剩余是偶数, head不动  剩余是奇数, head移动, 移动位置为向后移动step
            head = head + step;
        }
        // 剩下的数字数量是奇数, 则删除remaining/2 + 1个数字, 如果是偶数, 则删除remaining/2个数字
        remaining = remaining >> 1; // remaining = remaining / 2
        // 每次删除一半的数字, 剩下的数字间, 步长变大
        step = step << 1;
        // 顺序调转
        left = !left;
    }
    System.out.println(head);
}

总结

详细注释已添加，快快练习吧，简单到有手就行！