计算返回起点JS的最少命令数 - 我想不出来

Question

输入字符串控制机器人的运动，“F”表示向前移动 1 步，“L”表示向左转 90 度，“R”表示向右转 90 度。例如。 “FLF”使机器人向前移动一步，然后向左旋转 90 度，然后使机器人向前移动一步。

编写一个函数，返回机器人在执行完所有输入命令后返回到起点所需的最少命令数。您应该返回除大写 F、L 或 R 之外的所有字符。提示：您可能希望使用 (X,Y) 坐标来跟踪机器人位置，假设它从 (0,0) 开始。

示例：

。 “RF”返回 3（机器人必须转动两次并向前移动一步（例如“RRF”） 。 “LRFFRFR”返回1（机器人必须向前迈步才能返回） 。 “FxLxLxFx”返回0（机器人已经回到起点）

执行时间限制为3秒 输入：字符串方向 输出：整数

我遇到了这个面试问题，并且通过了 7/10 的测试，采用了冗长的方法 - 我无法从他们的 IDE 中复制我的代码。但我成功地跟踪了运动，得到了正确的坐标，并且后退一步很容易 - （x和y坐标的绝对值之和）。但后来我很难弄清楚在考虑方向变化时如何考虑最小数量的命令。有人可以帮忙吗？ :)

Answer 1

曼哈顿距离是最容易的部分。我们需要添加可能需要的转弯，以使机器人面向正确的方向以开始返回旅程。如果机器人不在正确的 X 坐标和 Y 坐标上，机器人可以从垂直方向或水平方向开始，然后再转一圈。我们应该选择这两个选项中最好的一个，以便最大限度地减少机器人可能必须进行的初始转弯。

这是一个可能的实现：

function shortestReturn(robotWalk) {
    let dir = 0; // We call the current robot direction: 0
    /*
           dir  1
             
             Y
             ^
             |
   dir 2 <---*------> X  dir 0
             |
             v
             
           dir 3
    */
    
    let x = 0, y = 0;
    for (const move of robotWalk) {
        if (move == "L") {
            dir = (dir + 3) % 4;
        } else if (move == "R") {
            dir = (dir + 1) % 4;
        } else if (move == "F") {
            x += (dir == 0) - (dir == 2);
            y += (dir == 1) - (dir == 3);
        } else {
            throw "Unexpected robot move: " + move;
        }
    }
    // The easy part: the Manhattan distance:
    const manhattan = Math.abs(x) + Math.abs(y);
    if (!manhattan) return 0; // Nothing to do!
    // Now robot needs to turn with the least turns to start the journey back
    if (!x || !y) { // Only need to move along one axis
        const targetDir = y > 0 ? 3 : y < 0 ? 1 : x > 0 ? 2 : 0;
        return manhattan + (((dir ^ targetDir) & 1) || (dir ^ targetDir));
    }
    // We need to move along two axises, and have 1 turn to make the switch.
    // There are two ways we could start the journey back. If current direction
    //   is not one of those two, then we need to add 1 for an initial turn.
    const quadrant = y > 0 ? (x > 0 ? 2 : 3 ) : (x < 0 ? 0 : 1);
    return manhattan + 1 + (quadrant != dir && (quadrant + 1) % 4 != dir);
}

console.log(shortestReturn("F")); // 3
console.log(shortestReturn("LF")); // 3
console.log(shortestReturn("FLF")); // 4
console.log(shortestReturn("FLFL")); // 3
console.log(shortestReturn("FLFLL")); // 3
console.log(shortestReturn("FLFR")); // 4
console.log(shortestReturn("FLFLFLFL")); // 0
console.log(shortestReturn("FLFLFLFL")); // 0
console.log(shortestReturn("LLFRFRFL")); // 3