这类题目看似复杂，其实读懂后，根据题意要求一步一步分解并统计出需要的信息即可。
- 求平均时间，则需要知道startStation到endStation这段路中累计通过的人数和时间
- checkOut中可以统计累计通过的人数和时间，但是该函数中缺少startStation和startTime信息
- checkIn中统计checkOut中需要的startStation和startTime信息
- 最后信息统计完成，通过除法便得到时间均值
class UndergroundSystem(object):
def __init__(self):
self.personInfo = dict()
self.stationInfo = dict()
def checkIn(self, id, stationName, t):
"""
:type id: int
:type stationName: str
:type t: int
:rtype: None
"""
self.personInfo[id] = (stationName, t)
def checkOut(self, id, stationName, t):
"""
:type id: int
:type stationName: str
:type t: int
:rtype: None
"""
startStation = self.personInfo[id][0]
startTime = self.personInfo[id][1]
# stationInfo的键为元组：始发站，终点站； 值为元组：通过人数，累计的通过时间
if (startStation, stationName) in self.stationInfo:
self.stationInfo[(startStation, stationName)][0] += 1
self.stationInfo[(startStation, stationName)][1] += t - startTime
else:
self.stationInfo[(startStation, stationName)] = [1, t - startTime]
## 注意：不能这样分开写。因为是第一次对该字典的键和值赋初值
# self.stationInfo[(startStation,stationName)][0]=1
# self.stationInfo[(startStation,stationName)][1]=t-startTime
def getAverageTime(self, startStation, endStation):
"""
:type startStation: str
:type endStation: str
:rtype: float
"""
allPeople = self.stationInfo[(startStation, endStation)][0]
allTime = self.stationInfo[(startStation, endStation)][1]
return (allTime + 0.0) / allPeople # python2和python3的除法略有区别。统一变成浮点除法
# Your UndergroundSystem object will be instantiated and called as such:
# obj = UndergroundSystem()
# obj.checkIn(id,stationName,t)
# obj.checkOut(id,stationName,t)
# param_3 = obj.getAverageTime(startStation,endStation)
#------------------------------------------
# 或者也可以使用字典的get函数
class UndergroundSystem(object):
def __init__(self):
self.personInfo = dict()
self.stationInfo = dict()
def checkIn(self, id, stationName, t):
"""
:type id: int
:type stationName: str
:type t: int
:rtype: None
"""
self.personInfo[id] = (stationName, t)
def checkOut(self, id, stationName, t):
"""
:type id: int
:type stationName: str
:type t: int
:rtype: None
"""
startStation = self.personInfo[id][0]
startTime = self.personInfo[id][1]
count,allTime=self.stationInfo.get((startStation, stationName),(0,0)) # 字典的get函数可以赋默认值
self.stationInfo[(startStation, stationName)] = [count+1, allTime+t - startTime]
def getAverageTime(self, startStation, endStation):
"""
:type startStation: str
:type endStation: str
:rtype: float
"""
allPeople,allTime = self.stationInfo[(startStation, endStation)]
return (allTime + 0.0) / allPeople # python2和python3的除法略有区别。统一变成浮点除法
1472. 设计浏览器历史记录
- 用栈保存数据
- visit时，如果当前位置上面还有记录，则需要删除
- back和forward时，当前位置与左（右）边界比较，并再更新该位置
class BrowserHistory(object):
def __init__(self, homepage):
"""
:type homepage: str
"""
self.res=[homepage]
self.current=0 # 记录当前位置
def visit(self, url):
"""
:type url: str
:rtype: None
"""
# 以栈为例，如果当前位置上面还有记录，则需要删除
self.res=self.res[:self.current+1] # 或者del self.res[self.current + 1:]
self.res.append(url)
self.current+=1
def back(self, steps):
"""
:type steps: int
:rtype: str
"""
self.current-=steps # 更新当前位置
self.current=max(0,self.current) # 并与0比较，再更新当前位置
return self.res[self.current]
def forward(self, steps):
"""
:type steps: int
:rtype: str
"""
self.current+=steps # 更新当前位置
self.current=min(self.current,len(self.res)-1)# 并与栈的长度比较，再更新当前位置
return self.res[self.current]
# Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)
211. 添加与搜索单词 - 数据结构设计
- 待更新
面试题 03.06. 动物收容所
- 使用队列达到先进先出
- 使用两个队列，分别保存猫和狗
class AnimalShelf:
def __init__(self):
self.cat = deque()
self.dog = deque()
def enqueue(self, animal: List[int]) -> None:
if animal[1] == 0:
self.cat.append(animal)
else:
self.dog.append(animal)
def dequeueAny(self) -> List[int]:
if self.dog and self.cat:
if self.cat[0][0] > self.dog[0][0]:
return self.dog.popleft()
else:
return self.cat.popleft()
elif self.dog:
return self.dog.popleft()
elif self.cat:
return self.cat.popleft()
else:
return [-1, -1]
def dequeueDog(self) -> List[int]:
return self.dog.popleft() if self.dog else [-1, -1]
def dequeueCat(self) -> List[int]:
return self.cat.popleft() if self.cat else [-1, -1]
# Your AnimalShelf object will be instantiated and called as such:
# obj = AnimalShelf()
# obj.enqueue(animal)
# param_2 = obj.dequeueAny()
# param_3 = obj.dequeueDog()
# param_4 = obj.dequeueCat()1109. 航班预订统计
- 定义 counter[] 数组记录每站的人数变化，counter[i] 表示第 i+1 站。遍历 bookings[]：bookings[i] = [i, j, k] 表示在 i 站增加 k 人即 counters[i-1] += k，在 j+1 站减少 k 人即 counters[j] -= k
- 遍历（整理）counter[] 数组，得到每站总人数： 每站的人数为前一站人数加上当前人数变化 counters[i] += counters[i - 1]
小而美的算法技巧：差分数组
class Solution(object):
def corpFlightBookings(self, bookings, n):
"""
:type bookings: List[List[int]]
:type n: int
:rtype: List[int]
"""
counter=[0 for i in range(n)]
for i,j,k in bookings:
counter[i-1]+=k
if j<n: # 注意边界
counter[j]-=k
for i in range(1,n):
counter[i]=counter[i-1]+counter[i]
return counter393. UTF-8 编码验证
- 位运算
class Solution:
def validUtf8(self, data: List[int]) -> bool:
if not data: return False
cnt = 0 # 记录需要用10XXXXXX填充的字节数
for d in data:
if cnt == 0:
if d >> 5 == 0b110: cnt = 1
elif d >> 4 == 0b1110: cnt = 2
elif d >> 3 == 0b11110: cnt = 3
elif d >> 7 != 0:
return False
else:
if d >> 6 != 0b10: return False
cnt -= 1
return cnt == 0
作者：powcai
链接：https://leetcode.cn/problems/utf-8-validation/solution/python-zi-fu-chuan-fang-fa-jie-jue-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
- 字符串
class Solution:
def validUtf8(self, data: List[int]) -> bool:
if not data: return False
data = [bin(d)[2:].rjust(8, "0") for d in data]
# print(data)
cnt = 0
for d in data:
if cnt == 0:
if d.startswith("0"): continue
elif d.startswith("110"): cnt = 1
elif d.startswith("1110"): cnt = 2
elif d.startswith("11110"): cnt = 3
else:
return False
else:
if not d.startswith("10"): return False
cnt -= 1
return cnt == 0
作者：powcai
链接：https://leetcode.cn/problems/utf-8-validation/solution/python-zi-fu-chuan-fang-fa-jie-jue-by-powcai/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
