LeetCode 390. 消除游戏

Categories:

题目描述
思路分析
1. 解法一：数学递推（推荐）
2. 解法二：递归（镜像对称）
相似题目

题目描述

✅ 390. 消除游戏

思路分析

解法一：数学递推（推荐）

核心思路：

每一轮消除后，剩余序列仍是等差数列，关键在于追踪每轮后首元素的值

定义 head 为当前序列的首元素，step 为公差，remaining 为剩余元素个数

从左向右消除时，首元素必定被删除，head += step

从右向左消除时，仅当剩余元素为奇数时首元素被删除，head += step（奇数情况）；偶数时首元素不变

每轮结束后：remaining /= 2，step *= 2

交替执行直到 remaining == 1，此时 head 即为答案

复杂度分析：

时间复杂度：O(log n)，其中 n 为初始序列长度，每轮元素减半

空间复杂度：O(1)，仅使用常数个变量

class Solution {
    public int lastRemaining(int n) {
        // 当前序列首元素
        int head = 1;
        // 当前公差
        int step = 1;
        // 剩余元素个数
        int remaining = n;
        // 是否从左向右消除
        boolean leftToRight = true;

        while (remaining > 1) {
            // 从左向右，或从右向左但剩余数量为奇数时，首元素被删除
            if (leftToRight || remaining % 2 == 1) {
                head += step;
            }

            remaining /= 2;
            step *= 2;
            leftToRight = !leftToRight;
        }

        return head;
    }
}

func lastRemaining(n int) int {
    // 当前序列首元素
    head := 1
    // 当前公差
    step := 1
    // 剩余元素个数
    remaining := n
    // 是否从左向右消除
    leftToRight := true

    for remaining > 1 {
        // 从左向右，或从右向左但剩余数量为奇数时，首元素被删除
        if leftToRight || remaining%2 == 1 {
            head += step
        }

        remaining /= 2
        step *= 2
        leftToRight = !leftToRight
    }

    return head
}

解法二：递归（镜像对称）

核心思路：

观察到：对序列 [1..n] 从左消除后，剩余序列是 [2, 4, 6, ...]，即 2 * lastRemaining(n/2) 的结果镜像

从右消除等价于对新序列求解后做变换：head = 2 * (n/2 + 1 - lastRemaining(n/2))

递推公式：f(n) = 2 * (n/2 + 1 - f(n/2))

复杂度分析：

时间复杂度：O(log n)，递归深度为 log n

空间复杂度：O(log n)，递归栈深度

class Solution {
    public int lastRemaining(int n) {
        if (n == 1) {
            return 1;
        }
        // 从左消除后，问题转化为对 n/2 个元素从右消除的镜像
        return 2 * (n / 2 + 1 - lastRemaining(n / 2));
    }
}

func lastRemaining(n int) int {
    if n == 1 {
        return 1
    }
    // 从左消除后，问题转化为对 n/2 个元素从右消除的镜像
    return 2 * (n/2 + 1 - lastRemaining(n/2))
}

相似题目

题目	难度	考察点
292. Nim 游戏	简单	数学规律
319. 灯泡开关	中等	数学推导
779. 第K个语法符号	中等	递归、数学
1823. 找出游戏的获胜者	中等	约瑟夫问题
457. 环形数组是否存在循环	中等	数组模拟
400. 第 N 位数字	中等	数学规律

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/63197218