题目描述
这是 LeetCode 上的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 次
简单变量
一个简单的做法是，直接使用几个局部变量来记录。
class ParkingSystem { int big, medium, small; public ParkingSystem(int _big, int _medium, int _small) { big = _big; medium = _medium; small = _small; } public boolean addCar(int ct) { if (ct == 1 && big > 0) return big-- > 0; else if (ct == 2 && medium > 0) return medium-- > 0; else if (ct == 3 && small > 0) return small-- > 0; return false; } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(1)O(1)
哈希表
另外一个更好拓展的方法，使用哈希表来进行记录。
这样做的好处是，当增加车类型，只需要重载一个构造方法即可。
class ParkingSystem { Map<Integer, Integer> map = new HashMap<>(); public ParkingSystem(int _big, int _medium, int _small) { map.put(1, _big); map.put(2, _medium); map.put(3, _small); } public boolean addCar(int ct) { if (map.get(ct) > 0) { map.put(ct, map.get(ct) - 1); return true; } return false; } } 复制代码
- 时间复杂度：O(1)O(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 做法（用户态）即可保证线程安全与原子性。
那么对应到该题，如果我们允许同时停入不同类型的车，在不引入重量级锁的前提下，想要真正做到「同时」修改两种类型的车的车位的话，只能采用这样的「二进制分段」做法 ~
class ParkingSystem { int cnt; // [small medium big] public ParkingSystem(int _big, int _medium, int _small) { for (int i = 0; i < 30; i++) { int cur = 0; if (i < 10) { cur = (_big >> i) & 1; } else if (i < 20) { cur = (_medium >> (i - 10)) & 1; } else if (i < 30) { cur = (_small >> (i - 20)) & 1; } cnt += cur == 1 ? (1 << i) : 0; } } public boolean addCar(int ct) { int cur = countOfType(ct); if (cur > 0) { setCount(ct, cur - 1); return true; } return false; } int countOfType(int ct) { int ans = 0; int start = --ct * 10, end = start + 10; for (int i = start; i < end; i++) { if (((cnt >> i) & 1) == 1) { ans += (1 << (i - start)); } } return ans; } void setCount(int ct, int pc) { int start = --ct * 10, end = start + 10; for (int i = start; i < end; i++) { if (((pc >> (i - start)) & 1) == 1) { cnt |= (1 << i); } else { cnt &= ~(1 << i); } } } } 复制代码
- 时间复杂度：O(1)O(1)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1603 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
