1. 动态规划与双指针在华为 OD 机试中的重要性
华为 OD 机试向来以算法题为核心考察点,其中动态规划和双指针算法出现的频率尤其高。就拿最近几场机试来说,'找车位'和'高效的任务规划'这两道动态规划题几乎成了必考题,而双指针也经常以各种变体形式出现。
为什么华为这么偏爱这两种算法?从实际开发场景来看,动态规划特别适合解决资源优化类问题,比如任务调度、路径规划等华为业务中的常见需求。而双指针在数据处理、字符串操作等基础场景中效率极高。例如经典的'滑动窗口求最大平均数',本质上就是双指针的变种。
2. 动态规划实战:停车位问题详解
2.1 问题描述与建模
'找车位'问题的典型描述是:给定一个只包含 0 和 1 的数组,1 表示已有车辆停放,0 表示空位。要求找到一个停车位,使得该位置到最近车辆的距离最大。比如数组 [1,0,0,0,1,0,1],最优解是下标 2 的位置,此时最近距离为 2。
这个问题可以分解为两个子问题:
- 从左向右遍历,记录每个位置左侧最近的 1 的距离
- 从右向左遍历,记录每个位置右侧最近的 1 的距离
最终结果是这两个距离中的较小值,再取所有位置中的最大值。这种'分解子问题 + 组合结果'的思路就是动态规划的典型特征。
2.2 代码实现与优化
def max_parking_distance(spaces):
n = len(spaces)
left = [float('inf')] * n
right = [float('inf')] * n
# 从左向右扫描
last = -float('inf')
for i in range(n):
if spaces[i] == 1:
last = i
left[i] = i - last
# 从右向左扫描
last = float('inf')
for i in range(n - 1, -1, -1):
if spaces[i] == 1:
last = i
right[i] = last - i
# 计算最大最小距离
max_dist = 0
for i in range(n):
dist = min(left[i], right[i])
dist > max_dist:
max_dist = dist
max_dist

