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

二当家的白帽子 2021-10-28 21:34:58
学习 算法 设计 法学 停车

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子 https://le-yi.blog.csdn.net/ 博客原创~



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://blog.csdn.net/leyi520/article/details/120976498

  1. python定义列表 新手入门级别
  2. Liste de définition Python débutant
  3. 如何用Python实现,急!!xdm
  4. 如何用Python實現,急!!xdm
  5. Comment implémenter en python, urgent!! Xdm
  6. 新猿木子李:0基础学python培训教程 Python操作Redis之hash类型
  7. python导入模块变量后,打印的值固定不变了,大老们怎么破。
  8. Why is my rust slower than Python!
  9. 用Python给喜欢的女孩写一个办公小工具,她说棒极了!
  10. python中\t是空一个tab,那这个1.2后面怎么没空格?
  11. Il y a un onglet vide en python, alors pourquoi n'y a - t - il pas d'espace après ce 1.2?
  12. 关于python中pygame.display.set_mode()的一点小问题
  13. 猜我能否用Python编程抢到茅台?已经全部开源到GitHub了
  14. python数据分析numpy 补充短试题
  15. 2W + word long article, an article on literacy python, numpy and pandas, recommended collection!
  16. Python培训-自动化运维常用库
  17. On the magical usage and principle of weak reference in Python
  18. Formation python - bibliothèques d'exploitation et de maintenance automatisées
  19. Python培训-HTTP与HTTPS之间的区别
  20. Python有哪些高级特性?
  21. Python代码阅读(第25篇):将多行字符串拆分成列表
  22. Quelles sont les fonctionnalités avancées de python?
  23. 运用python程序编写下面的的代码
  24. Python代码阅读(第25篇):将多行字符串拆分成列表
  25. 初学者 可以帮我看一下为什么Python程序运行不了吗
  26. 初學者 可以幫我看一下為什麼Python程序運行不了嗎
  27. Python代碼閱讀(第25篇):將多行字符串拆分成列錶
  28. Les débutants peuvent - ils m'aider à voir pourquoi le programme Python ne fonctionne pas?
  29. Lecture du Code Python (article 25): diviser les chaînes multilignes en listes
  30. Écrivez le code suivant en utilisant le programme Python
  31. Python exercises
  32. Python exercises
  33. Python exercises
  34. 随机试验数据函数统计分析python
  35. Python after class exercises (junior / October 11, 2021)
  36. python使用cv2.imread()读取图片失败
  37. python使用cv2.imread()讀取圖片失敗
  38. Python n'a pas lu l'image en utilisant cv2.imread ()
  39. Error debugging is accurate to lines, match case pattern matching... The official version of Python 3.10 is really friendly
  40. 100 basic Python interview questions Part II (41-60)
  41. Angry liver half moon! Python learning route + resource summary
  42. 如何用Python编写下列程序
  43. Comment écrire les programmes suivants en python
  44. 熬夜整理了2021年Python最新学习资料,分享给学弟学妹们【大学生必备】
  45. 朋友股票亏惨了,我一怒用Python爬取了证券最新数据
  46. Python爬虫高阶:微店混淆逆向解密
  47. Python爬虫开发学习全教程第二版,爆肝十万字【建议收藏】
  48. 我用Python逆向登录世界上最大的游戏平台,steam加密手段有多高明【内附源码】
  49. 我用Python爬取1000封情书助力室友表白班花,却反转再反转...原来这就是班花的终极秘密!
  50. 我用Python爬取了五千张美女图壁纸,每天一张忘记初恋!
  51. 我Python采集了新榜热门内容,原来这就是别人能成为自媒体大佬的秘密!
  52. 30个Python小游戏,上班摸鱼我能玩一天【内附源码】
  53. 【JS 逆向 AES逆向加密】Python爬虫实战,日子越来越有判头了
  54. python将两个列表进行合并,合并时删除重复元素
  55. J'a i utilisé Python pour accéder aux dernières données sur les titres.
  56. Rester debout tard pour trier les derniers documents d'apprentissage de Python 2021 et les partager avec les étudiants et les jeunes filles [Must for College Students]
  57. python中sklearn版本一直是0.0
  58. La version de sklearn en Python a toujours été 0.0
  59. django 自定义中间件如何忽略部分视图函数
  60. Comment les intergiciels personnalisés Django ignorent certaines fonctions de vue