[LintCode] Parking Lot 停车场问题-阿里云开发者社区

开发者社区> 开发与运维> 正文

[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

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

本文转自博客园Grandyang的博客,原文链接:停车场问题[LintCode] Parking Lot ,如需转载请自行联系原博主。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
开发与运维
使用钉钉扫一扫加入圈子
+ 订阅

集结各类场景实战经验,助你开发运维畅行无忧

其他文章