818.md

818 Race Car

Description

link

---

Solution 1 : BFS

• visited : used to record the state we have already arrived, because the pos not eqaul to target, so no need to add it into next_state
• pos_a < (target << 1) : double pos of the target means we also no need to record it, we have to add a limit to pos
• step : Do not use memo to record step, just increase it once a time

---

Code 1

Complexity T : O(target * log(target)) M : O(target * log(target))

class Solution:
    def racecar(self, target):
        """
        :type target: int
        :rtype: int
        """
        state = [(0, 1)] # starts from position 0 with speed 1
        
        visited = set(state)
        
        step = 1
        while state:
            next_state = []
            
            for pos, speed in state:
                pos_a = pos + speed
                speed_a = 2 * speed
                
                pos_r = pos
                speed_r = 1 if speed < 0 else -1
                
                if pos_a == target:
                    return step
                
                if (pos_a, speed_a) not in visited and 0 < pos_a and pos_a < (target << 1): # pos_a < (target << 1)
                    next_state.append((pos_a, speed_a))
                    visited.add((pos_a, speed_a))
                
                if (pos_r, speed_r) not in visited and 0 < pos_r and pos_r < (target << 1): # pos_r < (target << 1)
                    next_state.append((pos_r, speed_r))
                    visited.add((pos_r, speed_r))
                
            state = next_state
            step += 1
        
        return -1