rr459595's blog

LeetCode question- Race car
By rr459595, history, 5 years ago, In English

Your car starts at position 0 and speed +1 on an infinite number line. (Your car can go into negative positions.) Your car drives automatically according to a sequence of instructions A (accelerate) and R (reverse).

When you get an instruction "A", your car does the following: position += speed, speed *= 2.

When you get an instruction "R", your car does the following: if your speed is positive then speed = -1 , otherwise speed = 1. (Your position stays the same.)

For example, after commands "AAR", your car goes to positions 0->1->3->3, and your speed goes to 1->2->4->-1. Now for some target position, return the length of the shortest sequence of instructions to get there.

Constraints:- 1<=target<=10^4

1) Input:- 3 Output:- 2 (shortest instruction is AA)

2) Input:- 6 Output:- 5 (AAARA)

3) Input:-5 Output:-7

Can someone please help me with this problem?

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The key observation is that we don’t want to go very far and don’t want to speed very much. You should think about limits on those two values and then you can run simple bfs where the state is (position, current speed). Also maybe greedy or dp approach is possible — I’ll think about it.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yea. I don't know how to find the limits appropriately. I got TLE because of naively running BFS on (position,speed).

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help?

→ Reply