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：

输入：
["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 次

简单变量

一个简单的做法是，直接使用几个成员变量来记录。

Java 代码：

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;
    }
}

C++ 代码：

class ParkingSystem {
public:
    int big, medium, small;
    ParkingSystem(int _big, int _medium, int _small) : big(_big), medium(_medium), small(_small) {}
    bool addCar(int type) {
        if (type == 1 && big > 0) { --big; return true; }
        else if (type == 2 && medium > 0) { --medium; return true; }
        else if (type == 3 && small > 0) { --small; return true; }
        return false;
    }
};

Python 代码：

class ParkingSystem:
    def __init__(self, big: int, medium: int, small: int):
        self.big = big
        self.medium = medium
        self.small = small

    def addCar(self, type_: int) -> bool:
        if type_ == 1 and self.big > 0:
            self.big -= 1
            return True
        elif type_ == 2 and self.medium > 0:
            self.medium -= 1
            return True
        elif type_ == 3 and self.small > 0:
            self.small -= 1
            return True
        return False

时间复杂度：$O(1)$
空间复杂度：$O(1)$

哈希表

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

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

Java 代码：

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;
    }
}

C++ 代码：

class ParkingSystem {
public:
    unordered_map<int, int> map;
    ParkingSystem(int _big, int _medium, int _small) {
        map[1] = _big;
        map[2] = _medium;
        map[3] = _small;
    }
    bool addCar(int type) {
        if (map[type] > 0) {
            map[type] -= 1;
            return true;
        }
        return false;
    }
};

Python 代码：

class ParkingSystem:
    def __init__(self, big, medium, small):
        self.map = {1: big, 2: medium, 3: small}

    def addCar(self, type_):
        if self.map.get(type_, 0) > 0:
            self.map[type_] -= 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 做法（用户态）即可保证线程安全与原子性。

那么对应到该题，如果我们允许同时停入不同类型的车，在不引入重量级锁的前提下，想要真正做到「同时」修改两种类型的车的车位的话，只能采用这样的「二进制分段」做法.

Java 代码：

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);
            }
        }
    }
}

C++ 代码：

class ParkingSystem {
public:
    int cnt = 0; // [small medium big]
    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;
        }
    }
    bool 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);
            }
        }
    }
};

Python 代码：

class ParkingSystem:
    def __init__(self, big: int, medium: int, small: int):
        self.cnt = 0
        for i in range(30):
            cur = 0
            if i < 10:
                cur = (big >> i) & 1
            elif i < 20:
                cur = (medium >> (i - 10)) & 1
            else:
                cur = (small >> (i - 20)) & 1
            if cur == 1:
                self.cnt |= (1 << i)

    def addCar(self, ct: int) -> bool:
        cur = self.countOfType(ct)
        if cur > 0:
            self.setCount(ct, cur - 1)
            return True
        return False
    
    def countOfType(self, ct):
        start = (ct - 1) * 10
        ans = 0
        for i in range(start, start + 10):
            if (self.cnt >> i) & 1:
                ans |= (1 << (i - start))
        return ans

    def setCount(self, ct, pc):
        start = (ct - 1) * 10
        for i in range(start, start + 10):
            if (pc >> (i - start)) & 1:
                self.cnt |= (1 << i)
            else:
                self.cnt &= ~(1 << i)

时间复杂度：$O(1)$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1603 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

哈希表位运算

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 150. 逆波兰表达式求值上一篇

LC 92. 反转链表 II 下一篇