3745. 三元素表达式的最大值 - 力扣（LeetCode）
题目类型
#排序
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def maximizeExpressionOfThree(self, nums: List[int]) -> int:
nums.sort()
return nums[-1] + nums[-2] - nums[0]3746. 等量移除后的字符串最小长度 - 力扣（LeetCode）
题目类型
#贪心
解题思路
参考：这道题很简单！
示例代码
python
class Solution:
def minLengthAfterRemovals(self, s: str) -> int:
cnta = s.count('a')
cntb = len(s) - cnta
return abs(cnta - cntb)3747. 统计移除零后不同整数的数目 - 力扣（LeetCode）
题目类型
#数位DP #数学
解题思路
剔除十进制为存在 0 的数即为答案。
示例代码
python
class Solution:
def count_numbers_in_range(self, low: int, high: int) -> int:
n = len(str(high))
diff = n - len(str(low))
high = list(map(int, str(high)))
low = list(map(int, str(low).zfill(n)))
@lru_cache(None)
def dfs(i: int, limit_low: bool, limit_high: bool, is_num: bool, has_zero) -> int:
if i == len(high):
return int(is_num and has_zero)
res = 0
if i < diff and not is_num:
res += dfs(i + 1, True, False, False, False)
lo = low[i] if limit_low else 0
hi = high[i] if limit_high else 9
for d in range(max(lo, 1 - is_num), hi + 1):
res += dfs(
i + 1,
limit_low and d == lo,
limit_high and d == hi,
True,
has_zero or (is_num and d == 0)
)
return res
ans = dfs(0, True, True, False, False)
dfs.cache_clear()
return ans
def countDistinct(self, n: int) -> int:
return n - self.count_numbers_in_range(1, n)3748. 统计稳定子数组的数目 - 力扣（LeetCode）
题目类型
#前缀和 #二分 #树状数组 #线段树 #离线查询
解题思路
统计连续的稳定子数组区间大小，按查询判断左右边界是否在同一区间，不在同一区间，着重判断左边界重新计算区间长度，右边界记录在前缀和中无需特判。
线段树幺元定义，如下：
- length，区间长度
- cnt，区间稳定子数组个数
- prefix，区间稳定子数组最大前缀
- suffix，区间稳定子数组最大后缀
- left value，左边界元素
- right value，右边界元素
示例代码
python
class Solution:
def countStableSubarrays(
self, nums: List[int], queries: List[List[int]]
) -> List[int]:
n = len(nums)
cnt = 0
pre = [0] * (n + 1)
for i, x in enumerate(nums):
if i > 0 and x < nums[i - 1]:
cnt = 0
cnt += 1
pre[i + 1] = pre[i] + cnt
nxt = [0] * n
nxt[-1] = n
for i in range(n - 2, -1, -1):
nxt[i] = nxt[i + 1] if nums[i] <= nums[i + 1] else i + 1
ans = [0] * len(queries)
for i, (l, r) in enumerate(queries):
l2 = nxt[l]
if l2 > r:
m = r - l + 1
ans[i] = m * (m + 1) // 2
continue
m = l2 - l
ans[i] = m * (m + 1) // 2 + pre[r + 1] - pre[l2]
return anspython
class Solution:
def countStableSubarrays(
self, nums: List[int], queries: List[List[int]]
) -> List[int]:
n = len(nums)
def op(a, b):
if a[0] == 0:
return b
if b[0] == 0:
return a
da, ca, pa, sa, la, ra = a
db, cb, pb, sb, lb, rb = b
res = [da + db, ca + cb, pa, sb, la, rb]
if ra <= lb:
res[1] += sa * pb
if pa == da:
res[2] += pb
if sb == db:
res[3] += sa
return res
e = (0, 0, 0, 0, 0, 0)
segTree = SegmentTree(op, e, [(1, 1, 1, 1, v, v) for v in nums])
ans = [0] * len(queries)
for i, (l, r) in enumerate(queries):
ans[i] = segTree.prod(l, r + 1)[1]
return anspy
import typing
class SegTree:
__slots__ = ["_op", "_e", "_n", "_log", "_size", "_d"]
def __init__(self, op: typing.Callable[[typing.Any, typing.Any], typing.Any],
e: typing.Any,
v: typing.Union[int, typing.List[typing.Any]]) -> None:
"""
Args:
op: maintain operation function, such as add, max, min, etc.
e: initial value of the segment tree
v: initial value of the array
"""
self._op = op
self._e = e
if isinstance(v, int):
v = [e] * v
self._n = len(v)
self._log = (self._n - 1).bit_length()
self._size = 1 << self._log
self._d = [e] * (2 * self._size)
for i in range(self._n):
self._d[self._size + i] = v[i]
for i in range(self._size - 1, 0, -1):
self._update(i)
def set(self, p: int, x: typing.Any) -> None:
assert 0 <= p < self._n
p += self._size
self._d[p] = x
for i in range(1, self._log + 1):
self._update(p >> i)
def get(self, p: int) -> typing.Any:
assert 0 <= p < self._n
return self._d[p + self._size]
def prod(self, left: int, right: int) -> typing.Any:
assert 0 <= left <= right <= self._n
sml = self._e
smr = self._e
left += self._size
right += self._size
while left < right:
if left & 1:
sml = self._op(sml, self._d[left])
left += 1
if right & 1:
right -= 1
smr = self._op(self._d[right], smr)
left >>= 1
right >>= 1
return self._op(sml, smr)
def all_prod(self) -> typing.Any:
return self._d[1]
def max_right(self, left: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= left <= self._n
assert f(self._e)
if left == self._n:
return self._n
left += self._size
sm = self._e
first = True
while first or (left & -left) != left:
first = False
while left % 2 == 0:
left >>= 1
if not f(self._op(sm, self._d[left])):
while left < self._size:
left *= 2
if f(self._op(sm, self._d[left])):
sm = self._op(sm, self._d[left])
left += 1
return left - self._size
sm = self._op(sm, self._d[left])
left += 1
return self._n
def min_left(self, right: int,
f: typing.Callable[[typing.Any], bool]) -> int:
assert 0 <= right <= self._n
assert f(self._e)
if right == 0:
return 0
right += self._size
sm = self._e
first = True
while first or (right & -right) != right:
first = False
right -= 1
while right > 1 and right % 2:
right >>= 1
if not f(self._op(self._d[right], sm)):
while right < self._size:
right = 2 * right + 1
if f(self._op(self._d[right], sm)):
sm = self._op(self._d[right], sm)
right -= 1
return right + 1 - self._size
sm = self._op(self._d[right], sm)
return 0
def _update(self, k: int) -> None:
self._d[k] = self._op(self._d[2 * k], self._d[2 * k + 1])- 本文链接：https://io.helltractor.top/posts/contest/leetcode-weekly/lc-weekly-contest-476
- 版权声明：本博客所有文章除特别声明外，均默认采用 CC BY-NC-SA 许可协议。
