三亩地 三亩地SAN MU DI · CODE DIARY
ARTICLE DETAIL

日记详情

真实记录编程学习的某一天,欢迎挑你感兴趣的翻一翻。

DeepSeek LeetCode 3803. 统计残差前缀 Python3实现

DeepSeek    LeetCode 3803. 统计残差前缀 Python3实现

您给出的 totalNumbers(self, digits: List[int]) -> int 方法签名,对应的是 LeetCode 第 3483 题「不同三位偶数的数目」,而不是第 3803 题。这一题要求统计用给定数字能组成多少个不同的三位偶数。

这里提供两种典型的 Python3 解法,您可以根据数据规模和个人偏好选择。

解法一:暴力枚举 + 去重(最直观)

因为 digits 的长度最多只有 10,直接枚举所有可能的三位数组合,然后利用集合去重即可。

```python
from typing import List

class Solution:
def totalNumbers(self, digits: List[int]) -> int:
n = len(digits)
seen = set()

# 枚举百位 i,十位 j,个位 k
for i in range(n):
# 百位不能为0
if digits[i] == 0:
continue
for j in range(n):
if j == i:
continue
for k in range(n):
if k == i or k == j:
continue
# 个位必须是偶数
if digits[k] % 2 != 0:
continue
# 组成数字并加入集合去重
num = digits[i] * 100 + digits[j] * 10 + digits[k]
seen.add(num)

return len(seen)
```

解法二:基于频数表的计数(更高效)

不枚举位置,而是统计每个数字出现的次数,然后枚举合法的百位、十位和个位数字,这样能更直接地处理重复数字的情况。

```python
from typing import List
from collections import Counter

class Solution:
def totalNumbers(self, digits: List[int]) -> int:
# 统计每个数字的出现次数
cnt = Counter(digits)
ans = 0

# 枚举可能的百位数字 (1-9)
for i in range(1, 10):
if cnt[i] == 0:
continue
cnt[i] -= 1 # 使用一个 i

# 枚举可能的十位数字 (0-9)
for j in range(0, 10):
if cnt[j] == 0:
continue
cnt[j] -= 1 # 使用一个 j

# 枚举可能的个位数字 (必须是偶数)
for k in range(0, 10, 2):
if cnt[k] > 0:
ans += 1

cnt[j] += 1 # 恢复十位数字

cnt[i] += 1 # 恢复百位数字

return ans
```

复杂度分析:

· 解法一:时间复杂度 O(n³),空间复杂度 O(m),其中 m 是生成的不同数字个数。
· 解法二:时间复杂度 O(10 * 10 * 5) 即 O(1),空间复杂度 O(1)。

---

补充说明:如果您确实想问的是 LeetCode 3803 题「统计残差前缀」,其方法签名应为 def residuePrefixes(self, s: str) -> int,实现方式是使用集合维护不同字符数量。

← 返回列表