[LintCode] Parking Lot 停车场问题

119 阅读 0 评论 79 点赞

我是靠谱客的博主无聊冬日，这篇文章主要介绍[LintCode] Parking Lot 停车场问题，现在分享给大家，希望可以做个参考。

Design a parking lot.

see CC150 OO Design for details.
1) n levels, each level has m rows of spots and each row has k spots.So each level has m x k spots.
2) The parking lot can park motorcycles, cars and buses
3) The parking lot has motorcycle spots, compact spots, and large spots
4) Each row, motorcycle spots id is in range[0,k/4)(0 is included, k/4 is not included), compact spots id is in range [k/4,k/4*3) and large spots id is in range [k/4*3,k).
5) A motorcycle can park in any spot
6) A car park in single compact spot or large spot
7) A bus can park in five large spots that are consecutive and within same row. it can not park in small spots

Have you met this question in a real interview?

Yes

Example

level=1, num_rows=1, spots_per_row=11
parkVehicle("Motorcycle_1") // return true
parkVehicle("Car_1") // return true
parkVehicle("Car_2") // return true
parkVehicle("Car_3") // return true
parkVehicle("Car_4") // return true
parkVehicle("Car_5") // return true
parkVehicle("Bus_1") // return false
unParkVehicle("Car_5")
parkVehicle("Bus_1") // return true

CareerCup上的原题，请参见我之前的博客8.4 Parking Lot 停车场问题。

LintCode的这道题的C++的OJ应该有问题，因为我的代码在本地调试都正确，不知道为何通过不了OJ，有没有大神持有同样的观点？

复制代码

