LeetCode 818. Race Car

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 818. Race Car 原题链接困难

作者：

wzc1995 , 2019-02-02 03:12:14 , 所有人可见 , 阅读 2317

3

1

题目描述

你的赛车起始停留在位置 0，速度为 +1，正行驶在一个无限长的数轴上。（车也可以向负数方向行驶。）

你的车会根据一系列由 A（加速）和 R（倒车）组成的指令进行自动驾驶。

当车得到指令 “A” 时, 将会做出以下操作：position += speed, speed *= 2。

当车得到指令 “R” 时, 将会做出以下操作：如果当前速度是正数，则将车速调整为 speed = -1；否则将车速调整为 speed = 1。 (当前所处位置不变。)

例如，当得到一系列指令 “AAR” 后, 你的车将会走过位置 0->1->3->3，并且速度变化为 1->2->4->-1。

现在给定一个目标位置，请给出能够到达目标位置的最短指令列表的长度。

样例

输入: 
target = 3
输出: 2
解释: 
最短指令列表为 "AA"
位置变化为 0->1->3

输入: 
target = 6
输出: 5
解释: 
最短指令列表为 "AAARA"
位置变化为 0->1->3->7->7->6

注意

1 <= target（目标位置）<= 10000。

算法

(宽度优先搜索) $O(target \log target)$

建立三维的状态，即 $dis[u][s][0/1]$ 表示到达位置 $u$，当前速度为 $2^s$，向前 (0) 还是向后 (1) 的最少步数。
初始化状态 $dis[0][0][0] = 0$，其余位正无穷。
然后每次转移可以有两种选择，A，则加速，且更新位置；R 则更换速度和方向。
宽搜的范围：显然，进入负的位置是没有意义的，因为总可以找到一个更快得不进入负位置的答案。进入位置大于 2 * target 也是没有意义的，因为我们倒车不可能超过之前一步走的距离。所以搜索的范围被限制在了 [0, 2 * target] 中。

时间复杂度

每个状态只进入一次，共计 $O(target \log target)$ 个状态，故时间复杂度为 $O(target \log target)$。

空间复杂度

同理，共计 $O(target \log target)$ 个状态，故空间复杂度为 $O(target \log target)$。

C++ 代码

class Solution {
public:
    int racecar(int target) {
        vector<vector<vector<int>>> dis(target * 2 + 1, vector<vector<int>>(21, vector<int>(2, INT_MAX)));
        dis[0][0][0] = 0;
        queue<pair<int, pair<int, int>>> q;
        q.push(make_pair(0, make_pair(0, 0)));
        while (!q.empty()) {
            pair<int, pair<int, int>> sta(q.front());
            q.pop();
            int u = sta.first;
            int speed = 1 << sta.second.first;
            if (sta.second.second == 1)
                speed = -speed;

            if (u == target)
                return dis[sta.first][sta.second.first][sta.second.second];


            // instruction A
            if (u + speed <= target * 2 && u + speed >= 0) {
                pair<int, pair<int, int>> nxt(u + speed,
                    make_pair(sta.second.first + 1, sta.second.second));

                if (dis[nxt.first][nxt.second.first][nxt.second.second]
                  > dis[sta.first][sta.second.first][sta.second.second] + 1) {

                    dis[nxt.first][nxt.second.first][nxt.second.second]
                  = dis[sta.first][sta.second.first][sta.second.second] + 1;

                    q.push(nxt);
                }
            }
            // instruction R
            pair<int, pair<int, int>> nxt(u, make_pair(0, 1 - sta.second.second));
            if (dis[nxt.first][nxt.second.first][nxt.second.second]
              > dis[sta.first][sta.second.first][sta.second.second] + 1) {

                dis[nxt.first][nxt.second.first][nxt.second.second]
              = dis[sta.first][sta.second.first][sta.second.second] + 1;

                q.push(nxt);
            }
        }
        return -1;
    }
};

12 评论

haaai 2020-07-06 10:53

时间复杂度计算和剪枝很棒👍

haaai 2020-07-06 10:55

class Solution {
public:
    int end;
    struct node {
        int x, spd, dir;
    };

    queue<node> q;
    int dp[20010][100][2];

    void refresh(node cur, node ne) {
        //两种剪枝：1坐标不为负 2 坐标不大于终点两倍
        if (ne.x < 0) return;
        if (ne.x > (end << 1))    return;
        int& a = dp[cur.x][cur.spd][cur.dir];
        int& b = dp[ne.x][ne.spd][ne.dir];
        if (a + 1 < b) {
            b = a + 1;
            q.push(ne);
        }
    }

    inline int getdir(int x) {
        return x == 1 ? 1 : -1;
    }

    int bfs(int s, int des) {
        memset(dp, 0x3f, sizeof dp);
        q.push({ s, 0, 1 });
        dp[s][0][1] = 0;
        while (q.size()) {
            auto t = q.front(); q.pop();
            if (t.x == des) {
                return dp[t.x][t.spd][t.dir];
            }
            //plan A
            node node_ne_a = { t.x + getdir(t.dir) * (1<<t.spd), t.spd  +1, t.dir };
            refresh(t, node_ne_a);
            //plan R
            node node_ne_r = { t.x, 0, !t.dir };
            refresh(t, node_ne_r);
        }
        return -1;
    }

    int racecar(int target) {
        end = target;
        return bfs(0, target);
    }
};

孤独时代的罗永浩 2021-02-03 11:13 回复了 haaai 的评论

你这个写得好清晰

acvv_bdxgd 2020-01-10 15:36

三维dp是不是转移不了

wzc1995 2020-01-11 03:53

宽搜其实和 DP 的思想差不多，但纯 DP 需要确定好转移顺序

JasonSun 2019-12-12 03:21

老哥，为啥不用 tuple

JasonSun 2019-12-12 06:26

class Solution {
 public:
  int racecar(int target) {
    using node = std::tuple<int, int, int>;

    auto command_a = [&](const node& n) {
      const auto [loc, speed, dir] = n;
      return node{loc + (1 << speed) * (dir == 1 ? -1 : 1), speed + 1, dir};
    };

    auto command_r = [&](const node& n) {
      const auto [loc, speed, dir] = n;
      return node{loc, 0, 1 - dir};
    };

    auto get_next = [&](const node& n) {
      return std::array<node, 2> {command_a(n), command_r(n)};
    };

    auto bfs = [&](int dest) -> optional<int> {
      vector<vector<vector<int>>> dist(dest * 2 + 1, vector<vector<int>>(15, vector<int>(2, INT_MAX / 2)));
      deque<node> q{{0, 0, 0}};
      for(dist[0][0][0] = 0; not empty(q);) {
        const auto [cur_loc, cur_speed, cur_dir] = q.front(); q.pop_front();
        if (cur_loc == dest)
          return dist[cur_loc][cur_speed][cur_dir];
        for (const auto& [next_loc, next_speed, next_dir] : get_next({cur_loc, cur_speed, cur_dir})) {
          if (not (0 <= next_loc and next_loc <= 2 * dest))
            continue;
          if (dist[next_loc][next_speed][next_dir] >  dist[cur_loc][cur_speed][cur_dir] + 1) {
            dist[next_loc][next_speed][next_dir] = dist[cur_loc][cur_speed][cur_dir] + 1;
            q.emplace_back(next_loc, next_speed, next_dir);
          }
        }
      }
      return std::nullopt;
    };
    return bfs(target).value_or(-1);
  }
};