This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details
Topic describes
This is 1603 on LeetCode. Design parking system.
Please design a parking system for a parking lot. There are three different sizes of parking Spaces: large, small and medium, with a fixed number of Spaces for each size.
Implement the ParkingSystem class:
- ParkingSystem(int big, int medium, int small) initializes the ParkingSystem class with three parameters corresponding to the number of each parking space.
- Bool addCar(int carType) Checks whether there is a parking space corresponding to carType. Cartypes come in three types: large, medium, and small, denoted by the numbers 1, 2, and 3, respectively. A car can only park in the parking space corresponding to the carType. Return false if there is no empty parking space, otherwise park the car in the parking space and return true.
Example 1:
Input: [" ParkingSystem addCar ", ""," addCar ", "addCar", "addCar"] [[1, 1, 0], [1], [2], [3], [1]] output: [null, true, true, false, false] ParkingSystem ParkingSystem = new ParkingSystem(1, 1, 0); parkingSystem.addCar(1); Parkingsystem.addcar (2); parkingSystem.addcar (2); Parkingsystem.addcar (3); parkingSystem.addcar (3); // Return false because there are no empty car bits parkingSystem.addcar (1); // Return false because there is no empty parking space and the only parking space is already occupiedCopy the codeTip:
- 0 <= big, medium, small <= 1000
- CarType can be 1, 2, or 3
- The addCar function will be called at most 1000 times
Simple variable
An easy way to do this is to use several local variables directly.
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; }}Copy the code- Time complexity: O(1)O(1)O(1)
- Space complexity: O(1)O(1)O(1)
Hash table
A more extensible approach is to use hash tables for recording.
The advantage of this is that when adding a car type, only one constructor needs to be overridden.
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; }}Copy the code- Time complexity: O(1)O(1)O(1)
- Space complexity: O(1)O(1)O(1)
Binary segmentation
In fact, since the binary representation of 1000 has only 10 bits, int has 32 bits.
We can use an int and “bit operation” to segment.
Use [0,10) for big, [10,20) for medium, and [20,30) for small
ThreadPoolExecutor in the JDK uses the first three bits of a CTL variable (int) to count the state of the thread pool, and the last 29 bits to count the number of threads in the pool.
The main purpose of such “binary segmented compression storage” is not to reduce the use of an int, but to make “non-atomic operations” become “atomic operations.”
We can examine why ThreadPoolExecutor does this.
When the number of threads changes to a particular value, you need to change not only the number of threads, but also the state of the thread pool.
Because in a concurrent environment, two ints need to be modified simultaneously to achieve atomicity. Only “heavyweight locks” can be placed, and “heavyweight locks” involve “kernel-mode” system calls, which typically take hundreds of times longer than “user-mode” system calls.
However, if we combine the number of threads and the state of the thread pool, we only need to change an int, and we only need to use the CAS approach (user state) to ensure thread-safety and atomicity.
So corresponding to this problem, if we allow to park in different types of cars at the same time, in the premise of not introducing heavyweight lock, to really “simultaneously” modify the parking space of the two types of cars, we can only use such “binary segmentation” method ~
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); }}}}Copy the code- Time complexity: O(1)O(1)O(1)
- Space complexity: O(1)O(1)O(1)
The last
This is the No.1603 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.