LeetCode-390-消除游戏
题目
给定一个从1 到 n 排序的整数列表。 首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。 第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。 我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。 返回长度为 n 的列表中，最后剩下的数字。
示例
输入:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6
输出:
6
解答
暴力模拟超时，看了一下别人的思路。
通过观察用例，我们可以得到以下规律：
- 经历的回合数应该是 $$\lfloor \log_2n \rfloor + 1$$
- arr数组永远是一个等差数列
- arr数组的数目，每次减少一半（向下取整）
- 公差每次翻倍
我们知道一个等差数列可以由a0（首项）, d（公差）, n（数列元素个数）三个参数来定义。
综合以上规律，我们知道每次删除后，以上三个参数每次应该这样变化
- d → 2d
- n → n/2
- a0→a0 或者a0→a0+d
大体上来说这道题目就是这样，其它细节可以看代码。
如何决定a0的变化？当删除数字时，存在以下四种情况：
- 从左向右删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
- 从左向右删除，总共有偶数个数字（第一位要删掉，最后一位不用删掉）
- 从右向左删除，总共有奇数个数字（第一位要删掉，最后一位要删掉）
- 从右向左删除，总共有偶数个数字（第一位不用删掉，最后一位要删掉）
只有情况4才会出现a0→a0，其余都是a0→a0+d
代码
int lastRemaining(int n) {
int num_amount = n;
int loop_cnt = 0;
int a0 = 1, d = 1;
while (num_amount != 1) {
// 奇数个数字
if (num_amount % 2 == 1) {
a0 = a0 + d;
}
// 偶数个数字
else if (num_amount % 2 == 0) {
bool left_to_right = (loop_cnt % 2 == 0);
if (left_to_right) {
a0 = a0 + d;
} else
a0 = a0;
}
loop_cnt++;
d *= 2;
num_amount /= 2;
}
return a0;
}