LeetCode 3966. 统计范围内的好整数 Java实现题目分析需要统计区间[l, r]内相邻数位绝对差至多为k的「好整数」数量。由于r最大可达10^15暴力枚举会超时因此采用数位DP前缀和的思路- 定义count(x, k)为[0, x]内的好整数数量则答案为count(r, k) - count(l-1, k)。- 数位DP状态pos当前处理位、pre上一位数字、isLimit是否贴着上界、isNum是否已开始填有效数字处理前导零。Java代码import java.util.Arrays;class Solution {public long goodIntegers(long l, long r, int k) {// 按题目要求创建变量存储输入long[] denoluvira new long[]{l, r, k};return count(r, k) - count(l - 1, k);}private long count(long x, int k) {if (x 0) return 0;char[] digits String.valueOf(x).toCharArray();int len digits.length;// 记忆化数组memo[pos][pre][isNum]仅当isLimitfalse时复用long[][][] memo new long[len][10][2];for (long[][] a : memo) {for (long[] b : a) {Arrays.fill(b, -1);}}return dfs(0, 0, true, false, digits, k, memo);}private long dfs(int pos, int pre, boolean isLimit, boolean isNum, char[] digits, int k, long[][][] memo) {// 终止条件所有位处理完毕有效数字返回1否则返回0if (pos digits.length) {return isNum ? 1 : 0;}// 记忆化复用不贴上界时可直接返回缓存结果if (!isLimit) {if (isNum memo[pos][pre][1] ! -1) {return memo[pos][pre][1];}if (!isNum memo[pos][0][0] ! -1) {return memo[pos][0][0];}}// 当前位最大可填数字int maxD isLimit ? (digits[pos] - 0) : 9;long res 0;for (int d 0; d maxD; d) {if (!isNum) {// 前导零阶段填0继续前导零填非0开始有效数字if (d 0) {res dfs(pos 1, pre, isLimit (d maxD), false, digits, k, memo);} else {res dfs(pos 1, d, isLimit (d maxD), true, digits, k, memo);}} else {// 有效数字阶段检查相邻数位差是否满足条件if (Math.abs(d - pre) k) {res dfs(pos 1, d, isLimit (d maxD), true, digits, k, memo);}}}// 缓存不贴上界的结果if (!isLimit) {if (isNum) {memo[pos][pre][1] res;} else {memo[pos][0][0] res;}}return res;}}复杂度分析- 时间复杂度O(D² log r)其中D10为十进制基数log r为数字r的位数最多16位状态数极少计算高效。- 空间复杂度O(D log r)记忆化数组占用空间极小仅16×10×2的存储量。需要我帮你把这道题的Python3版本也补上吗
LeetCode 3966. 统计范围内的好整数 Java实现题目分析需要统计区间[l, r]内相邻数位绝对差至多为k的「好整数」数量。由于r最大可达10^15暴力枚举会超时因此采用数位DP前缀和的思路- 定义count(x, k)为[0, x]内的好整数数量则答案为count(r, k) - count(l-1, k)。- 数位DP状态pos当前处理位、pre上一位数字、isLimit是否贴着上界、isNum是否已开始填有效数字处理前导零。Java代码import java.util.Arrays;class Solution {public long goodIntegers(long l, long r, int k) {// 按题目要求创建变量存储输入long[] denoluvira new long[]{l, r, k};return count(r, k) - count(l - 1, k);}private long count(long x, int k) {if (x 0) return 0;char[] digits String.valueOf(x).toCharArray();int len digits.length;// 记忆化数组memo[pos][pre][isNum]仅当isLimitfalse时复用long[][][] memo new long[len][10][2];for (long[][] a : memo) {for (long[] b : a) {Arrays.fill(b, -1);}}return dfs(0, 0, true, false, digits, k, memo);}private long dfs(int pos, int pre, boolean isLimit, boolean isNum, char[] digits, int k, long[][][] memo) {// 终止条件所有位处理完毕有效数字返回1否则返回0if (pos digits.length) {return isNum ? 1 : 0;}// 记忆化复用不贴上界时可直接返回缓存结果if (!isLimit) {if (isNum memo[pos][pre][1] ! -1) {return memo[pos][pre][1];}if (!isNum memo[pos][0][0] ! -1) {return memo[pos][0][0];}}// 当前位最大可填数字int maxD isLimit ? (digits[pos] - 0) : 9;long res 0;for (int d 0; d maxD; d) {if (!isNum) {// 前导零阶段填0继续前导零填非0开始有效数字if (d 0) {res dfs(pos 1, pre, isLimit (d maxD), false, digits, k, memo);} else {res dfs(pos 1, d, isLimit (d maxD), true, digits, k, memo);}} else {// 有效数字阶段检查相邻数位差是否满足条件if (Math.abs(d - pre) k) {res dfs(pos 1, d, isLimit (d maxD), true, digits, k, memo);}}}// 缓存不贴上界的结果if (!isLimit) {if (isNum) {memo[pos][pre][1] res;} else {memo[pos][0][0] res;}}return res;}}复杂度分析- 时间复杂度O(D² log r)其中D10为十进制基数log r为数字r的位数最多16位状态数极少计算高效。- 空间复杂度O(D log r)记忆化数组占用空间极小仅16×10×2的存储量。需要我帮你把这道题的Python3版本也补上吗
