刷题笔记合集🔗

停车场车辆统计

问题描述

小柯管理着一个特定大小的停车场，她用一个数组 来表示停车场的情况，其中 表示有车占据车位， 表示车位空闲。

由于车辆大小不同，停车场可以停放三种不同类型的车：小车占一个车位（长度 ），货车占两个车位（长度 ），卡车占三个车位（长度 ）。

请你帮小柯统计停车场最少可以停多少辆车，返回具体的数目。

输入格式

输入为整型字符串数组 ，其中 表示有车， 表示没车，数组长度小于 。

输入数据以英文逗号分隔。

输出格式

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

样例输入

1,0,1

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

样例输出

2

3

样例	解释说明
样例1	个小车占第 个车位，第 个车位空， 个小车占第 个车位，最少有 辆车。
样例2	个货车占第 、 个车位，第 、 个车位空， 个卡车占第 、、 个车位，第 个车位空， 个小车占第 个车位，最少 辆车。

数据范围

• 数组 长度小于
• 数组元素值只为 或

题解

这道题的核心是如何识别出停车场中停放的车辆类型，从而算出最少车辆数。

题目告诉我们，有三种类型的车：小车占1个车位，货车占2个车位，卡车占3个车位。由于要求最少的车辆数，我们的策略是尽量识别出占用车位多的车辆。

最直接的解法是贪心算法：

1. 首先识别出连续3个1的位置，这代表一辆卡车
2. 然后识别出连续2个1的位置，这代表一辆货车
3. 最后剩下的单独的1，都代表一辆小车

具体实现上，可以用字符串替换的方式：

1. 将输入的字符串中所有逗号去掉，得到一个只包含0和1的字符串
2. 将字符串中所有的"111"替换为"x"（代表一辆卡车）
3. 将字符串中所有的"11"替换为"x"（代表一辆货车）
4. 将字符串中所有剩余的"1"替换为"x"（代表一辆小车）
5. 统计字符串中"x"的个数，即为最少车辆数

时间复杂度分析：

• 字符串替换操作的复杂度为O(n)，其中n为字符串长度
• 统计字符"x"的个数也是O(n)
• 总体时间复杂度为O(n)

由于输入数据规模最大为1000，这个复杂度完全可以接受。算法简单直观，不需要复杂的数据结构，很适合这个问题。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入的字符串
cars = input()

# 用字符串替换的方式处理不同车型
# 先替换卡车(占3个位置)，再替换货车(占2个位置)，最后替换小车(占1个位置)
s = cars.replace(",", "")
s = s.replace("111", "x")  # 卡车替换为x
s = s.replace("11", "x")   # 货车替换为x
s = s.replace("1", "x")    # 小车替换为x

# 统计车辆数量
cnt = 0
for c in