当前位置: 面试刷题>> 青蛙跳 (经典算法题500道)


题目描述补充

青蛙跳问题

有一只小青蛙,想要从河的一边跳到另一边。河的宽度被划分为n个连续的格子(从0到n-1),每个格子可以是空的(小青蛙可以跳过去),也可以是石头(小青蛙不能跳上去)。给定一个数组stones,其中stones[i]表示第i个石头在河岸上的位置(位置从0开始计数),请问小青蛙能否跳到河的对岸(即位置n-1),如果可以,返回任意一种跳跃序列;如果不可以,返回空数组。

注意

  • 小青蛙每次可以跳过一个或两个格子。
  • 小青蛙的起始位置在stones[0],结束位置是n-1
  • 如果存在多种跳跃序列,返回任意一种即可。

示例

输入

stones = [0, 1, 3, 5, 6, 8, 12, 17]
n = 20

输出

[0, 1, 3, 5, 6, 8, 12, 17]  # 这是一种可能的跳跃序列

PHP 代码示例

function canCross($stones, $n) {
    $dp = array_fill(0, $n, array_fill(0, 2, false));  // dp[i][0] 表示能否一步跳到i,dp[i][1] 表示能否两步跳到i
    $stoneSet = array_flip($stones);  // 将stones数组转为哈希集合,便于快速查找
    
    if (!isset($stoneSet[0])) return [];
    
    $dp[0][0] = true;  // 起始位置可以一步跳到
    
    foreach ($stones as $stone) {
        if ($stone > 2) {
            // 检查是否可以一步或两步从前一个位置跳过来
            if (isset($stoneSet[$stone - 1]) && $dp[$stone - 1][0]) {
                $dp[$stone][0] = true;
                $path[] = $stone;  // 记录路径,但注意这里不是直接返回,因为需要遍历完所有石头
            }
            if (isset($stoneSet[$stone - 2]) && $dp[$stone - 2][1]) {
                $dp[$stone][1] = true;
            }
        }
        
        // 更新两步可达的状态
        if ($stone > 1) {
            $dp[$stone][1] = $dp[$stone][1] || ($dp[$stone - 1][0] && isset($stoneSet[$stone - 2]));
        }
    }
    
    // 回溯构建路径(如果需要的话,这里简化为返回是否可达及一种可能的结束位置)
    if ($dp[$n - 1][0] || $dp[$n - 1][1]) {
        // 假设只需要判断是否可达,并返回最后一个位置作为示例
        return [$n - 1];
        // 注意:实际面试中,可能需要回溯算法来构建完整的跳跃序列
    }
    
    return [];
}

// 注意:上面的代码主要展示了动态规划的思路,并简化了路径的构建部分。
// 完整构建路径需要回溯算法,可能不适合在此直接展示完整代码。

Python 代码示例

def canCross(stones, n):
    dp = [[False, False] for _ in range(n)]
    stone_set = set(stones)
    dp[0][0] = True
    
    for stone in stones:
        if stone > 2:
            if stone - 1 in stone_set and dp[stone - 1][0]:
                dp[stone][0] = True
            if stone - 2 in stone_set and dp[stone - 2][1]:
                dp[stone][1] = True
        
        if stone > 1:
            dp[stone][1] = dp[stone][1] or (dp[stone - 1][0] and stone - 2 in stone_set)
    
    # 假设只需要判断是否可达
    if dp[n - 1][0] or dp[n - 1][1]:
        return True  # 实际面试中可能需要构建路径
    return False

# 注意:此Python示例仅判断了是否可达,未构建路径。

JavaScript 代码示例

function canCross(stones, n) {
    const dp = Array.from({ length: n }, () => [false, false]);
    const stoneSet = new Set(stones);
    dp[0][0] = true;

    for (const stone of stones) {
        if (stone > 2) {
            if (stoneSet.has(stone - 1) && dp[stone - 1][0]) {
                dp[stone][0] = true;
            }
            if (stoneSet.has(stone - 2) && dp[stone - 2][1]) {
                dp[stone][1] = true;
            }
        }

        if (stone > 1) {
            dp[stone][1] = dp[stone][1] || (dp[stone - 1][0] && stoneSet.has(stone - 2));
        }
    }

    return dp[n - 1][0] || dp[n - 1][1];  // 仅判断是否可达

    // 注意:构建完整路径需要额外的回溯逻辑。
}

码小课:在码小课网站中,你可以找到更多关于动态规划、回溯算法以及算法面试题目的详细解析和实战演练,帮助你更好地掌握这些算法技巧,提升编程和解题能力。

推荐面试题