最新华为OD机试真题-停车场车位统计(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍿 停车场车位统计
题目描述
K小姐经营着一个特定大小的停车场,停车场可以看成一个数组 ,其中
表示有车,
表示没车。现在停车场内停放着大小不一的车辆,其中小车占一个车位(长度
),货车占两个车位(长度
),卡车占三个车位(长度
)。
K小姐想知道,按照当前停车场的停放情况,最少有多少辆车停在停车场内。你能帮帮她吗?
输入描述
输入一个由 和
组成的字符串,以逗号分隔,表示停车场的车位情况。其中
表示有车,
表示没车,字符串长度不超过
。
输出描述
输出一个整数,表示停车场内最少的停车数目。
样例1
输入
1,0,1
输出
2
说明: 个小车占第
个车位,第
个车位空,
个小车占第
个车位,最少有
辆车。
样例2
输入
1,1,0,0,1,1,1,0,1
输出
3
说明: 个货车占第
、
个车位,第
、
个车位空,
个卡车占第
、
、
个车位,第
个车位空,
个小车占第
个车位,最少有
辆车。
数据范围
题解
本题可以使用贪心算法来解决。我们可以从左到右遍历停车场的车位情况,每次尽可能地停放一辆大的车。
具体地,我们维护一个变量 ,表示当前已经停放的车辆数。同时,用变量
表示当前遍历到的位置。
在遍历过程中,如果当前位置为 ,说明没有车,直接跳过。如果为
,我们就尝试停放一辆车。首先判断能否停放一辆卡车,即
、
、
这三个位置都为
。如果可以,就停一辆卡车,
加
,
向后移动
个位置。如果不能停卡车,就判断能否停货车,即
、
这两个位置都为
。如果可以,就停一辆货车,
加
,
向后移动
个位置。如果也不能停货车,那只能停一辆小车,
加
,
向后移动
个位置。
遍历结束后, 的值就是停车场内最少的停车数目。
参考代码
- Python
cars = input().split(',')
n = len(cars)
cnt = 0
i = 0
while i < n:
if cars[i] == '1':
if i+2 < n and cars[i+1] == '1' and cars[i+2] == '1':
cnt += 1
i += 3
elif i+1 < n and cars[i+1] == '1':
cnt += 1
i += 2
else:
cnt += 1
i += 1
else:
i += 1
print(cnt)
- Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] cars = sc.next().split(",");
int n = cars.length;
int cnt = 0;
for (int i = 0; i < n; ) {
if (cars[i].equals("1")) {
if (i+2 < n && cars[i+1].equals("1") && cars[i+2].equals("1")) {
cnt++;
i += 3;
} else if (i+1 < n && cars[i+1].equals("1")) {
cnt++;
i += 2;
} else {
cnt++;
i++;
}
} else {
i++;
}
}
System.out.println(cnt);
}
}
- Cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string str;
cin >> str;
int n = str.size();
int cnt = 0;
for (int i = 0; i < n; ) {
if (str[i] == '1') {
if (i+2 < n && str[i+1] == '1' && str[i+2] == '1') {
cnt++;
i += 3;
} else if (i+1 < n && str[i+1] == '1') {
cnt++;
i += 2;
} else {
cnt++;
i++;
}
} else {
i++;
}
}
cout << cnt << endl;
return 0;
}
#华为##华为OD##华为OD机试算法题库##笔试##秋招#本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测