当前位置: 面试刷题>> 停车问题 (经典算法题500道)


题目描述补充

题目:停车问题

在一个繁忙的城市中,有一个大型停车场,该停车场有多个区域,每个区域都有一定数量的停车位。车辆进入停车场时,需要找到一个可用的停车位。停车场管理系统需要高效地处理停车请求,并尽可能快地分配停车位。具体需求如下:

  1. 停车场数据结构:设计一个停车场的数据结构,包括多个区域,每个区域包含一定数量的停车位。
  2. 停车请求处理:当车辆请求停车时,系统需要搜索整个停车场,找到第一个可用的停车位,并返回其位置和区域信息。
  3. 停车位释放:当车辆离开时,对应的停车位应被标记为可用,以便后续车辆使用。
  4. 性能要求:考虑到停车场可能非常大且频繁接收停车请求,系统需要高效运作,尽量减少搜索时间。

PHP 示例代码

class ParkingLot {
    private $regions;

    public function __construct($regions) {
        $this->regions = $regions;
    }

    public function findParkingSpot() {
        foreach ($this->regions as $region) {
            if (($spot = $region->findAvailableSpot()) !== null) {
                return [
                    'region' => $region->getName(),
                    'spot' => $spot
                ];
            }
        }
        return null; // 如果没有可用停车位
    }

    public function releaseSpot($regionName, $spot) {
        foreach ($this->regions as $region) {
            if ($region->getName() === $regionName) {
                $region->releaseSpot($spot);
                return true;
            }
        }
        return false; // 如果区域不存在
    }
}

class Region {
    private $name;
    private $spots;

    public function __construct($name, $spots) {
        $this->name = $name;
        $this->spots = $spots; // 假设为数组,0表示空,1表示占用
    }

    public function getName() {
        return $this->name;
    }

    public function findAvailableSpot() {
        foreach ($this->spots as $index => $occupied) {
            if (!$occupied) {
                $this->spots[$index] = 1; // 标记为已占用
                return $index;
            }
        }
        return null; // 如果没有可用停车位
    }

    public function releaseSpot($spot) {
        if (isset($this->spots[$spot]) && $this->spots[$spot] === 1) {
            $this->spots[$spot] = 0; // 释放停车位
            return true;
        }
        return false; // 如果停车位不存在或已被释放
    }
}

// 使用示例
$regions = [
    new Region('A', [0, 1, 0, 1]),
    new Region('B', [0, 0, 0, 0])
];
$parkingLot = new ParkingLot($regions);
$parkingSpot = $parkingLot->findParkingSpot();
print_r($parkingSpot); // 示例输出

Python 示例代码

class Region:
    def __init__(self, name, spots):
        self.name = name
        self.spots = [0] * len(spots)  # 0 表示空,1 表示占用

    def find_available_spot(self):
        for index, occupied in enumerate(self.spots):
            if not occupied:
                self.spots[index] = 1  # 标记为已占用
                return index
        return None

    def release_spot(self, spot):
        if 0 <= spot < len(self.spots) and self.spots[spot] == 1:
            self.spots[spot] = 0  # 释放停车位
            return True
        return False

class ParkingLot:
    def __init__(self, regions):
        self.regions = regions

    def find_parking_spot(self):
        for region in self.regions:
            spot = region.find_available_spot()
            if spot is not None:
                return {'region': region.name, 'spot': spot}
        return None

    def release_spot(self, region_name, spot):
        for region in self.regions:
            if region.name == region_name:
                return region.release_spot(spot)
        return False

# 使用示例
regions = [Region('A', [0, 1, 0, 1]), Region('B', [0, 0, 0, 0])]
parking_lot = ParkingLot(regions)
parking_spot = parking_lot.find_parking_spot()
print(parking_spot)  # 示例输出

JavaScript 示例代码

class Region {
    constructor(name, spots) {
        this.name = name;
        this.spots = spots.map(() => 0); // 0 表示空,1 表示占用
    }

    findAvailableSpot() {
        for (let i = 0; i < this.spots.length; i++) {
            if (this.spots[i] === 0) {
                this.spots[i] = 1; // 标记为已占用
                return i;
            }
        }
        return null;
    }

    releaseSpot(spot) {
        if (this.spots[spot] === 1) {
            this.spots[spot] = 0; // 释放停车位
            return true;
        }
        return false;
    }
}

class ParkingLot {
    constructor(regions) {
        this.regions = regions;
    }

    findParkingSpot() {
        for (let region of this.regions) {
            let spot = region.findAvailableSpot();
            if (spot !== null) {
                return { region: region.name, spot: spot };
            }
        }
        return null;
    }

    releaseSpot(regionName, spot) {
        for (let region of this.regions) {
            if (region.name === regionName) {
                return region.releaseSpot(spot);
            }
        }
        return false;
    }
}

// 使用示例
const regions = [
    new Region('A', [0, 1, 0, 1]),
    new Region('B', [0, 0, 0, 0])
];
const parkingLot = new ParkingLot(regions);
const parkingSpot = parkingLot.findParkingSpot();
console.log(parkingSpot); // 示例输出

码小课网站中有更多相关内容分享给大家学习,欢迎访问。

推荐面试题