【算法学习】1603. 设计停车系统(java / c / c++ / python / go / rust)

简介: 请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。请你实现 ParkingSystem 类: ParkingSystem(int big, int medium, int small) 初始化 ParkingSystem 类,三个参数分别对应每种停车位的数目。 bool addCar(int carType) 检查是否有 carType 对应的停车位。 carType 有三种类型:大,中,小,分别用数字 1, 2 和 3 表示。一辆车只能停在 carType 对应尺寸的停车位中。如果没有空车位,请返回 false

1603. 设计停车系统:

请你给一个停车场设计一个停车系统。停车场总共有三种不同大小的车位:大,中和小,每种尺寸分别有固定数目的车位。

请你实现 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 次

分析

  • 这道算法题其实可以很简单,但是为了追求算法的优化理念,尽量难为了自己一下。
  • 需要对三种车位计数,常规的方式就是三个变量,如果为了扩展性,其实可以用hash表或者数组。
  • 题目已经规定有三种车位,而且每种车位数量不超过1000(210正好够用),所以我们可以用一个int类型(一般都是大于等于32位)变量存储三种车位的数量。
  • 所以二当家的题解重点是一个变量如何利用位运算存储三个数量(这种方式并不一定在任何语言中都能做到优化空间,仅仅是在ac了这道算法题的同时,用一种不一样的思路)。

题解

java

class ParkingSystem {
    private int counter;

    public ParkingSystem(int big, int medium, int small) {
        counter = big | medium << 10 | small << 20;
    }

    public boolean addCar(int carType) {
        // 数量存储的位置
        int bits = (carType - 1) * 10;
        // 当前数量
        int cnt  = (counter >> bits) & 0b1111111111;
        if (cnt > 0) {
            // 数量减少,上面判断了大于0,所以不会造成跨类型借位
            counter -= 1 << bits;
            return true;
        }
        return false;
    }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem obj = new ParkingSystem(big, medium, small);
 * boolean param_1 = obj.addCar(carType);
 */

c

typedef struct {
    int count;
} ParkingSystem;


ParkingSystem* parkingSystemCreate(int big, int medium, int small) {
    int count = big | medium << 10 | small << 20;
    ParkingSystem *s = (ParkingSystem *) malloc(sizeof(ParkingSystem));
    s->count = count;
    return s;
}

bool parkingSystemAddCar(ParkingSystem* obj, int carType) {
    // 数量存储的位置
    int bits = (carType - 1) * 10;
    // 当前数量
    int cnt = (obj->count >> bits) & 0b1111111111;
    if (cnt > 0) {
        // 数量减少,上面判断了大于0,所以不会造成跨类型借位
        obj->count -= 1 << bits;
        return true;
    }
    return false;
}

void parkingSystemFree(ParkingSystem* obj) {
    free(obj);
}

/**
 * Your ParkingSystem struct will be instantiated and called as such:
 * ParkingSystem* obj = parkingSystemCreate(big, medium, small);
 * bool param_1 = parkingSystemAddCar(obj, carType);
 
 * parkingSystemFree(obj);
*/

c++

class ParkingSystem {
private:
    int counter;
public:
    ParkingSystem(int big, int medium, int small) {
        counter = big | medium << 10 | small << 20;
    }

    bool addCar(int carType) {
        // 数量存储的位置
        int bits = (carType - 1) * 10;
        // 当前数量
        int cnt  = (counter >> bits) & 0b1111111111;
        if (cnt > 0) {
            // 数量减少,上面判断了大于0,所以不会造成跨类型借位
            counter -= 1 << bits;
            return true;
        }
        return false;
    }
};

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * ParkingSystem* obj = new ParkingSystem(big, medium, small);
 * bool param_1 = obj->addCar(carType);
 */

python

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.counter = big | medium << 10 | small << 20

