403. Frog Jump

public class Solution {
    public bool CanCross(int[] stones) {
        var dp = new Dictionary<int, HashSet<int>>();
        foreach (var stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        dp[0].Add(0);
        
        foreach (var stone in stones) {
            foreach (var jump in dp[stone]) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.ContainsKey(stone + step)) {
                        dp[stone + step].Add(step);
                    }
                }
            }
        }
        
        return dp[stones[stones.Length - 1]].Count > 0;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanCross(vector<int>& stones) {
        var dp = new unordered_map<int, HashSet<int>>();
        foreach (var stone in stones) {
            dp[stone] = new HashSet<int>();
        }
        dp[0].push_back(0);
        
        foreach (var stone in stones) {
            foreach (var jump in dp[stone]) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.count(stone + step)) {
                        dp[stone + step].push_back(step);
                    }
                }
            }
        }
        
        return dp[stones[stones.size() - 1]].size() > 0;
    }
}

import java.util.*;

class Solution {
    public boolean canCross(int[] stones) {
        Map<Integer, Set<Integer>> dp = new HashMap<>();
        for (int stone : stones) {
            dp.put(stone, new HashSet<>());
        }
        dp.get(0).add(0);
        
        for (int stone : stones) {
            for (int jump : dp.get(stone)) {
                for (int step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.containsKey(stone + step)) {
                        dp.get(stone + step).add(step);
                    }
                }
            }
        }
        
        return !dp.get(stones[stones.length - 1]).isEmpty();
    }
}

class Solution {
    canCross(stones) {
        const dp = new Map();
        for (const stone of stones) {
            dp.set(stone, new Set());
        }
        dp.get(0).add(0);
        
        for (const stone of stones) {
            for (const jump of dp.get(stone)) {
                for (let step = jump - 1; step <= jump + 1; step++) {
                    if (step > 0 && dp.has(stone + step)) {
                        dp.get(stone + step).add(step);
                    }
                }
            }
        }
        
        return dp.get(stones[stones.length - 1]).size > 0;
    }
}

class Solution:
    def canCross(self, stones: List[int]) -> bool:
        stone_set = set(stones)
        dp = {stone: set() for stone in stones}
        dp[0].add(0)
        
        for stone in stones:
            for jump in dp[stone]:
                for step in range(jump-1, jump+2):
                    if step > 0 and stone + step in stone_set:
                        dp[stone + step].add(step)
        
        return bool(dp[stones[-1]])

func canCross(stones []int) bool {
    dp := make(map[int]map[int]bool)
    for _, stone := range stones {
        dp[stone] = make(map[int]bool)
    }
    dp[0][0] = true
    
    for _, stone := range stones {
        for jump := range dp[stone] {
            for step := jump - 1; step <= jump + 1; step++ {
                if step > 0 && dp[stone + step] != nil {
                    dp[stone + step][step] = true
                }
            }
        }
    }
    
    return len(dp[stones[len(stones) - 1]]) > 0
}

Algorithm

Инициализация и структура данных

Создайте набор для хранения всех камней для быстрого доступа.

Используйте dynamic programming с помощью словаря для отслеживания достижимых позиций и возможных прыжков.

Итерация по камням

Пройдитесь по каждому камню и для каждого возможного прыжка (k-1, k, k+1) проверьте, если он ведет на существующий камень.

Если такой камень существует, добавьте его в набор возможных прыжков.

Проверка достижения последнего камня

Если можно достичь последний камень с помощью одного из возможных прыжков, return True.

Если после всех итераций последний камень не достигнут, return False.Формирование результата:

Постройте итоговое number из цифр в стеке и удалите ведущие нули.

😎