停车场车辆统计 - 华为OD统一考试 (C卷)
OD统一考试 (C卷)
分值: 100分
题解: Java / Python / C++
题目描述
特定大小的停车场,数组cars[]表示,其中1表示有车,0表示没车。
车辆大小不一,小车占一个车位(长度1),货车占两个车位(长度2),卡车占三个车位(长度3),统计停车场最少可以停多少辆车,返回具体的数目。
输入描述
整型字符串数组cars[],其中1表示有车,0表示没车,数组长度小于1000。
输出描述
整型数字字符串,表示最少停车数目。
示例1
输入:
1,0,1
输出:
2
说明:
1个小车占1个车位
第二个车位空
1个小车占3个车位最少有两辆车
示例2
输入:
1,1,0,0,1,1,1,0,1
输出:
3
说明:
1个货车占第1、2个车位
第3、4个车位空
1个卡车占第5、6、7个车位
第8个车位空
1个小车占第9个车位
最少3辆车
题解
停车场的规则是:小车占一个车位(长度1),货车占两个车位(长度2),卡车占三个车位(长度3)。
我们可以通过遍历输入的车辆状态数组
cars[]
,同时记录当前连续的占用车位数d
。
- 当遇到有车(
1
)时 d + 1;- 当遇到空位时,计算可以停放多少辆车(贪心的选择: 卡车 》 货车 》 小车),并将
d
置零。- 最后,再次检查一下是否还有剩余的车位数未计算,进行补充计算。最终得到停车场最少可以停多少辆车。
复杂度分析
时间复杂度:O(n),其中 n 为输入数组
cars[]
的长度。空间复杂度:O(1),只使用了常数个变量。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] carsStr =
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2024华为OD机试真题题解 文章被收录于专栏
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。