Ускорение решения алгоритма

Работаем по следующему алгоритму:

Учитывая массив неотрицательных целых чисел, вы изначально занимаетесь первым индексом массива.

Каждый элемент в массиве представляет вашу максимальную длину прыжка в этой позиции.

Определите, можете ли вы достичь последнего индекса.

Например:

  • A = [2,3,1,1,4], вернуть true.
  • A = [3,2,1,0,4], вернуть false.

Ниже мое решение. Он пробует каждый потенциальный шаг, а затем соответствующим образом запоминает. Итак, если первый элемент равен трем, код выполняет три шага, два шага и один шаг, а оттуда запускает три отдельные функции. Затем я запомнил с помощью хеша. Моя проблема в том, что код работает отлично, но время ожидания очень велико. Воспоминания помогли, но совсем немного. Правильно ли я запоминаю или ошибаюсь здесь?

def can_jump(nums)
    @memo = {}
    avail?(nums, 0)
end

def avail?(nums, index)
    return true if nums.nil? || nums.empty? || nums.length == 1 || index >= nums.length - 1
    current = nums[index]
    true_count = 0
    until current == 0  #try every jump from the val to 1
        @memo[index + current] ||= avail?(nums, index + current)
        true_count +=1 if @memo[index + current] == true
        current -= 1
    end

    true_count > 0

end

ruby algorithm memoization time-complexity
person segue_segway    schedule 23.02.2017    source источник
comment
Вероятно, это больше подходит для обмена стеком проверки кода.   -  person Jordan Running    schedule 23.02.2017
comment
Самый эффективный способ решить эту проблему - динамическое программирование, начиная с предпоследнего индекса и возвращаясь назад. Каждый индекс помечен true или false. Я предложу решение, которое сделает это.   -  person Cary Swoveland    schedule 23.02.2017
comment
@ Джордан, я не согласен. Вопрос в том, нужно ли больше об алгоритме использовать, чем о том, как алгоритм должен быть реализован.   -  person Cary Swoveland    schedule 23.02.2017
comment
@CarySwoveland, так что мой подход + использование мемоизации правильно в реализации, но можно ли было бы сделать более оптимальным способом?   -  person segue_segway    schedule 23.02.2017
comment
@Jordan, задавая здесь вопрос, мы получаем и алгоритм, и код Ruby.   -  person Cary Swoveland    schedule 23.02.2017
comment
@Jordan, ссылаясь на другие сайты, часто бывает полезно указать, что перекрестная публикация не одобряется   -  person gnat    schedule 24.02.2017

Ответы (2)


arrow_upward
2
arrow_downward

Вот алгоритм ???? (????):

  1. Установите ???????????? на 0.
  2. For each number ???????? in ????:
    1. If ???? is greater than ????????????, neither ???????? nor any subsequent number can be reached, so
      • return false.
    2. Если ???? ???? + ???? больше ????????????, установите ???????????? равным ???? ???? + ????.
  3. If ???????????? is greater than or equal to the last index in ????
    • return true.
    • В противном случае верните false.

Вот реализация Ruby:

def can_jump(nums)
  max_reach = 0
  nums.each_with_index do |num, idx|
    return false if idx > max_reach
    max_reach = [idx+num, max_reach].max
  end
  max_reach >= nums.size - 1
end

p can_jump([2,3,1,1,4]) # => true
p can_jump([3,2,1,0,4]) # => false

См. На repl.it: https://repl.it/FvlV/1

person Jordan Running    schedule 23.02.2017
comment
Ваше решение действительно раздражает. Я потратил довольно много времени на свой ответ, который пришлось удалить. Что делает ваш метод, ясно из кода, но я не мог понять объяснения. - person Cary Swoveland; 24.02.2017
comment
Хорошо. Вас раздражает то, что он неясен, или вас раздражает то, что вам пришлось (?) Удалить свой ответ? - person Jordan Running; 24.02.2017
comment
Ой! Я имел в виду (в моем теперь удаленном комментарии) последнее. Пора вывести мою собаку на прогулку. Очень умно, кстати. - person Cary Swoveland; 24.02.2017

arrow_upward
2
arrow_downward

Ваш код - O (n ^ 2), но вы можете получить результат за время O (n) и пространство O (1). Идея состоит в том, чтобы работать в обратном направлении через массив, сохраняя минимальный найденный индекс, от которого вы можете достичь индекса n-1.

Что-то вроде этого:

def can_jump(nums)
    min_index = nums.length - 1
    for i in (nums.length - 2).downto(0)
        if nums[i] + i >= min_index
            min_index = i
        end
    end
    min_index == 0
end

print can_jump([2, 3, 1, 1, 4]), "\n"
print can_jump([3, 2, 1, 0, 4]), "\n"
person Paul Hankin    schedule 23.02.2017
comment
Не могли бы вы объяснить, почему это O (N ^ 2)? Каждый индекс должен быть рассчитан только один раз - после этого доступ? (Числа, индекс) сохраняется в хеш-таблице. Так разве это не просто O (N)? - person segue_segway; 24.02.2017
comment
Это потому, что каждый вызов avail? выполняет итерацию по диапазону значений current. Пример случая O (n ^ 2): [n-1, n-2, ..., 0]. При этом, даже если более высокие значения уже вычислены и запомнены, avail?(nums, i) занимает O (nums.length - i) времени. Суммирование всех значений i дает время O (n ^ 2). - person Paul Hankin; 24.02.2017
comment
Хорошая работа, Пол. Вы работаете в обратном направлении, @ Jordan работает вперед, оба используют одну и ту же идею. - person Cary Swoveland; 24.02.2017
comment
@PaulHankin 'текущая' переменная - это просто целое число в массиве, правильно? Значение не масштабируется с размером ввода. Я понимаю вашу точку зрения о том, что в результате мой путь стал медленнее, но разве не стоимость итерации через текущий диапазон O (1)? - person segue_segway; 24.02.2017
comment
@Sunny Я дал вам пример массива выше, который выполняется за O (n ^ 2). Значение current может масштабироваться или не масштабироваться как n. Когда это произойдет (для достаточно значительной части массива), ваш код будет O (n ^ 2), но он всегда может быть небольшим, и тогда ваш код будет O (n). Является ли current малым для данных, с которыми вы работаете? - person Paul Hankin; 24.02.2017
comment
@PaulHankin Я понимаю, о чем вы говорите. Массив заполняется случайными целыми числами, поэтому я говорю, что целочисленный ток не связан с размером массива, поэтому он не масштабируется с N, поэтому он O (N) (хотя и очень медленный O (N )). Но я думаю, что понял, о чем вы говорите! - person segue_segway; 24.02.2017