题目描述
这是 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 原题链接和其他优选题解。