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

Ответ 1

Обзор

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

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

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

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

Пример

Рассмотрим массив значений 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 элементов. Цель находится в пределах досягаемости, поэтому переходите к цели.

Demo

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

Ответ 2

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

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

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

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 - максимальное значение внутри массива.

Примечание

Я сохраняю этот ответ, но жадный алгоритм жадности правильный и эффективный.

Ответ 3

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

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

Ответ 4

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

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

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

273846927
000001234

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

Ответ 5

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

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

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

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

простой пример в 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 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]