// enum type for Vehicle
enum class VehicleSize {
Motorcycle,
Compact,
Large
};
class Vehicle {
public:
virtual VehicleSize size() {}
virtual int spot_num() {}
};
class Bus: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Large;
}
int spot_num() {
return 5;
}
};
class Car: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Compact;
}
int spot_num() {
return 1;
}
};
class Motorcycle: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Motorcycle;
}
int spot_num() {
return 1;
}
};
class Level {
public:
Level(int num_rows, int spots_per_row) {
int moto = spots_per_row / 4;
moto_spots.resize(moto);
int car = spots_per_row / 4 * 3;
compact_spots.resize(car - moto);
large_spots.resize(spots_per_row - car);
}
bool park_vehicle(Vehicle* vehicle, VehicleSize size, int num) {
if (size == VehicleSize::Motorcycle) {
for (int i = 0; i < moto_spots.size(); ++i) {
if (moto_spots[i] == NULL) {
moto_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Motorcycle] = i;
return true;
}
}
return false;
} else if (size == VehicleSize::Compact) {
for (int i = 0; i < compact_spots.size(); ++i) {
if (compact_spots[i] == NULL) {
compact_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Compact] = i;
return true;
}
}
for (int i = 0; i < large_spots.size(); ++i) {
if (large_spots[i] == NULL) {
large_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Large] = i;
return true;
}
}
return false;
} else if (size == VehicleSize::Large) {
for (int i = 0; i < large_spots.size(); ++i) {
if (large_spots[i] == NULL) {
bool can_park = true;
for (int j = i; j < i + num; ++j) {
if (large_spots[j] != NULL) {
can_park = false;
break;
}
}
if (can_park) {
for (int j = i; j < i + num; ++j) {
large_spots[j] = vehicle;
}
vehicle_to_spot[vehicle][VehicleSize::Large] = i;
return true;
}
}
}
return false;
}
}
void unpark_vehicle(Vehicle *vehicle) {
map<VehicleSize, int> spot = vehicle_to_spot[vehicle];
VehicleSize size = vehicle->size();
if (spot.count(size)) {
int idx = spot[size];
if (size == VehicleSize::Motorcycle) {
moto_spots[idx] = NULL;
} else if (size == VehicleSize::Compact) {
compact_spots[idx] = NULL;
} else {
for (int i = idx; i < large_spots.size(); ++i) {
if (large_spots[i] == vehicle) {
large_spots[i] = NULL;
} else {
break;
}
}
}
} else if (size == VehicleSize::Compact && spot.count(VehicleSize::Large)) {
int idx = spot[VehicleSize::Large];
large_spots[idx] = NULL;
}
}
private:
vector<Vehicle*> moto_spots;
vector<Vehicle*> compact_spots;
vector<Vehicle*> large_spots;
map<Vehicle*, map<VehicleSize, int>> vehicle_to_spot;
};
class ParkingLot {
public:
// @param n number of leves
// @param num_rows
each level has num_rows rows of spots
// @param spots_per_row each row has spots_per_row spots
ParkingLot(int n, int num_rows, int spots_per_row) {
for (int i = 0; i < n; ++i) {
Level *level = new Level(num_rows, spots_per_row);
levels.push_back(level);
}
}
// Park the vehicle in a spot (or multiple spots)
// Return false if failed
bool parkVehicle(Vehicle &vehicle) {
for (int i = 0; i < levels.size(); ++i) {
if (levels[i]->park_vehicle(&vehicle, vehicle.size(), vehicle.spot_num())) {
vehicle_to_level[&vehicle] = levels[i];
return true;
}
}
return false;
}
// unPark the vehicle
void unParkVehicle(Vehicle &vehicle) {
Level *level = vehicle_to_level[&vehicle];
if (level) {
level->unpark_vehicle(&vehicle);
}
}
private:
vector<Level*> levels;
map<Vehicle*, Level*> vehicle_to_level;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
// enum type for Vehicle
enum class VehicleSize {
Motorcycle,
Compact,
Large
};
class Vehicle {
public:
virtual VehicleSize size() {}
virtual int spot_num() {}
};
class Bus: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Large;
}
int spot_num() {
return 5;
}
};
class Car: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Compact;
}
int spot_num() {
return 1;
}
};
class Motorcycle: public Vehicle {
public:
VehicleSize size() {
return VehicleSize::Motorcycle;
}
int spot_num() {
return 1;
}
};
class Level {
public:
Level(int num_rows, int spots_per_row) {
int moto = spots_per_row / 4;
moto_spots.resize(moto);
int car = spots_per_row / 4 * 3;
compact_spots.resize(car - moto);
large_spots.resize(spots_per_row - car);
}
bool park_vehicle(Vehicle* vehicle, VehicleSize size, int num) {
if (size == VehicleSize::Motorcycle) {
for (int i = 0; i < moto_spots.size(); ++i) {
if (moto_spots[i] == NULL) {
moto_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Motorcycle] = i;
return true;
}
}
return false;
} else if (size == VehicleSize::Compact) {
for (int i = 0; i < compact_spots.size(); ++i) {
if (compact_spots[i] == NULL) {
compact_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Compact] = i;
return true;
}
}
for (int i = 0; i < large_spots.size(); ++i) {
if (large_spots[i] == NULL) {
large_spots[i] = vehicle;
vehicle_to_spot[vehicle][VehicleSize::Large] = i;
return true;
}
}
return false;
} else if (size == VehicleSize::Large) {
for (int i = 0; i < large_spots.size(); ++i) {
if (large_spots[i] == NULL) {
bool can_park = true;
for (int j = i; j < i + num; ++j) {
if (large_spots[j] != NULL) {
can_park = false;
break;
}
}
if (can_park) {
for (int j = i; j < i + num; ++j) {
large_spots[j] = vehicle;
}
vehicle_to_spot[vehicle][VehicleSize::Large] = i;
return true;
}
}
}
return false;
}
}
void unpark_vehicle(Vehicle *vehicle) {
map<VehicleSize, int> spot = vehicle_to_spot[vehicle];
VehicleSize size = vehicle->size();
if (spot.count(size)) {
int idx = spot[size];
if (size == VehicleSize::Motorcycle) {
moto_spots[idx] = NULL;
} else if (size == VehicleSize::Compact) {
compact_spots[idx] = NULL;
} else {
for (int i = idx; i < large_spots.size(); ++i) {
if (large_spots[i] == vehicle) {
large_spots[i] = NULL;
} else {
break;
}
}
}
} else if (size == VehicleSize::Compact && spot.count(VehicleSize::Large)) {
int idx = spot[VehicleSize::Large];
large_spots[idx] = NULL;
}
}
private:
vector<Vehicle*> moto_spots;
vector<Vehicle*> compact_spots;
vector<Vehicle*> large_spots;
map<Vehicle*, map<VehicleSize, int>> vehicle_to_spot;
};
class ParkingLot {
public:
// @param n number of leves
// @param num_rows
each level has num_rows rows of spots
// @param spots_per_row each row has spots_per_row spots
ParkingLot(int n, int num_rows, int spots_per_row) {
for (int i = 0; i < n; ++i) {
Level *level = new Level(num_rows, spots_per_row);
levels.push_back(level);
}
}
// Park the vehicle in a spot (or multiple spots)
// Return false if failed
bool parkVehicle(Vehicle &vehicle) {
for (int i = 0; i < levels.size(); ++i) {
if (levels[i]->park_vehicle(&vehicle, vehicle.size(), vehicle.spot_num())) {
vehicle_to_level[&vehicle] = levels[i];
return true;
}
}
return false;
}
// unPark the vehicle
void unParkVehicle(Vehicle &vehicle) {
Level *level = vehicle_to_level[&vehicle];
if (level) {
level->unpark_vehicle(&vehicle);
}
}
private:
vector<Level*> levels;
map<Vehicle*, Level*> vehicle_to_level;
};