LC 1603. 设计停车系统
题目描述
这是 LeetCode 上的 1603. 设计停车系统 ,难度为 简单。
请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。
请你实现 ParkingSystem 类:
- ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,三个参数分别对应每种停车位的数目。
- bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位,请返回 false ,否则将该车停入车位并返回 true 。
示例 1:1
2
3
4
5
6
7
8
9
10
11
12输入:
["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 次
简单变量
一个简单的做法是,直接使用几个成员变量来记录。
1 |
|
- 时间复杂度:$O(1)$
- 空间复杂度:$O(1)$
哈希表
另外一个更好拓展的方法,使用哈希表来进行记录。
这样做的好处是,当增加车类型,只需要重载一个构造方法即可。
1 |
|
- 时间复杂度:$O(1)$
- 空间复杂度:$O(1)$
二进制分段
事实上,由于 $1000$ 的二进制表示只有 $10$ 位,而 $int$ 有 $32$ 位。
我们可以使用一个 $int$ 配合「位运算」来分段做。
使用 $[0,10)$ 代表 big,$[10,20)$ 表示 medium,$[20,30)$ 表示 small
PS. 这样 $int$ 分段的做法,在工程源码上也有体现:JDK
中的 ThreadPoolExecutor
使用了一个 $ctl$ 变量 ($int$ 类型) 的前 $3$ 位记录线程池的状态,后 $29$ 位记录程池中线程个数。
这样的「二进制分段压缩存储」的主要目的,不是为了减少使用一个 $int$,而是为了让「非原子性操作」变为「原子性操作」。
我们可以分析下为什么 ThreadPoolExecutor
要这么做。
当线程数量变化为某个特定值时,要修改的就不仅仅是「线程数量」,还需要修改「线程池的状态」。
由于并发环境下,如果要做到「原子性」地同时需要修改两个 $int$ 的话。只能上「重量级锁」,「重量级锁」就会涉及到「内核态」的系统调用,通常是耗时是「用户态」的上百倍。
但是如果我们将「线程数量」和「线程池的状态」合二为一之后,我们只需要修改一个 $int$,这时候只需要使用 CAS 做法(用户态)即可保证线程安全与原子性。
那么对应到该题,如果我们允许同时停入不同类型的车,在不引入重量级锁的前提下,想要真正做到「同时」修改两种类型的车的车位的话,只能采用这样的「二进制分段」做法 ~
1 |
|
- 时间复杂度:$O(1)$
- 空间复杂度:$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1603
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!