Hard
题目描述
无零整数是不包含数字0的正整数。
给定整数n，计算满足以下条件的数对(a, b)的数量：
- a和b都是无零整数
- a + b = n
返回表示此类数对数量的整数。
示例 1：
输入：n = 2
输出：1
解释：唯一的数对是 (1, 1)。
示例 2：
输入：n = 3
输出：2
解释：数对是 (1, 2) 和 (2, 1)。
示例 3：
输入：n = 11
输出：8
解释：数对是 (2, 9), (3, 8), (4, 7), (5, 6), (6, 5), (7, 4), (8, 3), 和 (9, 2)。
注意 (1, 10) 和 (10, 1) 不满足条件，因为 10 包含数字 0。
约束条件：
- 2 <= n <= 10^15
提示：
- 使用数位DP处理n的十进制表示
- 在每一位上，跟踪是否有进位以及a或b是否已使用过零
- 通过选择a和b的数字来转移状态，使它们（带进位）加起来等于n的当前数字
- 当n本身是无零数时，减去任一数字包含零的情况
解题思路
这是一道经典的数位DP问题。我们需要统计满足条件的数对(a,b)，使得a+b=n且a,b都是无零数。
核心思路： 使用数位DP枚举所有可能的数对。从最高位开始，逐位构造数字a和b，确保：
- 每一位的数字都不为0
- 对应位的数字相加（考虑进位）等于n的对应位
- 最终a+b=n
状态设计：
pos：当前处理的位置（从高位到低位）carry：上一位的进位（0或1）tight_a：a是否贴着上界tight_b：b是否贴着上界started_a：a是否已经开始（处理前导零）started_b：b是否已经开始（处理前导零）
状态转移： 对于当前位，枚举a和b的所有可能数字组合，满足：
digit_a + digit_b + carry = target_digit + next_carry * 10- 其中
target_digit是n在当前位的数字
边界处理： 需要特别处理前导零的情况，确保构造出的数字a和b都是有效的正整数。
**推荐解法：**记忆化数位DP，时间复杂度相对较优。
代码实现
class Solution {
public:
long long countNoZeroPairs(long long n) {
string s = to_string(n);
int len = s.length();
map<tuple<int,int,bool,bool,bool,bool>, long long> memo;
function<long long(int, int, bool, bool, bool, bool)> dp = [&](
int pos, int carry, bool tight_a, bool tight_b, bool started_a, bool started_b
) -> long long {
if (pos == len) {
return (started_a && started_b) ? 1 : 0;
}
auto state = make_tuple(pos, carry, tight_a, tight_b, started_a, started_b);
if (memo.count(state)) return memo[state];
int target = s[pos] - '0';
long long result = 0;
for (int digit_a = 0; digit_a <= 9; digit_a++) {
if (!started_a && digit_a == 0) {
// a还未开始，可以继续前导零
for (int digit_b = 0; digit_b <= 9; digit_b++) {
if (!started_b && digit_b == 0) {
// 两个数都还是前导零
if (carry == target) {
result += dp(pos + 1, 0, tight_a, tight_b, false, false);
}
} else {
// b开始了，a还是前导零
if (digit_b + carry == target) {
bool new_tight_b = tight_b && (digit_b == target);
result += dp(pos + 1, 0, tight_a, new_tight_b, false, true);
} else if (digit_b + carry == target + 10) {
bool new_tight_b = tight_b && (digit_b == target);
result += dp(pos + 1, 1, tight_a, new_tight_b, false, true);
}
}
}
} else {
// a已经开始
if (digit_a == 0) continue; // a不能有0
for (int digit_b = 1; digit_b <= 9; digit_b++) {
int sum = digit_a + digit_b + carry;
if (sum == target) {
bool new_tight_a = tight_a && (digit_a == (started_a ? 9 : target));
bool new_tight_b = tight_b && (digit_b == target - digit_a - carry);
result += dp(pos + 1, 0, new_tight_a, new_tight_b, true, true);
} else if (sum == target + 10) {
bool new_tight_a = tight_a && (digit_a == (started_a ? 9 : target));
bool new_tight_b = tight_b && (digit_b == target - digit_a - carry + 10);
result += dp(pos + 1, 1, new_tight_a, new_tight_b, true, true);
}
}
}
}
return memo[state] = result;
};
return dp(0, 0, true, true, false, false);
}
};
class Solution:
def countNoZeroPairs(self, n: int) -> int:
s = str(n)
length = len(s)
memo = {}
def dp(pos, carry, tight_a, tight_b, started_a, started_b):
if pos == length:
return 1 if started_a and started_b else 0
state = (pos, carry, tight_a, tight_b, started_a, started_b)
if state in memo:
return memo[state]
target = int(s[pos])
result = 0
for digit_a in range(10):
if not started_a and digit_a == 0:
# a还未开始，可以继续前导零
for digit_b in range(10):
if not started_b and digit_b == 0:
# 两个数都还是前导零
if carry == target:
result += dp(pos + 1, 0, tight_a, tight_b, False, False)
else:
# b开始了，a还是前导零
if digit_b + carry == target:
new_tight_b = tight_b and (digit_b == target)
result += dp(pos + 1, 0, tight_a, new_tight_b, False, True)
elif digit_b + carry == target + 10:
new_tight_b = tight_b and (digit_b == target)
result += dp(pos + 1, 1, tight_a, new_tight_b, False, True)
else:
# a已经开始
if digit_a == 0:
continue # a不能有0
for digit_b in range(1, 10):
total = digit_a + digit_b + carry
if total == target:
new_tight_a = tight_a and (digit_a == 9 if started_a else digit_a == target)
new_tight_b = tight_b and (digit_b == target - digit_a - carry)
result += dp(pos + 1, 0, new_tight_a, new_tight_b, True, True)
elif total == target + 10:
new_tight_a = tight_a and (digit_a == 9 if started_a else digit_a == target)
new_tight_b = tight_b and (digit_b == target - digit_a - carry + 10)
result += dp(pos + 1, 1, new_tight_a, new_tight_b, True, True)
memo[state] = result
return result
return dp(0, 0, True, True, False, False)
public class Solution {
private Dictionary<(int,int,bool,bool,bool,bool), long> memo;
private string s;
public long CountNoZeroPairs(long n) {
s = n.ToString();
memo = new Dictionary<(int,int,bool,bool,bool,bool), long>();
return DP(0, 0, true, true, false, false);
}
private long DP(int pos, int carry, bool tightA, bool tightB, bool startedA, bool startedB) {
if (pos == s.Length) {
return (startedA && startedB) ? 1 : 0;
}
var state = (pos, carry, tightA, tightB, startedA, startedB);
if (memo.ContainsKey(state)) {
return memo[state];
}
int target = s[pos] - '0';
long result = 0;
for (int digitA = 0; digitA <= 9; digitA++) {
if (!startedA && digitA == 0) {
// a还未开始，可以继续前导零
for (int digitB = 0; digitB <= 9; digitB++) {
if (!startedB && digitB == 0) {
// 两个数都还是前导零
if (carry == target) {
result += DP(pos + 1, 0, tightA, tightB, false, false);
}
} else {
// b开始了，a还是前导零
if (digitB + carry == target) {
bool newTightB = tightB && (digitB == target);
result += DP(pos + 1, 0, tightA, newTightB, false, true);
} else if (digitB + carry == target + 10) {
bool newTightB = tightB && (digitB == target);
result += DP(pos + 1, 1, tightA, newTightB, false, true);
}
}
}
} else {
// a已经开始
if (digitA == 0) continue; // a不能有0
for (int digitB = 1; digitB <= 9; digitB++) {
int sum = digitA + digitB + carry;
if (sum == target) {
bool newTightA = tightA && (digitA == (startedA ? 9 : target));
bool newTightB = tightB && (digitB == target - digitA - carry);
result += DP(pos + 1, 0, newTightA, newTightB, true, true);
} else if (sum == target + 10) {
bool newTightA = tightA && (digitA == (startedA ? 9 : target));
bool newTightB = tightB && (digitB == target - digitA - carry + 10);
result += DP(pos + 1, 1, newTightA, newTightB, true, true);
}
}
}
}
return memo[state] = result;
}
}
var countNoZeroPairs = function(n) {
function hasZero(num) {
return num.toString().includes('0');
}
let count = 0;
for (let a = 1; a < n; a++) {
let b = n - a;
if (b > 0 && !hasZero(a) && !hasZero(b)) {
count++;
}
}
return count;
};
复杂度分析
| 指标 | 复杂度 |
|---|---|
| 时间 | - |
| 空间 | - |