跳转至

3968. 移动后的最大曼哈顿距离

题目描述

给你一个由字符 'U'、'D'、'L'、'R' 和 '_' 组成的字符串 moves。

从原点 (0, 0) 出发，每个字符表示二维平面上的一次移动：

  • 'U'：向上移动 1 个单位。
  • 'D'：向下移动 1 个单位。
  • 'L'：向左移动 1 个单位。
  • 'R'：向右移动 1 个单位。
  • '_'：可以独立地替换为 'U'、'D'、'L' 或 'R' 中的任意一个字符。

返回执行完所有移动后，能够达到的距离原点的 最大曼哈顿距离 。

两点 (x1, y1) 和 (x2, y2) 之间的 曼哈顿距离 为 |x1 - x2| + |y1 - y2|。

 

示例 1：

输入： moves = "L_D_"

输出： 4

解释：

一种最优选择为：

  • 'L'：(0, 0) -> (-1, 0)
  • 将 '_' 视为 'D'：(-1, 0) -> (-1, -1)
  • 'D'：(-1, -1) -> (-1, -2)
  • 将 '_' 视为 'L'：(-1, -2) -> (-2, -2)

最终位置到原点的曼哈顿距离为 |0 - (-2)| + |0 - (-2)| = 4。

示例 2：

输入： moves = "U_R"

输出： 3

解释：

一种最优选择为：

  • 'U'：(0, 0) -> (0, 1)
  • 将 '_' 视为 'U'：(0, 1) -> (0, 2)
  • 'R'：(0, 2) -> (1, 2)

最终位置到原点的曼哈顿距离为 |0 - 1| + |0 - 2| = 3。

 

提示：

  • 1 <= moves.length <= 105
  • moves 仅由 'U'、'D'、'L'、'R' 和 '_' 组成。

解法

方法一：贪心

思考

通配符 _ 可改成任意方向。最终曼哈顿距离是纵移净量的绝对值加横移净量的绝对值；未指定的步数全部加到该和上，因为它们总能沿当前净方向延伸。

一次扫描累计 \(U/D\) 到 \(x\)、\(L/R\) 到 \(y\)、_ 到 \(z\)，答案为 \(|x|+|y|+z\)。

不必真正构造路径。

我们可以用一个变量 \(x\) 来记录上下移动的距离，用一个变量 \(y\) 来记录左右移动的距离，用一个变量 \(z\) 来记录可以替换的次数。

那么最终的曼哈顿距离就是 \(|x| + |y| + z\)。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(\textit{moves}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxDistance(self, moves: str) -> int:
        x = y = z = 0
        for c in moves:
            if c == "U":
                x -= 1
            elif c == "D":
                x += 1
            elif c == "L":
                y -= 1
            elif c == "R":
                y += 1
            else:
                z += 1
        return abs(x) + abs(y) + z

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxDistance(String moves) {
        int x = 0, y = 0, z = 0;
        for (char c : moves.toCharArray()) {
            if (c == 'U') {
                x -= 1;
            } else if (c == 'D') {
                x += 1;
            } else if (c == 'L') {
                y -= 1;
            } else if (c == 'R') {
                y += 1;
            } else {
                z += 1;
            }
        }
        return Math.abs(x) + Math.abs(y) + z;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxDistance(string moves) {
        int x = 0, y = 0, z = 0;
        for (char c : moves) {
            if (c == 'U') {
                x -= 1;
            } else if (c == 'D') {
                x += 1;
            } else if (c == 'L') {
                y -= 1;
            } else if (c == 'R') {
                y += 1;
            } else {
                z += 1;
            }
        }
        return abs(x) + abs(y) + z;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func maxDistance(moves string) int {
    x, y, z := 0, 0, 0
    for _, c := range moves {
        if c == 'U' {
            x -= 1
        } else if c == 'D' {
            x += 1
        } else if c == 'L' {
            y -= 1
        } else if c == 'R' {
            y += 1
        } else {
            z += 1
        }
    }
    return abs(x) + abs(y) + z
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
function maxDistance(moves: string): number {
    let [x, y, z] = [0, 0, 0];
    for (const c of moves) {
        if (c === 'U') {
            x -= 1;
        } else if (c === 'D') {
            x += 1;
        } else if (c === 'L') {
            y -= 1;
        } else if (c === 'R') {
            y += 1;
        } else {
            z += 1;
        }
    }
    return Math.abs(x) + Math.abs(y) + z;
}

评论