Leetcode第103场双周赛解题报告

听我说，不是太难就是数据恶心人，谢谢你，出题人

6406. K 个元素的最大和

知识点：智商
复杂度：$O(n)$
根据题意，取k次最大的即可，然后推公式

class Solution:
    def maximizeSum(self, nums: List[int], k: int) -> int:
        return int(max(nums) * k + (k * (k-1)/2))

6405. 找到两个数组的前缀公共数组

知识点：模拟
复杂度：$O(n*logn)$
根据题意，维护两个set不断求交集

from typing import List

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        ans = []
        s1 = set()
        s2 = set()
        for i in range(len(A)):
            s1.add(A[i])
            s2.add(B[i])
            ans.append(len(s1&s2))
        return ans

6403. 网格图中鱼的最大数目

知识点：广度搜索/BFS
复杂度：$O(n)$
思路：
经典的染色问题，按照染色问题的做法做即可

from typing import List

class Solution:
    def findMaxFish(self, grid: List[List[int]]) -> int:
        ly,lx = len(grid), len(grid[0])
        vis = [([0]*lx) for i in range(ly)]
        def bfs(sx,sy):
            if vis[sy][sx]==1:
                return 0
            if grid[sy][sx]==0:
                return 0
            ans = 0
            q = [(sx,sy)]
            vis[sy][sx] = 1
            while len(q)>0:
                x,y = q.pop()
                ans += grid[y][x]
                for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
                    nx, ny = (x + dx, y + dy)
                    if lx > nx >= 0 and ly > ny >= 0 and grid[ny][nx] > 0 and vis[ny][nx] == 0:
                        vis[ny][nx] = 1
                        q.insert(0,(nx,ny))
            return ans
        return max(
            bfs(i,j) for i in range(lx) for j in range(ly)
        )

6404. 将数组清空

知识点：线段树/树状数组
复杂度：$O(n*logn)$
使用树状数组来维护，维护的内容是什么呢？是区间[l,r]有多少个数已经被处理过了
PS：做的时候线段树超时了，但是最后发现差了常数倍，跟实现、语言有关系

from typing import List

INF = 100000000

class BinaryIndexedTree:
    def __init__(self, siz, data):
        self.tree = [0] * (siz + 1)
        self.data = data
        for i in range(1, siz + 1):
            self.update(i, data[i - 1])

    def lowbit(self, x):
        return x & (-x)

    def update(self, i, delta):
        while i < len(self.tree):
            self.tree[i] += delta
            i += self.lowbit(i)

    def query(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= self.lowbit(i)
        return res

    def query_range(self, l, r):
        return self.query(r) - self.query(l - 1)


class ListNode:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        sorted_nums = nums.copy()
        sorted_nums.sort()
        mp = {}
        for k, v in enumerate(nums):
            mp[v] = k
        ans = 0
        lst = 0
        l = len(nums)

        mp_nd = {}
        head = ListNode(nums[0])
        mp_nd[nums[0]] = head
        now = head
        for i in range(1, l):
            now.next = ListNode(nums[i], now)
            mp_nd[nums[i]] = now.next
            now = now.next
        now.next = head
        head.prev = now

        bit = BinaryIndexedTree(l + 2, [0] * (l + 2))

        for i in sorted_nums:
            t = mp[i]
            if lst == t:
                ans += 1
            else:
                if lst < t:
                    ans += t - lst - bit.query_range(lst + 1, t + 1) + 1
                else:
                    ans += l - lst - bit.query_range(lst + 1, l + 1) \
                           + t - bit.query_range(1, t) + 1
            t_node = mp_nd[i]
            prev = t_node.prev
            prev.next = t_node.next
            bit.update(t + 1, 1)
            lst = mp[t_node.next.val]
        return ans