1.题目基本信息

1.1.题目描述

列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：

• 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。

• 重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。

• 不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回 arr 最后剩下的数字。

1.2.题目地址

https://leetcode.cn/problems/elimination-game/description/

2.解题方法

2.1.解题思路

等差数列模拟

2.2.解题步骤

第一步，构建维护变量。a1维护剩余的数列的第一个元素值；d维护当前等差数列的公差；k当前已经执行的轮数；cnt维护当前剩余的元素的个数。

第二步，遍历；更新维护变量。

= 2.1.更新下一轮等差数列的首元素值

• 2.2.更新k,cnt,d

3.解题代码

python代码

class Solution:
    def lastRemaining(self, n: int) -> int:
        # 思路：等差数列模拟
        # 第一步，构建维护变量。a1维护剩余的数列的第一个元素值；d维护当前等差数列的公差；k当前已经执行的轮数；cnt维护当前剩余的元素的个数。
        a1, d, k = 1, 1, 0
        cnt = n
        # 第二步，遍历；更新维护变量。
        while cnt > 1:
            # 2.1.更新下一轮等差数列的首元素值
            if k & 1 == 0:  # 正项遍历
                a1 = a1 + d
            else:
                a1 = a1 if cnt & 1 == 0 else a1 + d
            # 2.2.更新k,cnt,d
            k += 1
            cnt >>= 1
            d <<= 1
        return a1

c++代码

class Solution {
public:
    int lastRemaining(int n) {
        int a1 = 1, d = 1, k = 0;
        int cnt = n;
        while (cnt > 1) {
            if (k % 2 == 0) {
                a1 = a1 + d;
            } else {
                a1 = (cnt % 2 == 0) ? a1 : a1 + d;
            }
            k++;
            cnt = cnt >> 1;
            d = d << 1;
        }
        return a1;
    }
};

4.执行结果