周赛笔记233


一、最大升序子数组和

class Solution:
    def maxAscendingSum(self, nums: List[int]) -> int:
        ans=[nums[0]]
        pre=nums[0]
        for i in range(1,len(nums)):
            if nums[i]>pre:
                ans[-1]+=nums[i]
            else:
                ans.append(nums[i])
            pre=nums[i]
            #print(pre,ans)
        return max(ans)

二、积压订单中的订单总数

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy,sell=[],[]
        for p,m,t in orders:
            if t==0:  #buy,
                while m and sell:
                    tmp=sell[0]
                    if tmp[0]>p: break
                    deal=min(m,tmp[1])
                    m-=deal
                    tmp[1]-=deal
                    if tmp[1]==0:
                        heapq.heappop(sell)
                if m: heapq.heappush(buy,[-p,m])
            else: #sell
                while m and buy:
                    tmp=buy[0]
                    if -tmp[0]<p: break
                    deal=min(m,tmp[1])
                    m-=deal
                    tmp[1]-=deal
                    if tmp[1]==0:
                        heapq.heappop(buy)
                if m: heapq.heappush(sell,[p,m])
        ans=sum([t[1] for t in buy+sell])
        return ans % (10**9+7)

#最小堆

三、有界数组中指定下标处的最大值

给你三个正整数 nindexmaxSum 。你需要构造一个同时满足下述所有条件的数组 nums(下标 从 0 开始 计数):

  • nums.length == n
  • nums[i]正整数 ,其中 0 <= i < n
  • abs(nums[i] - nums[i+1]) <= 1 ,其中 0 <= i < n-1
  • nums 中所有元素之和不超过 maxSum
  • nums[index] 的值被 最大化

返回你所构造的数组中的 nums[index]

class Solution:
    def maxValue(self, n: int, index: int, maxSum: int) -> int:
        l=index
        r=n-1-index

        def compu(x,l):
            if l>=x-1:
                return x*(x-1)//2+l-x+1
            else:
                return (2*x-l-1)*l//2

        lp,rp=1,maxSum
        while lp<=rp:
            mid=(lp+rp)//2
            #print(lp,rp,compu(mid,l),compu(mid,r),mid)
            if compu(mid,l)+compu(mid,r)+mid>maxSum:
                rp=mid-1
            else:
                lp=mid+1
        return min(lp,rp)

#经典二分(对答案)

四、统计异或值在范围内的数对有多少

给你一个整数数组 nums (下标从 0 开始计数)以及两个整数:lowhigh ,请返回 漂亮数对 的数目。

漂亮数对 是一个形如 (i, j) 的数对,其中 0 <= i < j < nums.lengthlow <= (nums[i] XOR nums[j]) <= high

#trie字典树

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