本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。
3692. 众数频率字符 - 力扣（LeetCode）
题目类型
#哈希 #计数
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def majorityFrequencyGroup(self, s: str) -> str:
cnt = Counter(s)
d = defaultdict(int)
for v in cnt.values():
d[v] += 1
mx = max(d.values())
mxk = 0
for k, v in d.items():
if v == mx:
mxk = max(mxk, k)
return ''.join(k for k, v in cnt.items() if v == mxk)3693. 爬楼梯 II - 力扣（LeetCode）
题目类型
#DP
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def climbStairs(self, n: int, costs: List[int]) -> int:
f = [inf] * (n + 1)
f[0] = 0
for i in range(n):
for j in range(i + 1, min(n, i + 3) + 1):
f[j] = min(f[j], f[i] + costs[j - 1] + (j - i) ** 2)
return f[n]3694. 删除子字符串后不同的终点 - 力扣（LeetCode）
题目类型
#前缀和
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def distinctPoints(self, s: str, k: int) -> int:
n = len(s)
fx = [0] * (n + 1)
fy = [0] * (n + 1)
for i, c in enumerate(s):
fx[i + 1] = fx[i]
fy[i + 1] = fy[i]
if c in 'LR':
fx[i + 1] += 1 if c == 'L' else -1
if c in 'UD':
fy[i + 1] += 1 if c == 'U' else -1
ans = set()
for i in range(n - k + 1):
dx = fx[i] + fx[-1] - fx[i + k]
dy = fy[i] + fy[-1] - fy[i + k]
ans.add((dx, dy))
return len(ans)3695. 交换元素后的最大交替和 - 力扣（LeetCode）
题目类型
#并查集 #置换环 #排序
解题思路
寻找联通区块，在区块中对元素进行交换，可以通过排序，使得较小元素位于奇数下标，较大元素位于偶数下标。
示例代码
python
class Solution:
def maxAlternatingSum(self, nums: List[int], swaps: List[List[int]]) -> int:
n = len(nums)
d = defaultdict(list)
for x, y in swaps:
d[x].append(y)
d[y].append(x)
def dfs(x, fa):
nonlocal li
for y in d[x]:
if y == fa or vis[y]:
continue
vis[y] = True
li.append(y)
dfs(y, x)
return
ans = 0
vis = [False] * n
for i in range(n):
if vis[i]:
continue
li = [i]
vis[i] = True
dfs(i, -1)
a = [nums[j] for j in li]
a.sort()
odd = sum(j % 2 for j in li)
ans += sum(a) - 2 * sum(a[: odd])
return anspython
class Solution:
def maxAlternatingSum(self, nums: List[int], swaps: List[List[int]]) -> int:
n = len(nums)
uf = UnionFind(n)
for x, y in swaps:
uf.union_by_size(x, y)
g = defaultdict(list)
for i, x in enumerate(nums):
g[uf.find(i)].append(i)
ans = 0
for a in g.values():
b = [nums[i] for i in a]
b.sort()
odd = sum(i % 2 for i in a)
for j, x in enumerate(b):
ans += -x if j < odd else x
return anspy
class UnionFind:
def __init__(self, n: int) -> None:
self.n = n
self.parent = list(range(n))
self.rank = [1] * n
self.size = [1] * n
def find(self, x: int) -> int:
if self.parent[x] == x:
return x
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union_by_size(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.size[y_root] <= self.size[x_root]:
self.parent[y_root] = x_root
self.size[x_root] += self.size[y_root]
else:
self.parent[x_root] = y_root
self.size[y_root] += self.size[x_root]
def union_rank(self, x: int, y: int) -> None:
x_root, y_root = self.find(x), self.find(y)
if x_root != y_root:
if self.rank[y_root] <= self.rank[x_root]:
self.parent[y_root] = x_root
else:
self.parent[x_root] = y_root
if self.rank[x_root] == self.rank[y_root]:
self.rank[x_root] += 1
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)