LeetCode435周赛T2贪心

题目描述

给你一个由字符 '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|

修改操作的影响

我们可以通过修改操作将某些移动方向调整为更优的方向。具体来说：

1. 如果 a < b，则将 a 中的某些步数改为向东走。
2. 如果 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;}
};

思路总结

贪心。不要想后面会怎么走，假设当前就是最优解。面对每一个走法，都有一个应对方案