您现在的位置是:首页 >技术教程 >[LeetCode周赛复盘] 第 103 场双周赛20230429网站首页技术教程
[LeetCode周赛复盘] 第 103 场双周赛20230429
简介[LeetCode周赛复盘] 第 103 场双周赛20230429
[LeetCode周赛复盘] 第 103 场双周赛20230429
一、本周周赛总结
- T1 贪心等差数列求和。
- T2 哈希表模拟。
- T3 最大权连通分量。
- T4 树状数组。
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. 找到两个数组的前缀公共数组
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. 网格图中鱼的最大数目
1. 题目描述
2. 思路分析
- 这题放在T3还标个hard,可能是出题人摆烂了吧。
- 200. 岛屿数量
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. 将数组清空
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
参考链接
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。