一、字符串交换相等
给你长度相等的两个字符串 s1 和 s2 。一次 字符串交换 操作的步骤如下：选出某个字符串中的两个下标（不必不同），并交换这两个下标所对应的字符。
如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等，返回 true ；否则，返回 false 。
class Solution:
def areAlmostEqual(self, s1: str, s2: str) -> bool:
m,n=[],[]
for x,y in zip(*(s1,s2)):
if x==y:
continue
else:
m.append(x)
n.append(y)
if len(m)>2 or len(m)==1: return False
if len(m)==0: return True
if len(m)==2:
return True if set(m)==set(n) else False
#好久没python了，true要大写都忘了
二、找出星型图的中心节点
class Solution:
def findCenter(self, edges: List[List[int]]) -> int:
ans=Counter(edges[0]+edges[1])
return ans.most_common(1)[0][0]
三、最大平均通过率
一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得所有班级的平均通过率最大 。
一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
self.ans=0
n=len(classes)
sortclass=[]
for x,y in classes:
change=(x+1)/(y+1)-x/y
self.ans+=x/y
sortclass.append([change,x,y])
#print(self.ans)
sortclass.sort(key=lambda x:x[0])
def check(sortclass):
#print(sortclass)
change,x,y=sortclass.pop()
self.ans+=change
x+=1
y+=1
change=(x+1)/(y+1)-x/y
keys=[i[0] for i in sortclass]
sortclass.insert(bisect_left(keys,change),[change,x,y])
#print(sortclass)
for i in range(extraStudents):
check(sortclass)
return self.ans/n
#又超时了......
class Solution:
def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
diff=lambda x,y:(x+1)/(y+1)-x/y
q=[]
ans=0.
for x,y in classes:
ans+=x/y
#python中的优先队列是小根堆
q.append((-diff(x,y),x,y))
heapq.heapify(q)
for i in range(extraStudents):
d,x,y=heapq.heappop(q)
ans-=d
heapq.heappush(q,(-diff(x+1,y+1),x+1,y+1))
return ans/len(classes)
# copy，使用堆
class Solution:
def maxAverageRatio(self, c: List[List[int]], e: int) -> float:
q=[(-((i+1)/(j+1)-i/j),i,j) for i,j in c]
heapify(q)
for i in range(e):
v,i,j=heappop(q)
i+=1
j+=1
heappush(pq,(-((i+1)/(j+1)-i/j),i,j))
# print(q)
return sum(i/j for v,i,j in q)/len(c)
四、好子数组的最大分数
给你一个整数数组 nums （下标从 0 开始）和一个整数 k 。
一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1) 。一个 好 子数组的两个端点下标需要满足 i <= k <= j 。
请你返回好子数组的最大可能分数 。
class Solution:
def maximumScore(self, nums: List[int], k: int) -> int:
i=j=k
ans=nums[k]
n=len(nums)
m=nums[k]
while i>=0 or j<n:
while i>=0 and nums[i]>=m:
i-=1
while j<n and nums[j]>=m:
j+=1
ans=max(ans,(j-i-1)*m)
if i>=0 and j<n:
m=max(nums[i],nums[j])
elif i>=0:
m=nums[i]
elif j<n:
m=nums[j]
print(i,j,m,ans)
return ans
# copy，好抽象
