出处：https://leetcode-cn.com/leetbook/read/designing-data-structures/rulls2/

题目描述

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位：大，中和小，每种尺寸分别有固定数目的车位。
请你实现 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 次

    实现格式

    1. class ParkingSystem {
    3.   public ParkingSystem(int big, int medium, int small) {
    5.   }
    7.   public boolean addCar(int carType) {
    9.   }
    10. }

    题解

    信号量

    使用信号量来记录 ```java public class ParkingSystem {

    private final Semaphore[] semaphores;

    public ParkingSystem(int big, int medium, int small) {

    1.   semaphores = new Semaphore[]{
    2.           new Semaphore(big),
    3.           new Semaphore(medium),
    4.           new Semaphore(small)};

    }

    public boolean addCar(int carType) {

    1.   return semaphores[carType - 1].tryAcquire();

    }

}

  1. <a name="KRHvd"></a>
  2. ## 哈希表
  3. 使用哈希表来进行记录
  4. ```java
  5. class ParkingSystem {
  6.     Map<Integer, Integer> map = new HashMap<>();
  7.     public ParkingSystem(int _big, int _medium, int _small) {
  8.         map.put(1, _big);
  9.         map.put(2, _medium);
  10.         map.put(3, _small);
  11.     }
  13.     public boolean addCar(int ct) {
  14.         if (map.get(ct) > 0) {
  15.             map.put(ct, map.get(ct) - 1);
  16.             return true;
  17.         }
  18.         return false;
  19.     }
  20. }

二进制分段

事实上，由于 1000 的二进制表示只有 10 位，而 int 有 32 位。
我们可以使用一个 int 配合「位运算」来分段做。

使用 [0,10) 代表 big，[10,20) 表示 medium，[20,30) 表示 small

PS. 这样 int 分段的做法，在工程源码上也有体现：JDK 中的 ThreadPoolExecutor 使用了一个 ctl变量 (int 类型) 的前 33 位记录线程池的状态，后 2929 位记录线程池中线程个数。

这样的「二进制分段压缩存储」的主要目的，不是为了减少使用一个 int，而是为了让「非原子性操作」变为「原子性操作」。

我们可以分析下为什么 ThreadPoolExecutor 要这么做。

当线程数量变化为某个特定值时，要修改的就不仅仅是「线程数量」，还需要修改「线程池的状态」。

由于并发环境下，如果要做到「原子性」地同时需要修改两个 int 的话。只能上「重量级锁」，「重量级锁」就会涉及到「内核态」的系统调用，通常是耗时是「用户态」的上百倍。

但是如果我们将「线程数量」和「线程池的状态」合二为一之后，我们只需要修改一个 int，这时候只需要使用 CAS 做法（用户态）即可保证线程安全与原子性。

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

  1. class ParkingSystem {
  2.     int cnt; // [small medium big]
  3.     public ParkingSystem(int _big, int _medium, int _small) {
  4.         for (int i = 0; i < 30; i++) {
  5.             int cur = 0;
  6.             if (i < 10) {
  7.                 cur = (_big >> i) & 1;
  8.             } else if (i < 20) {
  9.                 cur = (_medium >> (i - 10)) & 1;
  10.             } else if (i < 30) {
  11.                 cur = (_small >> (i - 20)) & 1;
  12.             }
  13.             cnt += cur == 1 ? (1 << i) : 0;
  14.         }
  15.     }
  17.     public boolean addCar(int ct) {
  18.         int cur = countOfType(ct);
  19.         if (cur > 0) {
  20.             setCount(ct, cur - 1);
  21.             return true;
  22.         }
  23.         return false;
  24.     }
  26.     int countOfType(int ct) {
  27.         int ans = 0;
  28.         int start = --ct * 10, end = start + 10;
  29.         for (int i = start; i < end; i++) {
  30.             if (((cnt >> i) & 1) == 1) {
  31.                 ans += (1 << (i - start));
  32.             }
  33.         }
  34.         return ans;
  35.     }
  37.     void setCount(int ct, int pc) {
  38.         int start = --ct * 10, end = start + 10;
  39.         for (int i = start; i < end; i++) {
  40.             if (((pc >> (i - start)) & 1) == 1) {
  41.                 cnt |= (1 << i);
  42.             } else {
  43.                 cnt &= ~(1 << i);
  44.             }
  45.         }
  46.     }
  47. }

使用位运算替代

  1. class ParkingSystem {
  2.     int cnt; // [small medium big]
  4.     public ParkingSystem(int _big, int _medium, int _small) {
  5.         cnt |= _big;
  6.         cnt |= (_medium << 10);
  7.         cnt |= (_small << 20);
  8.     }
  10.     public boolean addCar(int ct) {
  11.         int cur = countOfType(ct);
  12.         if (cur > 0) {
  13.             minusOne(ct);
  14.             return true;
  15.         }
  16.         return false;
  17.     }
  19.     private int countOfType(int ct) {
  20.         switch (ct) {
  21.             case 1:
  22.                 return cnt & 0x3FF; // 1-10位是1
  23.             case 2:
  24.                 return (cnt & 0xFFC00) >> 10; // 11-20位是1
  25.             default: // 3
  26.                 return (cnt & 0x3FF00000) >> 20; // 21-30位是1
  27.         }
  28.     }
  30.     private void minusOne(int ct) {
  31.         switch (ct) {
  32.             case 1:
  33.                 cnt--;
  34.                 break;
  35.             case 2:
  36.                 int mediumRes = (((cnt & 0xffc00) >> 10) - 1) << 10;
  37.                 cnt = (mediumRes | (cnt & 0x3ff003ff));
  38.                 break;
  39.             default: // 3
  40.                 int smallRes = (((cnt & 0x3ff00000) >> 20) - 1) << 20;
  41.                 cnt = (smallRes | (cnt & 0xfffff));
  42.                 break;
  43.         }
  44.     }
  45. }