Hard
题目描述
给你两个整数 l 和 r。
如果一个整数的各位数字形成严格单调序列，即数字严格递增或严格递减，则称该整数为好数。所有单位数都被认为是好数。
如果一个整数是好数，或者它的各位数字之和是好数，则称该整数为花哨数。
返回一个整数，表示区间 [l, r]（包含端点）内花哨数的个数。
严格递增序列是指每个元素都严格大于前一个元素（如果存在）。
严格递减序列是指每个元素都严格小于前一个元素（如果存在）。
示例 1：
输入：l = 8, r = 10
输出：3
解释：
8 和 9 是单位数，所以它们是好数，因此是花哨数。
10 的数字是 [1, 0]，形成严格递减序列，所以 10 是好数，因此是花哨数。
因此，答案是 3。
示例 2：
输入：l = 12340, r = 12341
输出：1
解释：
12340
12340 不是好数，因为 [1, 2, 3, 4, 0] 不是严格单调的。
数字和是 1 + 2 + 3 + 4 + 0 = 10。
10 是好数，因为它的数字 [1, 0] 是严格递减的。因此，12340 是花哨数。
12341
12341 不是好数，因为 [1, 2, 3, 4, 1] 不是严格单调的。
数字和是 1 + 2 + 3 + 4 + 1 = 11。
11 不是好数，因为它的数字 [1, 1] 不是严格单调的。因此，12341 不是花哨数。
因此，答案是 1。
提示：
1 <= l <= r <= 10^15
解题思路
这道题需要统计区间内的"花哨数"，花哨数定义为：数字本身是好数，或者各位数字之和是好数。
解题思路
核心思想： 使用数位DP + 预处理的方法求解。
预处理好数集合：
- 生成所有由数字1-9组成的严格递增数
- 生成所有由数字0-9组成的严格递减数
- 去重得到所有好数
预处理好的数字和：
- 由于最大数是10^15，最大数字和为9×15=135
- 找出[1,135]中所有是好数的数字和
数位DP统计：
- 实现
count(bound)函数，统计≤bound且数字和为好数的数的个数 - 使用记忆化搜索，状态包括：当前位置、是否达到上界、当前数字和
- 实现
容斥原理计算最终结果：
答案 = count(r) - count(l-1) + 区间内好数个数 - 既是好数又数字和是好数的个数
关键在于数位DP的实现，需要维护当前数字和，并判断最终和是否在好数集合中。时间复杂度主要由数位DP决定，为O(log(r) × 数字和范围)。
代码实现
class Solution {
public:
vector<long long> goods;
vector<bool> good_sums;
vector<vector<vector<int>>> memo;
void generateGoods() {
set<long long> good_set;
// Generate strictly increasing numbers from digits 1-9
for (int mask = 1; mask < (1 << 9); mask++) {
long long num = 0;
for (int i = 0; i < 9; i++) {
if (mask & (1 << i)) {
num = num * 10 + (i + 1);
}
}
good_set.insert(num);
}
// Generate strictly decreasing numbers from digits 0-9
for (int mask = 1; mask < (1 << 10); mask++) {
long long num = 0;
for (int i = 9; i >= 0; i--) {
if (mask & (1 << i)) {
num = num * 10 + i;
}
}
if (num > 0) good_set.insert(num);
}
goods.assign(good_set.begin(), good_set.end());
}
bool isGood(int n) {
if (n < 10) return true;
string s = to_string(n);
bool inc = true, dec = true;
for (int i = 1; i < s.size(); i++) {
if (s[i] <= s[i-1]) inc = false;
if (s[i] >= s[i-1]) dec = false;
}
return inc || dec;
}
void generateGoodSums() {
good_sums.resize(146, false);
for (int i = 1; i <= 145; i++) {
good_sums[i] = isGood(i);
}
}
long long digitDP(const string& num, int pos, bool tight, int sum) {
if (pos == num.size()) {
return good_sums[sum] ? 1 : 0;
}
if (!tight && memo[pos][sum][0] != -1) {
return memo[pos][sum][0];
}
int limit = tight ? (num[pos] - '0') : 9;
long long result = 0;
for (int digit = 0; digit <= limit; digit++) {
if (pos == 0 && digit == 0 && num.size() > 1) {
result += digitDP(num, pos + 1, false, sum);
} else {
result += digitDP(num, pos + 1, tight && (digit == limit), sum + digit);
}
}
if (!tight) {
memo[pos][sum][0] = result;
}
return result;
}
long long count(long long n) {
if (n <= 0) return 0;
string num = to_string(n);
memo.assign(num.size(), vector<vector<int>>(146, vector<int>(1, -1)));
return digitDP(num, 0, true, 0);
}
long long countFancy(long long l, long long r) {
generateGoods();
generateGoodSums();
long long result = count(r) - count(l - 1);
// Count goods in range [l, r]
auto left = lower_bound(goods.begin(), goods.end(), l);
auto right = upper_bound(goods.begin(), goods.end(), r);
long long goodsInRange = right - left;
// Count goods in range whose digit sum is also good
long long overlap = 0;
for (auto it = left; it != right; it++) {
long long num = *it;
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
if (good_sums[sum]) overlap++;
}
return result + goodsInRange - overlap;
}
};
class Solution:
def countFancy(self, l: int, r: int) -> int:
# Generate all good numbers
goods = set()
# Strictly increasing from 1-9
for mask in range(1, 1 << 9):
num = 0
for i in range(9):
if mask & (1 << i):
num = num * 10 + (i + 1)
goods.add(num)
# Strictly decreasing from 0-9
for mask in range(1, 1 << 10):
num = 0
for i in range(9, -1, -1):
if mask & (1 << i):
num = num * 10 + i
if num > 0:
goods.add(num)
goods = sorted(goods)
# Check if a number is good
def is_good(n):
if n < 10:
return True
s = str(n)
inc = all(s[i] > s[i-1] for i in range(1, len(s)))
dec = all(s[i] < s[i-1] for i in range(1, len(s)))
return inc or dec
# Generate good sums
good_sums = [is_good(i) for i in range(146)]
# Digit DP
def count(n):
if n <= 0:
return 0
s = str(n)
memo = {}
def dp(pos, tight, digit_sum):
if pos == len(s):
return 1 if good_sums[digit_sum] else 0
if not tight and (pos, digit_sum) in memo:
return memo[(pos, digit_sum)]
limit = int(s[pos]) if tight else 9
result = 0
for digit in range(limit + 1):
if pos == 0 and digit == 0 and len(s) > 1:
result += dp(pos + 1, False, digit_sum)
else:
result += dp(pos + 1, tight and digit == limit, digit_sum + digit)
if not tight:
memo[(pos, digit_sum)] = result
return result
return dp(0, True, 0)
result = count(r) - count(l - 1)
# Count goods in range
import bisect
left_idx = bisect.bisect_left(goods, l)
right_idx = bisect.bisect_right(goods, r)
goods_in_range = right_idx - left_idx
# Count overlap
overlap = 0
for i in range(left_idx, right_idx):
num = goods[i]
digit_sum = sum(int(d) for d in str(num))
if good_sums[digit_sum]:
overlap += 1
return result + goods_in_range - overlap
public class Solution {
private List<long> goods;
private bool[] goodSums;
private Dictionary<(int, int, bool), long> memo;
public long CountFancy(long l, long r) {
GenerateGoods();
GenerateGoodSums();
long result = Count(r) - Count(l - 1);
// Count goods in range [l, r]
int leftIdx = Array.BinarySearch(goods.ToArray(), l);
if (leftIdx < 0) leftIdx = ~leftIdx;
int rightIdx = Array.BinarySearch(goods.ToArray(), r);
if (rightIdx < 0) rightIdx = ~rightIdx;
else rightIdx++;
long goodsInRange = rightIdx - leftIdx;
// Count overlap
long overlap = 0;
for (int i = leftIdx; i < rightIdx; i++) {
long num = goods[i];
int digitSum = 0;
long temp = num;
while (temp > 0) {
digitSum += (int)(temp % 10);
temp /= 10;
}
if (goodSums[digitSum]) overlap++;
}
return result + goodsInRange - overlap;
}
private void GenerateGoods() {
var goodSet = new HashSet<long>();
// Strictly increasing from 1-9
for (int mask = 1; mask < (1 << 9); mask++) {
long num = 0;
for (int i = 0; i < 9; i++) {
if ((mask & (1 << i)) != 0) {
num = num * 10 + (i + 1);
}
}
goodSet.Add(num);
}
// Strictly decreasing from 0-9
for (int mask = 1; mask < (1 << 10); mask++) {
long num = 0;
for (int i = 9; i >= 0; i--) {
if ((mask & (1 << i)) != 0) {
num = num * 10 + i;
}
}
if (num > 0) goodSet.Add(num);
}
goods = goodSet.OrderBy(x => x).ToList();
}
private bool IsGood(int n) {
if (n < 10) return true;
string s = n.ToString();
bool inc = true, dec = true;
for (int i = 1; i < s.Length; i++) {
if (s[i] <= s[i-1]) inc = false;
if (s[i] >= s[i-1]) dec = false;
}
return inc || dec;
}
private void GenerateGoodSums() {
goodSums = new bool[146];
for (int i = 1; i <= 145; i++) {
goodSums[i] = IsGood(i);
}
}
private long Count(long n) {
if (n <= 0) return 0;
string num = n.ToString();
memo = new Dictionary<(int, int, bool), long>();
return DigitDP(num, 0, true, 0);
}
private long DigitDP(string num, int pos, bool tight, int sum) {
if (pos == num.Length) {
return goodSums[sum] ? 1 : 0;
}
var key = (pos, sum, tight);
if (!tight && memo.ContainsKey(key)) {
return memo[key];
}
int limit = tight ? (num[pos] - '0') : 9;
long result = 0;
for (int digit = 0; digit <= limit; digit++) {
if (pos == 0 && digit == 0 && num.Length > 1) {
result += DigitDP(num, pos + 1, false, sum);
} else {
result += DigitDP(num, pos + 1, tight && (digit == limit), sum + digit);
}
}
if (!tight) {
memo[key] = result;
}
return result;
}
}
var countFancy = function(l, r) {
function isGood(num) {
const digits = num.toString().split('').map(Number);
if (digits.length <= 1) return true;
let increasing = true;
let decreasing = true;
for (let i = 1; i < digits.length; i++) {
if (digits[i] <= digits[i-1]) increasing = false;
if (digits[i] >= digits[i-1]) decreasing = false;
}
return increasing || decreasing;
}
function isFancy(num) {
if (isGood(num)) return true;
const digitSum = num.toString().split('').reduce((sum, digit) => sum + parseInt(digit), 0);
return isGood(digitSum);
}
function countFancyUpTo(limit) {
const s = limit.toString();
const n = s.length;
const memo = new Map();
function dp(pos, tight, started, lastDigit, isIncreasing, isDecreasing, digitSum) {
if (pos === n) {
if (!started) return 0;
const currentGood = isIncreasing || isDecreasing;
if (currentGood) return 1;
return isGood(digitSum) ? 1 : 0;
}
const key = `${pos},${tight},${started},${lastDigit},${isIncreasing},${isDecreasing},${digitSum}`;
if (memo.has(key)) return memo.get(key);
const maxDigit = tight ? parseInt(s[pos]) : 9;
let result = 0;
for (let digit = 0; digit <= maxDigit; digit++) {
const newTight = tight && (digit === maxDigit);
const newStarted = started || (digit > 0);
if (!newStarted) {
result += dp(pos + 1, newTight, false, -1, true, true, 0);
} else {
const newIsIncreasing = lastDigit === -1 ? true : (isIncreasing && digit > lastDigit);
const newIsDecreasing = lastDigit === -1 ? true : (isDecreasing && digit < lastDigit);
const newDigitSum = digitSum + digit;
result += dp(pos + 1, newTight, true, digit, newIsIncreasing, newIsDecreasing, newDigitSum);
}
}
memo.set(key, result);
return result;
}
return dp(0, true, false, -1, true, true, 0);
}
return countFancyUpTo(r) - countFancyUpTo(l - 1);
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |