Hard

题目描述

给你一个非负整数 k。存在一个无限长的阶梯，最低的台阶编号为 0。

Alice 有一个整数 jump，初始值为 0。她从台阶 1 开始，想要用任意次数的操作到达台阶 k。如果她在台阶 i，在一次操作中她可以：

  • 下降到台阶 i - 1。这个操作不能连续使用，也不能在台阶 0 使用。
  • 上升到台阶 i + 2^jump。然后，jump 变成 jump + 1。

返回 Alice 可以到达台阶 k 的总方案数。

注意，Alice 可能到达台阶 k，然后执行一些操作再次到达台阶 k。

示例 1：

输入：k = 0
输出：2

示例 2：

输入：k = 1
输出：4

约束条件：

  • 0 <= k <= 10^9

提示：

  • 使用 x 次第二种操作和 y 次第一种操作，到达的台阶是 2^x - y。
  • 由于第一种操作不能连续使用，恰好有 x + 1 个位置（每个2的幂前后）来执行第二种操作。
  • 使用组合数学，我们有 C(x+1, y) 种方法来选择第二种操作的位置。

解题思路

这道题的关键在于理解操作模式和数学规律。

核心观察：

  1. Alice 从台阶 1 开始，可以向下走 1 步（不能连续），或向上走 2^jump 步
  2. 经过 x 次向上操作和 y 次向下操作后，位置为：1 + (2^0 + 2^1 + … + 2^(x-1)) - y = 1 + (2^x - 1) - y = 2^x - y
  3. 我们需要找到所有满足 2^x - y = k 的 (x, y) 组合

数学分析：

  • 如果 2^x - y = k，则 y = 2^x - k
  • 由于向下操作不能连续使用，在 x 次向上操作之间有 x+1 个位置可以插入向下操作
  • 因此对于固定的 x，方案数为 C(x+1, y) = C(x+1, 2^x - k)

算法步骤：

  1. 枚举所有可能的 x 值（从 0 开始）
  2. 计算对应的 y = 2^x - k
  3. 检查 y 是否有效（0 ≤ y ≤ x+1）
  4. 如果有效，累加组合数 C(x+1, y)
  5. 当 2^x > k + x + 1 时可以提前终止（因为此时 y 会超出范围）

由于 k 最大为 10^9，x 最大约为 30，所以时间复杂度是可控的。

代码实现

class Solution {
public:
    int waysToReachStair(int k) {
        long long result = 0;
        
        for (int x = 0; x <= 31; x++) {
            long long powerOf2 = 1LL << x;
            long long y = powerOf2 - k;
            
            if (y < 0 || y > x + 1) {
                if (y < 0) break; // 提前终止
                continue;
            }
            
            // 计算组合数 C(x+1, y)
            long long ways = 1;
            for (int i = 0; i < y; i++) {
                ways = ways * (x + 1 - i) / (i + 1);
            }
            result += ways;
        }
        
        return (int)result;
    }
};

class Solution:
    def waysToReachStair(self, k: int) -> int:
        from math import comb
        
        result = 0
        x = 0
        
        while True:
            power_of_2 = 1 << x
            y = power_of_2 - k
            
            if y < 0:
                break
            
            if y <= x + 1:
                result += comb(x + 1, y)
            
            x += 1
            if x > 31:  # 防止溢出
                break
        
        return result

public class Solution {
    public int WaysToReachStair(int k) {
        long result = 0;
        
        for (int x = 0; x <= 31; x++) {
            long powerOf2 = 1L << x;
            long y = powerOf2 - k;
            
            if (y < 0) break;
            if (y > x + 1) continue;
            
            // 计算组合数 C(x+1, y)
            long ways = 1;
            for (int i = 0; i < y; i++) {
                ways = ways * (x + 1 - i) / (i + 1);
            }
            result += ways;
        }
        
        return (int)result;
    }
}

var waysToReachStair = function(k) {
    const memo = new Map();
    
    function dp(pos, jump, canGoDown) {
        if (pos > k + 1) return 0;
        
        const key = `${pos},${jump},${canGoDown}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = 0;
        if (pos === k) result = 1;
        
        if (canGoDown && pos > 0) {
            result += dp(pos - 1, jump, false);
        }
        
        result += dp(pos + (1 << jump), jump + 1, true);
        
        memo.set(key, result);
        return result;
    }
    
    return dp(1, 0, true);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log²k)
空间复杂度O(1)

说明：

  • 时间复杂度：外层循环最多执行 O(log k) 次（因为 2^x ≤ k + x + 1），内层计算组合数需要 O(log k) 时间
  • 空间复杂度：只使用常量额外空间

相关题目