390.消除游戏

链接：390.消除游戏
难度：Medium
标签：递归、数学
简介：给你整数 n ，返回 arr 最后剩下的数字。

题解 1 - cpp

• 编辑时间：2022-01-04
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：dfs, 每次减少后都为等差数列，记录每次的头值和间隔。

class Solution {
   public:
    /*
    cnt 有多少个
    step 每个间隔多少
    start 起始值
    dir 方向
    */
    int dfs(int cnt, int step, int start, int dir) {
        if (cnt == 1) return start;
        return dfs(cnt >> 1, step << 1,
                   start + (dir == 1 || cnt & 1 ? step : 0), dir * -1);
    }
    int lastRemaining(int n) { return dfs(n, 1, 1, 1); }
};