390. 消除游戏

exiaohu 于 2022-01-02 发布

题目链接：390. 消除游戏

数列模拟。

  1. 输入整数 $n$ ，最初的数列，是一个首项 $a_1=1$，末项 $a_n=n$，公差 $d=1$ 的数列。
  2. 每次进行消除游戏，在等差数列中，间隔一个元素删除，所得的新数列也是一个等差数列，其公差为原数列公差的 $2$ 倍：
    • 若数列长度 $\frac{a_n-a_1}{d}+1$ 为奇数，那么首尾元素都需要消除，即 $a_1’=a_1+d$ ， $a_n’=a_n-d$ ；
    • 若数列长度 $\frac{a_n-a_1}{d}+1$ 为偶数，那么随着方向不同，只需要删除首项或者末尾元素。
import math


class Solution:
    def lastRemaining(self, n: int) -> int:
        a1, an, diff = 1, n, 1

        while a1 < an:
            l, step = (an - a1) // diff + 1, math.floor(math.log2(diff))
            if step & 1 == 0:
                a1 += diff
                if l & 1 == 1:
                    an -= diff
            else:
                an -= diff
                if l & 1 == 1:
                    a1 += diff

            diff *= 2

        return a1