題目描述
給你一個由字符 'N'、'S'、'E' 和 'W' 組成的字符串 s，其中 s[i] 表示在無限網格中的移動操作：
'N'：向北移動 1 個單位。'S'：向南移動 1 個單位。'E'：向東移動 1 個單位。'W'：向西移動 1 個單位。
初始時，你位于原點 (0, 0)。你 最多 可以修改 k 個字符為任意四個方向之一。
請找出在 按順序 執行所有移動操作過程中的 任意時刻，所能達到的離原點的 最大曼哈頓距離。
曼哈頓距離定義為兩個坐標點 (xi, yi) 和 (xj, yj) 的橫向距離絕對值與縱向距離絕對值之和，即 |xi - xj| + |yi - yj|。
解題思路
我們可以將問題分解為橫坐標和縱坐標兩部分，分別計算它們的貢獻。
橫坐標的計算
設當前向西走了 a 步，向東走了 b 步。
- 如果
a < b，則橫坐標為b - a。 - 如果
a > b，則橫坐標為a - b。
綜合兩種情況，橫坐標為：
|x| = |a - b|
修改操作的影響
我們可以通過修改操作將某些移動方向調整為更優的方向。具體來說：
- 如果
a < b，則將a中的某些步數改為向東走。 - 如果
a > b，則將b中的某些步數改為向西走。
每次修改可以將 |a - b| 增加 2d，因為：
-
如果
a < b，修改d步后，橫坐標為：(b + d) - (a - d) = b - a + 2d
-
如果
a > b，修改d步后，橫坐標為：(a + d) - (b - d) = a - b + 2d
綜合兩種情況，修改后的橫坐標為：
|x| = |a - b| + 2d
其中：
d = min({a,b,k})
然后將 k 減少 d，繼續按照同樣的方法計算縱坐標。
算法實現
以下是基于上述思路的算法實現：
class Solution {
public:int maxDistance(string s, int k) {int up = 0, down = 0, left = 0, right = 0;int res = 0;for(auto c : s){if(c == 'N')up += 1;if(c == 'S')down += 1;if(c == 'W')left += 1;if(c == 'E')right += 1;int t = k;int d = min({up,down,t});t -= d;int f = min({left,right, t});res = max(res, abs(up - down) + 2*d + abs(left - right) + 2 * f );}return res;}
};
思路總結
貪心。不要想后面會怎么走，假設當前就是最優解。面對每一個走法，都有一個應對方案