    def addCar(self, carType: int) -> bool:
        # 数量存储的位置
        bits = (carType - 1) * 10
        # 当前数量
        cnt = (self.counter >> bits) & 0b1111111111
        if cnt > 0:
            # 数量减少,上面判断了大于0,所以不会造成跨类型借位
            self.counter -= 1 << bits
            return True
        return False



# Your ParkingSystem object will be instantiated and called as such:
# obj = ParkingSystem(big, medium, small)
# param_1 = obj.addCar(carType)

go

type ParkingSystem struct {
    counter int
}


func Constructor(big int, medium int, small int) ParkingSystem {
    return ParkingSystem{big | medium << 10 | small << 20}
}


func (this *ParkingSystem) AddCar(carType int) bool {
    // 数量存储的位置
    bits := (carType - 1) * 10
    // 当前数量
    cnt  := (this.counter >> bits) & 0b1111111111
    if cnt > 0 {
        // 数量减少,上面判断了大于0,所以不会造成跨类型借位
        this.counter -= 1 << bits
        return true
    }
    return false
}


/**
 * Your ParkingSystem object will be instantiated and called as such:
 * obj := Constructor(big, medium, small);
 * param_1 := obj.AddCar(carType);
 */

rust

struct ParkingSystem {
  counter: i32,
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl ParkingSystem {

  fn new(big: i32, medium: i32, small: i32) -> Self {
    ParkingSystem{counter:big | medium << 10 | small << 20}
  }

  fn add_car(&mut self, car_type: i32) -> bool {
    // 数量存储的位置
    let bits = (car_type - 1) * 10;
    // 当前数量
    let cnt  = (self.counter >> bits) & 0b1111111111;
    if (cnt > 0) {
      // 数量减少,上面判断了大于0,所以不会造成跨类型借位
      self.counter -= 1 << bits;
      return true;
    }
    return false;
  }
}

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * let obj = ParkingSystem::new(big, medium, small);
 * let ret_1: bool = obj.add_car(carType);
 */

在这里插入图片描述


原题传送门:https://leetcode-cn.com/problems/design-parking-system/


非常感谢你阅读本文~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://developer.aliyun.com/profile/sqd6avc7qgj7y 博客原创~

相关文章
|
1天前
|
人工智能 Java 开发者
Python与Java:两大编程语言的联系与区别
Python与Java:两大编程语言的联系与区别
|
7天前
|
算法 Java
Java中CAS算法的集中体现:Atomic原子类库,你了解吗?
【5月更文挑战第15天】Java中CAS算法的集中体现:Atomic原子类库,你了解吗?
21 1
|
7天前
|
数据采集 Java 数据挖掘
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
最新Python+OpenCV+dlib汽车驾驶员疲劳驾驶检测!,2024年最新网易云java面试
|
7天前
|
Python
2024年最全用Python写了一个电子考勤系统_用python写一个宿舍考勤系统,2024年最新1307页阿里Python面试全套真题解析在互联网火了
2024年最全用Python写了一个电子考勤系统_用python写一个宿舍考勤系统,2024年最新1307页阿里Python面试全套真题解析在互联网火了
|
8天前
|
机器学习/深度学习 人工智能 算法
食物识别系统Python+深度学习人工智能+TensorFlow+卷积神经网络算法模型
食物识别系统采用TensorFlow的ResNet50模型,训练了包含11类食物的数据集,生成高精度H5模型。系统整合Django框架,提供网页平台,用户可上传图片进行食物识别。效果图片展示成功识别各类食物。[查看演示视频、代码及安装指南](https://www.yuque.com/ziwu/yygu3z/yhd6a7vai4o9iuys?singleDoc#)。项目利用深度学习的卷积神经网络(CNN),其局部感受野和权重共享机制适于图像识别,广泛应用于医疗图像分析等领域。示例代码展示了一个使用TensorFlow训练的简单CNN模型,用于MNIST手写数字识别。
27 3
|
8天前
|
Linux C语言 iOS开发
Python初学者在不同系统上安装Python的保姆级指引_altinstall 安装路径
Python初学者在不同系统上安装Python的保姆级指引_altinstall 安装路径
|
8天前
|
算法 Python
Python中实现图论算法
Python中实现图论算法 “【5月更文挑战第20天】”
14 3
|
10天前
|
算法 搜索推荐 Java
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
【5月更文挑战第8天】🏆本文收录于「滚雪球学Java」专栏,专业攻坚指数级提升,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!!
37 8
滚雪球学Java(33):数组算法大揭秘:应用案例实战分享
|
10天前
|
编解码 Java API
Jmeter--控制器--详解,2024年最新系统学Python从零开始
Jmeter--控制器--详解,2024年最新系统学Python从零开始
|
11天前
|
Python
【python学习小案例】提升兴趣之模拟系统入侵,2024年最新面试阿里运营一般问什么
【python学习小案例】提升兴趣之模拟系统入侵,2024年最新面试阿里运营一般问什么