Участник:Evgin/race car py

Материал из DISCOPAL
< Участник:Evgin
Версия от 07:33, 26 декабря 2020; Evgin (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/race-car/ Python3 Кажется, все идеально, если двигаться так: R только когда уезж…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/race-car/

Python3

Кажется, все идеально, если двигаться так: R только когда уезжаем от цели или когда следующим шагом пересечем ее.

class Solution:
    def racecar(self, target: int) -> int:
        from collections import deque
 
        q = deque([(0, 0, 1)]) # length, position, speed
        best = float('inf')
        while q:
            length, position, speed = q.popleft()
            if position == target:
                best = min(best, length)
            if length >= best:
                continue
            # A
            q.append((length + 1, position + speed, 2 * speed))
 
            if (position + speed > target and speed > 0) or (position + speed < target and speed < 0):
                # R
                q.append((length + 1, position, (-1) * speed / abs(speed)))
        return best