极致优化：使用二进制分段实现压缩存储

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 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)$

哈希表

另外一个更好拓展的方法，使用哈希表来进行记录。

这样做的好处是，当增加车类型，只需要重载一个构造方法即可。

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)$

二进制分段

事实上，由于 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);
            }
        }
    }
}
复制代码