Интервью-головоломка: Jump Game

Question

Игра с прыжками. Для данного массива начните с первого элемента и прыгните до последнего.Длина прыжка может быть не более значения в текущей позиции в массиве.Оптимальный результат - достижение цели за минимальное количество прыжков.

Что такое алгоритм для нахождения оптимального результата?

Пример: данный массив A = {2,3,1,1,4} возможных путей достижения цели (список индексов)):

1. 0,2,3,4 (переход 2 к индексу 2, затем переход 1 к индексу 3, затем 1 к индексу 4)
2. 0,1,4 (переход1 к индексу 1, затем переход 3 к индексу 4)

Поскольку второе решение имеет только 2 скачка, это оптимальный результат.

Answer 1

Обзор

Учитывая ваш массив a и индекс вашей текущей позиции i, повторяйте следующее, пока не дойдете до последнего элемента.

Рассмотрим все возможные "элементы перехода" от a[i+1] до a[a[i] + i]. Для каждого такого элемента с индексом e рассчитайте v = a[e] + e. Если один из элементов является последним элементом, перейдите к последнему элементу. В противном случае перейдите к элементу с максимальным значением v.

Проще говоря, из элементов, находящихся в пределах досягаемости, найдите тот, который сделает вас дальше всего при следующем прыжке . Мы знаем, что этот выбор, x, является правильным, потому что по сравнению с любым другим элементом y, к которому вы можете перейти, элементы, доступные с y, являются подмножеством элементов, доступных с x (за исключением элементов из прыжок назад, что явно является плохим выбором).

Этот алгоритм работает в O (n), потому что каждый элемент должен рассматриваться только один раз (элементы, которые будут рассматриваться во второй раз, могут быть пропущены).

* +1025 * Пример

Рассмотрим массив значений a, показателей i, а также суммы индекса и значения v.

i ->  0   1   2   3   4   5   6   7   8   9  10  11  12
a -> [4, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1]
v ->  4  12   3   4   5   6   7   8   9  10  11  12  13

Начните с индекса 0 и рассмотрите следующие 4 элемента. Найдите тот с максимальным v. Этот элемент имеет индекс 1, поэтому перейдите к 1. Теперь рассмотрим следующие 11 элементов. Цель в пределах досягаемости, поэтому прыгайте к цели.

Демо

См. здесь или здесь с кодом .

Answer 2

Динамическое программирование.

Представьте, что у вас есть массив B, где B[i] показывает минимальное количество шагов, необходимых для достижения индекса i в вашем массиве A.Ваш ответ, конечно, на B[n], учитывая, что A имеет n элементов и индексы начинаются с 1. Предположим, C[i]=j означает, что вы перепрыгнули с индекса j на индекс i (это восстановить путь, взятый позже)

Итак, алгоритм следующий:

set B[i] to infinity for all i
B[1] = 0;                    <-- zero steps to reach B[1]
for i = 1 to n-1             <-- Each step updates possible jumps from A[i]
    for j = 1 to A[i]        <-- Possible jump sizes are 1, 2, ..., A[i]
        if i+j > n           <-- Array boundary check
            break
        if B[i+j] > B[i]+1   <-- If this path to B[i+j] was shorter than previous
            B[i+j] = B[i]+1  <-- Keep the shortest path value
            C[i+j] = i       <-- Keep the path itself

Необходимое количество прыжков B[n].Необходимо выбрать путь:

1 -> C[1] -> C[C[1]] -> C[C[C[1]]] -> ... -> n

, который можно восстановить простым циклом.

Алгоритм имеет O(min(k,n)*n) сложность времени и O(n) сложность пространства.n - это количество элементов в A, а k - максимальное значение в массиве.

Примечание

Я держу этот ответ, но жадный алгоритм Чикена верен иболее эффективный.

Answer 3

Построить ориентированный граф из массива.Например: i-> j if | ij | <= x [i] (В принципе, если вы можете перейти от i к j за один переход, i-> j будет ребром в графе).Теперь найдите кратчайший путь от первого до последнего узла.

FWIW, вы можете использовать алгоритм Дейкстры, чтобы найти кратчайший путь.Сложность есть O (| E | + | V | log | V |).Так как |E |

Answer 4

Мы можем рассчитать дальний индекс для максимального скачка, а если между любым значением индекса больше дальнего, мы обновим дальний индекс.

Простое O (n) решение для сложности времени

public boolean canJump(int[] nums) {
    int far = 0;
    for(int i = 0; i<nums.length; i++){
        if(i <= far){
            far = Math.max(far, i+nums[i]);
        }
        else{
            return false;
        }
    }
    return true;
}

Answer 5

основная идея:

начать построение пути от конца к началу, найдя все элементы массива, из которых можно сделать последний переход к целевому элементу (все i такие, что A[i] >= target - i).

обработайте каждый такой i как новую цель и найдите путь к ней (рекурсивно).

выберите найденную минимальную длину пути, добавьте target, верните.

простой пример на python:

ls1 = [2,3,1,1,4]
ls2 = [4,11,1,1,1,1,1,1,1,1,1,1,1]

# finds the shortest path in ls to the target index tgti
def find_path(ls,tgti):

    # if the target is the first element in the array, return it's index.
    if tgti<= 0:
        return [0]

    # for each 0 <= i < tgti, if it it possible to reach
    # tgti from i (ls[i] <= >= tgti-i) then find the path to i

    sub_paths = [find_path(ls,i) for i in range(tgti-1,-1,-1) if ls[i] >= tgti-i]

    # find the minimum length path in sub_paths

    min_res = sub_paths[0]
    for p in sub_paths:
        if len(p) < len(min_res):
            min_res = p

    # add current target to the chosen path
    min_res.append(tgti)
    return min_res

print  find_path(ls1,len(ls1)-1)
print  find_path(ls2,len(ls2)-1)

>>>[0, 1, 4]
>>>[0, 1, 12]

Answer 6

начало слева (конец) .. и перемещение до числа, совпадающего с индексом, используйте максимум таких чисел. пример, если список

   list:  2738|4|6927
   index: 0123|4|5678

как только вы получите этот шаг, повторяющийся выше, от этого числа до крайнего правого угла.

273846927
000001234

в случае, если вы не нашли сетку, соответствующую индексу, используйте цифру с самым дальним индексом и значением, превышающим индекс. в данном случае 7. (потому что довольно скоро индекс будет больше, чем число, вы, вероятно, можете просто сосчитать до 9 индексов)