Прыгающая лягушка
Источник: https://leetcode.com/problems/frog-jump/
Лягушка переберитается через реку. Река разделена на участки, в каждом участке есть камни (но их также может и не быть), по которым прыгает лягушка. Оягушке нельзя упасть в воду.
Дан список stones позиций (на участках), отсортированных в возрастающем порядке. Определить, может ли лягушка перейти реку, приземлившись на поседний камень. В начальной позиции лягука на первом камне и может прыгнуть вперед на 1 участок (ход).
Если предыдущий прыжок лягушки был на k ходов, ее следующий прыжко может быть на k - 1, k, илиk + 1 ходов. Прыгать можно только вперед.
Пример 1:
Дано: stones = [0,1,3,5,6,8,12,17] Результат: true Пояснение: Лягушка может допрыгнуть до последнего камня так:
1. на k=1 ход до 2-го камня (=1).
2. на k=2 хода до 3-го камня (=3).
2. на k=2 хода до 4-го камня (=5).
2. на k=3 хода до 6-го камня (=8).
2. на k=4 хода до 7-го камня (=12).
2. на k=5 хода до 8-го камня (=17).
Пример 2:
Дано: stones = [0,1,2,3,4,8,9,11] Результат: false Пояснение: Нет комбинации прыжков, чтобы допрыгнуь до последнего камня.
Ограничения:
2 <= stones.length <= 20000 <= stones[i] <= 231 - 1stones[0] == 0
Идея решения
Будем использовать динамическое программирование, и в каждой точке рассматривать варианты решения. Для этого используем хэшмап с парами key-value, где key - позиция камня (элементы в заданном массиве), value - список шагов (k), которыми можно допрыгнуть до этого камня.
Просматриваем камни в заданном массиве. Для каждого текущего камня currentStone мы смотрим его список value, состоящий из k. И смотрим, существует ли камень currentStone+jumpsize, где jumpsize может быть {k-1, k, k+1}. Если существует, то к списку value камня currentStone+jumpsize мы добавляем jumpsize.
Если список value последнего камня не пуст, то лягушка может до него допрыгнуть без падений в воду.
Картинка ниже иллюстрирует алгоритм.
Из камня со значением 0 мы можем прыгнуть на 1 позицию вперед до камня со значением 1.
Из камня со значением 1 мы можем прыгнуть вперед на 1 или на 2 хода. Если бы мы прыгали на 1 ход, то нужно, чтобы существовал камень 1+1=2, но его нет. Поэтому остается единственный шаг на 2 хода до камня 1+2=3.
Из камня 3 можно прыгать на 2, 3, или 4 хода, соответвенно на камни 5, 6, 7. Камня 7 не существует, а вот камням 5 и 6 мы добавляем соответственно 2 и 3.
Из 5 можно прыгать на 1, 2, 3 ходы на, соответственно, камни 6, 7, 8. Камня 7 не сущетвует, а камням 6 и 8 добавляем, соответвенно, 1 и 3.
На камне 6 интересная ситуация: там два значения, 3 и 1. Значит, если лягушка допрыгала до камня 6 так, что её предыдущий прыэок был на 3 хода, то она может сделать прыжок на 2, 3, 4 хода. Если же предыдущий прыжок был на 1 ход, то она может сделать на 1 или 2 хода следующий:
6+2=8, добвляем к ходам камня 8 ещё и 2.
6+3=9 не сущестует.
6+4=10 не существует.
6+1=7 не существует.
У камня 8 тоже два элемента: из 3 мы можем прыгнуть на 2, 3, 4 ходв. Из 2 мы можем прыгнуть на 1, 2, 3 хода.
8+2=10 не существует
8+3=11 не существует
8+14=12 - добавляем к камню 12 в список k=4
8+1=9 не существует
Наконек, в камне 12 у нас одно значение 4. Значит, мы можем сделать:
12+3=15 не существует
12+4=16 не существует
12+5=17 - последний камень. Куда лягушке и надо было допрыгнуть.
Имплементация
class Solution {
public boolean canCross(int[] stones) {
// хэшмап, где каждому камню ставим в соответствие размеры шагов (числа k), которми до него можно допрыгать
HashMap<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < stones.length; i++) {
// изначально список шагов до каждогo камня пустой
map.put(stones[i], new HashSet<Integer>());
}
map.get(0).add(0); // в нулевом шаге k=0
for (int i = 0; i < stones.length; i++) { // проходим по каждому камню
for (int k : map.get(stones[i])) { // проходим по каждому k в value
// из k мы можем прыгнуть на {k-1, k, k+1}
for (int step = k - 1; step <= k + 1; step++) {
// k-1 должен быть не нудевым (иначе мы топчемся)
// и не отрицательным (иначе мы прыгаем назад)
// и текущий_камень+k должен существовать
if (step > 0 && map.containsKey(stones[i] + step)) {
map.get(stones[i] + step).add(step);
}
}
}
}
return map.get(stones[stones.length - 1]).size() > 0;
}
}
Комментарии
Отправить комментарий