:-: 4.5 消除游戏 ***** **题干：** 给定一个从1 到 n 排序的整数列表。首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。返回长度为 n 的列表中，最后剩下的数字。 示例： ``` 输入: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6 输出: 6 ``` **题目分析：** 此题初看不难，我们可利用list集合删除的特性循环删除，直至集合长度为1或者不使用集合，每次创建新数组。但是真的如此简单吗？ **新手有可能遇到的解题思路陷阱：** 陷入上面两种解法不可自拔。 **解题思路分析以及代码实现：** 第一种思路：List集合循环删除法。此方法正确但超出时间限制，仅作分析学习。 **ArrayList底层使用数组实现，查找操作迅速，添加、删除操作缓慢，而LinkedList底层使用链表实现,查找操作缓慢，添加、删除操作迅速，这个算法又使用了删除操作，为什么不用LinkedList？1.由于LinkedList集合删除、添加需要先进行查找，而链表我们只知道头和尾，中间的元素要遍历获取的，所以导致了访问元素时，效率低2.我们需要使用普通for循环（需要用位置）来遍历集合，但是普通for循环对于LinkedList的遍历是个灾难，原因同上。** [高手不得不知的List细节](https://mp.weixin.qq.com/s/lCmj6pAocbUiiQmaqfJ1Fg) [Java数据结构学习，从源码角度彻底搞懂LinkedList](https://mp.weixin.qq.com/s/-DY7lbDnZSsTAF5e5om7Sg) [为什么千万别用for循环迭代LinkedList](https://blog.csdn.net/u010853261/article/details/54143917) 第一种思路代码： ``` public int lastRemaining(int n) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { list.add(i); } while (list.size() != 1) { for (int i = 0; i < list.size() && list.size() != 1; i++) { list.remove(i); } for (int i = list.size() - 1; i >= 0 && list.size() != 1; i = i - 2) { list.remove(i); } } return list.get(0); } ``` ``` public int lastRemaining(int n) { ArrayList<Integer> list = new ArrayList<Integer>(); for (int i = 1; i <= n; i++) { list.add(i); } while (list.size() != 1) { for (int i = 0; i < list.size(); i++) { list.remove(i); } //集合反转 Collections.reverse(list); } return list.get(0); } ``` 第二种思路：前面我们使用集合结果无误但是时间超时，我们能不能使用数组呢？创建数组。此方法正确但超出内存限制，仅作分析学习。 第二种思路代码： ``` public int lastRemaining(int n) { int[] sum = new int[n]; for (int i = 0; i < n; i++) { sum[i] = i + 1; } while (sum.length != 1) { if (sum.length != 1) { for (int i = 0; i < sum.length; i = i + 2) { sum[i] = 0; } sum = last(sum, sum.length / 2); } if (sum.length != 1) { for (int i = sum.length - 1; i >= 0; i = i - 2) { sum[i] = 0; } sum = last(sum, sum.length / 2); } } return sum[0]; } public static int[] last(int[] sum, int n) { int[] num = new int[n]; int j = 0; for (int s : sum) { if (s != 0) { num[j] = s; j++; } } return num; } ``` 第三种思路：数学法。 我们通过观察能得到这样的规律： 假如输入为 n，我们使用 f(n) 表示 从左到右(forward) 的最终结果，使用 b(n)表示 从右到左(backward) 的最终结果。则 **规律1：当 n = 1 时，存在 f(n) = 1, b(n) = 1。 规律2：对于任意 n，存在 f(n) + b(n) = n + 1。 规律3：对于 n > 2 的情况下，f(n) = 2 * b(n / 2)。** 具体分析过程看这个博客：[消除游戏（Elimination Game）分析和解答](https://blog.csdn.net/afei__/article/details/83689502) 第三种思路代码： ``` public int lastRemaining(int n) { return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2)); } ``` 第三种思路变种：数学法。 我们再分析从n = 1， n = 2，.....开始的结果。 | n值 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | ..... | | :-:| :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: |:-: | | 结果 | 1 | 2 | 2 | 2 | 2 | 4 | 4 | 6 | 6 | 8 | 8 | 6 | 6 | 8 | 8 | 6 | 6 | ..... | 假如输入为 n，我们使用 f(n) 表示最终结果。则 **规律1：当 n = 1时，存在 f(n) = 1。 规律2：当 n >= 2 && n <= 5时，存在 f(n) = 2。 规律3：当n > 5时，相邻的偶奇数的f(n)值相同，所以为了统一处理，所有奇数都转化为它前面的偶数来进行处理。 规律4：当 n % 4 != 0时，f(n) = 4 * f(n / 4)。 规律4：当 n % 4 = 0时，f(n) = 4 * f(n / 4) - 2。** 第三种思路代码： ``` public int lastRemaining(int n) { if (n == 1) return 1; if (n <= 5) return 2; if (n % 2 != 0) n -= 1; if (n % 4 != 0) return 4 * lastRemaining(n / 4); else return 4 * lastRemaining(n / 4) - 2; } ``` 第四种思路代码：惊奇的思路。解题思路看以下链接。 [Java：最简单的解决方案O（logN）和解释](https://leetcode.com/problems/elimination-game/discuss/87119/java-easiest-solution-ologn-with-explanation) [step值是怎么来的](http://www.mamicode.com/info-detail-2269097.html) 第四种思路代码： ``` public int lastRemaining(int n) { int remain = n; boolean left = true; int step = 1, head = 1; while (remain > 1) { if (left || remain % 2 == 1) { head += step; } remain /= 2; step *= 2; left = !left; } return head; } ``` **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**