您现在的位置是:首页 >技术教程 >[LeetCode周赛复盘] 第 103 场双周赛20230429网站首页技术教程

[LeetCode周赛复盘] 第 103 场双周赛20230429

七水shuliang 2023-07-08 16:00:02
简介[LeetCode周赛复盘] 第 103 场双周赛20230429

一、本周周赛总结

  • T1 贪心等差数列求和。
  • T2 哈希表模拟。
  • T3 最大权连通分量。
  • T4 树状数组。
    在这里插入图片描述

2656. K 个元素的最大和

2656. K 个元素的最大和

1. 题目描述

在这里插入图片描述

2. 思路分析

  • 不难看出每次都应该选最大的值。
  • 且每次更新完后最大值+1。
  • 那么最后的结果就是选k个数,从mx开始直到mx+k-1

3. 代码实现

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

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

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

1. 题目描述

在这里插入图片描述

2. 思路分析

 通过样例可以看出来,公共元组不考虑下标,即跟元素顺序无关,数相同即可。
  • 当跟顺序无关时,一般考虑排序或者计数。这题显然计数更合适。
  • 由于AB都是0~n-1的排列,即不重复,那么前缀出现相同元素,则数量一定是2。
  • 那么无脑cnt,出现2就贡献一个答案即可。

3. 代码实现

class Solution:
    def findThePrefixCommonArray(self, A: List[int], B: List[int]) -> List[int]:
        cnt = Counter()
        ans = []
        s = 0
        for x,y in zip(A,B):
            cnt[x] += 1
            if cnt[x] == 2:
                s += 1
            cnt[y] += 1
            if cnt[y] == 2:
                s += 1
            ans.append(s)
        return ans 

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

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

1. 题目描述

在这里插入图片描述

2. 思路分析

3. 代码实现

DIRS = ((0,1),(0,-1),(1,0),(-1,0))
class Solution:
    def findMaxFish(self, g: List[List[int]]) -> int:
        m,n = len(g),len(g[0])
        def inside(x,y):
            return 0<=x<m and 0<=y<n 
        
        def bfs(x,y):
            s = g[x][y]
            if not s :
                return 0
            g[x][y] = 0 
            q = deque([(x,y)])
            while q:
                x,y = q.popleft()
                for dx,dy in DIRS:
                    a,b = x+dx,y+dy 
                    if inside(a,b) and g[a][b]:
                        s += g[a][b]
                        g[a][b] = 0
                        q.append((a,b))
            return s         
       
        return max(bfs(i,j) for i in range(m) for j in range(n)) 

2659. 将数组清空

2659. 将数组清空

1. 题目描述

在这里插入图片描述

在这里插入图片描述

2. 思路分析

  • 观察发现,数据操作过程中,大小关系相邻的元素,相对位置在循环里是不变的。
  • 那么处理完pre开始处理cur时,只需要分类讨论下标:
    • pre在cur前边,则只需要移动一下这之间的数。然后删除cur。
    • pre在cur后边,那需要移动这俩数外边的所有数。
  • 发现数字大小关系确定即可,数字值不重要。
  • 因此用树状数组维护每个下标上有几个数(初始一个,删除则-1)。
  • 然后计算两个区间内的数字数量即可。

3. 代码实现

class BinIndexTree:
    def __init__(self, size_or_nums):  # 树状数组,下标需要从1开始
        # 如果size 是数字,那就设置size和空数据;如果size是数组,那就是a
        if isinstance(size_or_nums, int):
            self.size = size_or_nums
            self.c = [0 for _ in range(self.size + 5)]
            # self.a = [0 for _ in range(self.size + 5)]
        else:
            self.size = len(size_or_nums)
            # self.a = [0 for _ in range(self.size + 5)]
            self.c = [0 for _ in range(self.size + 5)]
            for i, v in enumerate(size_or_nums):
                self.add_point(i + 1, v)

    def add_point(self, i, v):  # 单点增加,下标从1开始
        # self.a[i] += v
        while i <= self.size:
            self.c[i] += v
            i += i & -i

    def sum_interval(self, l, r):  # 区间求和,下标从1开始,计算闭区间[l,r]上的和
        return self.sum_prefix(r) - self.sum_prefix(l - 1)

    def sum_prefix(self, i):  # 前缀求和,下标从1开始
        s = 0
        while i >= 1:
            s += self.c[i]
            # i -= i&-i
            i &= i - 1
        return s   

class Solution:
    def countOperationsToEmptyArray(self, nums: List[int]) -> int:
        n = len(nums)
        ans = 0
        tree = BinIndexTree(n)
        for i in range(1,n+1):
            tree.add_point(i,1)
        
        p = 1
        for _,i in sorted([(v,i) for i,v in enumerate(nums,start=1)]):
            if i >= p:
                ans += tree.sum_interval(p,i)
            else:
                ans += tree.sum_prefix(i) + tree.sum_interval(p,n)
       
            tree.add_point(i,-1)
            p = i 
        return ans       

参考链接

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。