911. 在线选举
这个题 就是用一个list 去记录 从 time[0] - time[-1] 时,最多选票的人是谁, 到底是哪个时刻不重要,主要是记录这个点对应的人是谁,
对于每个查询 ,查找当前的t 对应time的哪个位置, 采用二分查找,找到位置之后返回人
class TopVotedCandidate:
def __init__(self, persons: List[int], times: List[int]):
dic =defaultdict(int)
self.maxper = []
maxnum = 0
self.times= times
for i in range(len(persons)):
dic[persons[i]] +=1
if dic[persons[i]] >=maxnum:
maxnum =dic[persons[i]]
self.maxper.append(persons[i])
else :
self.maxper.append(self.maxper[-1])
#print(self.maxper)
def q(self, t: int) -> int:
left,right =0,len(self.times)-1
while left<right:
mid = (left+right)//2
if self.times[mid]<=t and (mid==len(self.times)-1 or self.times[mid+1]> t):
return self.maxper[mid]
if self.times[mid] <t:
left =mid+1
elif self.times[mid]>t:
right =mid
return self.maxper[len(self.maxper)-1]
744. 寻找比目标字母大的最小字母
扫一遍 看看有没有比他大的 没有的话返回第一个
class Solution:
def nextGreatestLetter(self, letters: List[str], target: str) -> str:
for s in letters:
if ord(s)> ord(target):
return s
return letters[0]