【leetcode】390 Elimination Game

发表于 | 分类于 ，

消除游戏


描述

输入一个正整数 n，有 1 , 2 , 3 ,… n,执行操作：

  1. 从左边第一个开始进行消除，每隔一个消除一个，直到结束
  2. 从右边第一个开始进行消除，每隔一个消除一个，直到结束
  3. 若剩下的个数不为 1 ，反复进行前两步操作，否则输出这个数
    1
    2
    3
    4
    5
    n = 9,
    1 2 3 4 5 6 7 8 9
    2 4 6 8
    2 6
    6

样例

1
2
输入: 9
输出: 6

思路

emmm, 有规律。记从左边消除 f(n),记从右边消除 g(n),会满足 f(n) + g(n)= n + 1 。

代码

1
2
3
4
5
6
class Solution {
public:
    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * ((n) / 2 + 1 - lastRemaining(n / 2));
    }
};

参考

原题链接