华为OD机试 - 停车场车辆统计 - 贪心算法（Java 2024 D卷 200分）

在这里插入图片描述

华为OD机试 2024D卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（D卷+C卷+A卷+B卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

特定大小的停车场，数组cars[]表示，其中1表示有车，0表示没车。车辆大小不一，小车占一个车位（长度1），货车占两个车位（长度2），卡车占三个车位（长度3），统计停车场最少可以停多少辆车，返回具体的数目。

二、输入描述

整型字符串数组cars[]，其中1表示有车，0表示没车，数组长度小于1000。

三、输出描述

整型数字字符串，表示最少停车数目。

四、测试用例

测试用例1：

1、输入

1,0,1

2、输出

3、说明

1个小车占第1个车位

第二个车位空

1个小车占第3个车位

最少有两辆车

测试用例2：

1、输入

1,1,0,0,1,1,1,0,1

2、输出

3、说明

1个货车占第1、2个车位

第3、4个车位空

1个卡车占第5、6、7个车位

第8个车位空

1个小车占第9个车位

最少3辆车

五、解题思路

1、贪心算法

贪心算法是一种在每一步选择中都采取当前最优策略，以期在全局达到最优解决方案的算法。

贪心算法适用哪些场景？

活动选择问题: 选择最多数量的互不重叠活动。
背包问题（可分割）: 将物品装入背包以最大化总价值，但物品可以分割。
最小生成树: 例如Kruskal和Prim算法。
霍夫曼编码: 构建一个高效的前缀编码树。
贪心货币找零问题: 在某些货币系统中，使用最少的硬币找零。
区间覆盖: 选择最少数量的区间覆盖所有点。
图的染色问题: 某些图的染色问题可以用贪心算法解决。

贪心算法有哪些注意事项？

（1）局部最优不保证全局最优:

贪心算法每一步选择的都是当前最优解，但这不一定能保证最后得到的是全局最优解。

例如，在某些背包问题（不可分割的背包问题）中，贪心算法并不适用。

（2）问题是否具有贪心选择性质:

问题必须具有贪心选择性质，即从局部最优解可以推导出全局最优解。

例如，在活动选择问题中，选择最早结束的活动可以保证最多的活动数。

（3）可行性:

每一步选择必须是可行的，即它必须满足问题的约束条件。

例如，在图的染色问题中，每一步选择的颜色必须不同于相邻节点的颜色。

（4）子问题的最优解:

原问题的最优解包含其子问题的最优解，子问题之间不能有相互影响。

例如，在区间覆盖问题中，每次选择的区间必须最优地覆盖未覆盖的部分。

2、为什么采用贪心算法？

贪心算法的适用性

（1）局部最优解构建全局最优解:

我们希望在每个连续1的段落中使用尽可能少的车位。贪心算法通过每次选择最长的车（优先使用卡车，再是货车，最后是小车），确保每段连续的1使用最少数量的车。

例如，对于连续3个1的段落，使用一辆卡车是最优选择，而不是使用三辆小车。这种局部最优选择最终会构成全局最优解。

（2）问题的分段处理:

本题可以通过对每个独立的连续1段落单独处理来简化问题。每个段落可以独立计算所需的最少车数，然后将结果累加得到最终结果。

贪心算法在这种分段处理时表现良好，因为它不需要考虑段落之间的相互影响。

（3）简单且高效:

贪心算法的时间复杂度是O(n)，其中n是数组的长度。只需一次遍历即可完成计算。

对于每段连续的1，贪心算法直接计算出所需的最少车数，而不需要复杂的动态规划或回溯算法。

3、具体步骤：

使用贪心算法来计算每个连续1段落所需的最少停车车数。

在计算每个连续1段落所需的最少停车车数时，优先选择最长的车（卡车长度为3），然后是中等长度的车（货车长度为2），最后是最短的车（小车长度为1）。这种策略确保我们以最少的车数覆盖所有连续的1段落。

六、Java算法源码

public class OdTest {public static int minParkingCars(int[] cars) {int n = cars.length;int minCars = 0;int i = 0;while (i < n) {if (cars[i] == 1) {int length = 0;while (i < n && cars[i] == 1) {length++;i++;}// 根据连续1的长度，计算最少需要的车数minCars += calculateMinCars(length);} else {i++;}}return minCars;}private static int calculateMinCars(int length) {int cars = 0;// 优先使用卡车（长度3）cars += length / 3;length %= 3;// 使用货车（长度2）cars += length / 2;length %= 2;// 剩余的使用小车（长度1）cars += length;return cars;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] cars = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();int result = minParkingCars(cars);System.out.println(result); // 输出 3}
}