周赛笔记232


一、字符串交换相等

给你长度相等的两个字符串 s1s2 。一次 字符串交换 操作的步骤如下:选出某个字符串中的两个下标(不必不同),并交换这两个下标所对应的字符。

如果对 其中一个字符串 执行 最多一次字符串交换 就可以使两个字符串相等,返回 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,好抽象

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录