个人评价:简单基础的系统设计题,可考虑优化其可扩展性

题目难度:🌟 (参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 )

另,通常算法题会考察分析时间复杂度和空间复杂度,可参考笔者之前的文章

「数据结构&算法」必知必会系列:3. 时间 & 空间复杂度(下)

设计停车系统

题目描述

1603. 设计停车系统

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。

请你实现 ParkingSystem 类:

  • ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,三个参数分别对应每种停车位的数目。
  • bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。一辆车只能停在  carType 对应尺寸的停车位中。如果没有空车位,请返回 false ,否则将该车停入车位并返回 true 。

示例 1:

输入:

[“ParkingSystem”, “addCar”, “addCar”, “addCar”, “addCar”] [[1, 1, 0], [1], [2], [3], [1]]

输出:

[null, true, true, false, false]

解释:

ParkingSystem parkingSystem = new ParkingSystem(1, 1, 0);
parkingSystem.addCar(1); // 返回 true ,因为有 1 个空的大车位
parkingSystem.addCar(2); // 返回 true ,因为有 1 个空的中车位
parkingSystem.addCar(3); // 返回 false ,因为没有空的小车位
parkingSystem.addCar(1); // 返回 false ,因为没有空的大车位,唯一一个大车位已经被占据了

提示:

0 <= big, medium, small <= 1000 carType 取值为 1, 2 或 3 最多会调用 addCar 函数 1000 次

解题思路

比较简单,基础定义类型,判断是否存在不同类型的空车位即可

Golang 实现代码如下:

type ParkingSystem struct {
	big    int
	medium int
	small  int
}

func Constructor(big int, medium int, small int) ParkingSystem {
	return ParkingSystem{big, medium, small}
}

func (this *ParkingSystem) AddCar(carType int) bool {
    switch carType {
        case 1:
            if this.big > 0 {
                this.big--
                return true
            }
        case 2:
            if this.medium > 0 {
                this.medium--
                return true
            }
        case 3:
            if this.small > 0 {
                this.small--
                return true
            }
        default:
            return false
    }
    return false
}

复杂度?🙌 操作的时间和空间复杂度均为常量 O(1)

优化点?复杂度上没必要了,想想可扩展性以及后续可能的使用场景,如下:

  • 车子驶离车位
  • 若允许小车停在更大的车位,如何判断及操作?
  • 固定车位(私家车位)只允许标识为固定车位的车驶入,系统如何扩展设计

总结

题是简单的,但是后续系统可使用场景可开阔下产品思维,作为面试题也是不错的~