华为OD机试真题 - 停车场车辆统计 - 贪心算法（Java/Python/JS/C/C++ 2024 D卷 200分）

本文主要是介绍华为OD机试真题 - 停车场车辆统计 - 贪心算法（Java/Python/JS/C/C++ 2024 D卷 200分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

专栏导读

本专栏收录于《华为OD机试真题（Java/Python/JS/C/C++）》。

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

一、题目描述

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

二、输入描述

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

三、输出描述

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

四、测试用例

测试用例1：

1、输入

1,0,1

2、输出

2

3、说明

1个小车占第1个车位

第二个车位空

1个小车占第3个车位

最少有两辆车

测试用例2：

1、输入

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

2、输出

3

3、说明

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

第3、4个车位空

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

第8个车位空

1个小车占第9个车位

最少3辆车

五、解题思路

1、贪心算法

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

贪心算法适用哪些场景？

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

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

（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}
}

七、效果展示

1、输入

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

2、输出

4

3、说明

每个车位段落都只包含一个1，因此每个段落需要一辆小车来占据车位。

具体计算步骤如下：

第一个1段落需要1辆小车。
第二个1段落需要1辆小车。
第三个1段落需要1辆小车。
第四个1段落需要1辆小车。

因此，总的最少停车数为4。

八、Python算法源码

def min_parking_cars(cars):n = len(cars)min_cars = 0i = 0while i < n:if cars[i] == 1:length = 0while i < n and cars[i] == 1:length += 1i += 1# 根据连续1的长度，计算最少需要的车数min_cars += calculate_min_cars(length)else:i += 1return min_carsdef calculate_min_cars(length):cars = 0# 优先使用卡车（长度3）cars += length // 3length %= 3# 使用货车（长度2）cars += length // 2length %= 2# 剩余的使用小车（长度1）cars += lengthreturn carsdef main():cars = list(map(int, input().split(',')))result = min_parking_cars(cars)print(result)if __name__ == "__main__":main()

九、JavaScript算法源码

function minParkingCars(cars) {const n = cars.length;let minCars = 0;let i = 0;while (i < n) {if (cars[i] === 1) {let length = 0;while (i < n && cars[i] === 1) {length++;i++;}// 根据连续1的长度，计算最少需要的车数minCars += calculateMinCars(length);} else {i++;}}return minCars;
}function calculateMinCars(length) {let cars = 0;// 优先使用卡车（长度3）cars += Math.floor(length / 3);length %= 3;// 使用货车（长度2）cars += Math.floor(length / 2);length %= 2;// 剩余的使用小车（长度1）cars += length;return cars;
}function main() {const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim();const cars = input.split(',').map(Number);const result = minParkingCars(cars);console.log(result);
}// 如果在Node.js环境中运行，调用main函数
main();

十、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 计算最少需要的车数
int calculateMinCars(int length) {int cars = 0;// 优先使用卡车（长度3）cars += length / 3;length %= 3;// 使用货车（长度2）cars += length / 2;length %= 2;// 剩余的使用小车（长度1）cars += length;return cars;
}// 计算最少需要的车数来停放连续的车
int minParkingCars(int* cars, int n) {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;
}int main() {char input[1000];fgets(input, sizeof(input), stdin);// 解析输入int cars[1000];int n = 0;char* token = strtok(input, ",");while (token != NULL) {cars[n++] = atoi(token);token = strtok(NULL, ",");}int result = minParkingCars(cars, n);printf("%d\n", result);return 0;
}

十一、C++算法源码

#include <iostream>
#include <sstream>
#include <vector>using namespace std;// 计算最少需要的车数
int calculateMinCars(int length) {int cars = 0;// 优先使用卡车（长度3）cars += length / 3;length %= 3;// 使用货车（长度2）cars += length / 2;length %= 2;// 剩余的使用小车（长度1）cars += length;return cars;
}// 计算最少需要的车数来停放连续的车
int minParkingCars(const vector<int>& cars) {int minCars = 0;int n = cars.size();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;
}int main() {string input;getline(cin, input);// 解析输入vector<int> cars;stringstream ss(input);string token;while (getline(ss, token, ',')) {cars.push_back(stoi(token));}int result = minParkingCars(cars);cout << result << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Java/Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Java/Python/JS/C/C++）

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

这篇关于华为OD机试真题 - 停车场车辆统计 - 贪心算法（Java/Python/JS/C/C++ 2024 D卷 200分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---