diff options
-rw-r--r-- | race_car.c | 112 | ||||
-rw-r--r-- | race_car.py | 38 |
2 files changed, 150 insertions, 0 deletions
diff --git a/race_car.c b/race_car.c new file mode 100644 index 0000000..e117baf --- /dev/null +++ b/race_car.c @@ -0,0 +1,112 @@ +// 818. Race Car +#include "leetcode.h" + +/* + * 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). given a + * target position 'target', return the length of the shortest sequence of + * instructions to get there. + */ + +#define MAX_POW_2 20 + +struct args { + int position; + int speed; +}; + +struct queue { + struct args *a; + int prev; + int curr; + size_t len; +}; + +int *get_pow_2(void) { + int *res = (int *)malloc(2 * MAX_POW_2 * sizeof(int)); + res[0] = 1; + for (int i = 1; i < MAX_POW_2; ++i) + res[i] = res[i - 1] * 2; + res[MAX_POW_2] = -1; + for (int i = MAX_POW_2 + 1; i < MAX_POW_2 * 2; ++i) + res[i] = res[i - 1] * 2; + return res; +} + +void queue_init(struct queue *q) { + q->a = (struct args *)malloc(128 * sizeof(struct args *)); + q->len = 128; + q->prev = -1; + q->curr = 0; +} + +void queue_push(struct queue *q, struct args a) { + q->prev++; + if (q->prev >= q->len) { + q->a = (struct args *)realloc(q->a, 2 * q->len * sizeof(struct args)); + q->len *= 2; + } + q->a[q->prev] = a; +} + +struct args queue_pop(struct queue *q) { + struct args res = q->a[q->curr]; + q->curr++; + return res; +} + +bool queue_empty(struct queue *q) { return q->curr > q->prev || q->prev == -1; } + +void queue_free(struct queue *q) { free(q->a); } + +int racecar(int target) { + int *pow = get_pow_2(); + int row_size = 2 * target + 1; + int col_size = 2 * MAX_POW_2; + int *vis[row_size]; + for (int i = 0; i < row_size; ++i) { + vis[i] = (int *)malloc(col_size * sizeof(int)); + memset(vis[i], -1, col_size * sizeof(int)); + } + struct queue q; + queue_init(&q); + struct args initial; + initial.position = 0; + initial.speed = 0; + vis[initial.position][initial.speed] = 0; + queue_push(&q, initial); + while (!queue_empty(&q)) { + struct args curr = queue_pop(&q); + if (curr.position + pow[curr.speed] < row_size && + curr.position + pow[curr.speed] >= 0 && + vis[curr.position + pow[curr.speed]][1 + curr.speed] == -1) { + vis[curr.position + pow[curr.speed]][1 + curr.speed] = + vis[curr.position][curr.speed] + 1; + if (curr.position + pow[curr.speed] == target) + return vis[curr.position + pow[curr.speed]][1 + curr.speed]; + struct args next; + next.position = curr.position + pow[curr.speed]; + next.speed = curr.speed + 1; + queue_push(&q, next); + } + int change = curr.speed < MAX_POW_2 ? MAX_POW_2 : 0; + if (vis[curr.position][change] == -1) { + vis[curr.position][change] = vis[curr.position][curr.speed] + 1; + struct args next; + next.position = curr.position; + next.speed = change; + queue_push(&q, next); + } + } + for (int i = 0; i < row_size; i++) + free(vis[i]); + free(pow); + queue_free(&q); + return -1; +} + +int main() { + printf("%d\n", racecar(3)); // expect: 2 + printf("%d\n", racecar(6)); // expect: 5 +} diff --git a/race_car.py b/race_car.py new file mode 100644 index 0000000..5352fbe --- /dev/null +++ b/race_car.py @@ -0,0 +1,38 @@ +# 818. Race Car + +""" +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). given a +target position 'target', return the length of the shortest sequence of +instructions to get there. +""" + + +class Solution(object): + dp = {0: 0} + + def racecar(self, target): + """ + :type target: int + :rtype: int + """ + if target in self.dp: + return self.dp[target] + n = target.bit_length() + if 2**n - 1 == target: + self.dp[target] = n + else: + self.dp[target] = self.racecar(2**n - 1 - target) + n + 1 + for m in range(n - 1): + self.dp[target] = min( + self.dp[target], + self.racecar(target - 2 ** (n - 1) + 2**m) + n + m + 1, + ) + return self.dp[target] + + +if __name__ == "__main__": + obj = Solution() + print(obj.racecar(3)) + print(obj.racecar(6)) |