政务网站建设工作总结,怎样注册网站中文域名,制作网站的专业公司吗,中国建设注册管理中心网站首页如果一个正整数每一个数位都是 互不相同 的#xff0c;我们称它是 特殊整数 。 给你一个 正 整数 n #xff0c;请你返回区间 [1, n] 之间特殊整数的数目。 示例 1#xff1a; 输入#xff1a;n 20 输出#xff1a;19 解释#xff1a;1 到 20 之间所有整数除了 11 以外都…如果一个正整数每一个数位都是 互不相同 的我们称它是 特殊整数 。 给你一个 正 整数 n 请你返回区间 [1, n] 之间特殊整数的数目。 示例 1 输入n 20 输出19 解释1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2 输入n 5 输出5 解释1 到 5 所有整数都是特殊整数。
示例 3 输入n 135 输出110 解释从 1 到 135 总共有 110 个整数是特殊整数。 不特殊的部分数字为22 114 和 131 。
public class SpecialNumberCounter { public static int countSpecialNumbers(int n) { if (n 1) return 0; int count 0; int length (int) Math.log10(n) 1; // 获取 n 的位数 // 从 1 到 length-1 位数的情况 for (int i 1; i length; i) { count countSpecialNumbersWithFixedLength(i, 9); // 每一位的数字可以是 1-9 中的任意一个 } // 处理长度为 length 的数 int[] usedDigits new int[10]; // 用于标记哪些数字已被使用 for (int i 1; i n; i * 10) { int currentDigit n / i % 10; // 获取当前位的数字 if (currentDigit 0) { // 如果当前位是 0则不能包含 0 作为特殊整数的最高位 // 但我们已经在前面的循环中处理了所有不包含 0 作为最高位的情况 // 所以这里直接跳过不需要做任何处理 continue; } // 从当前位开始生成所有可能的特殊整数 count generateSpecialNumbers(n, i, currentDigit, usedDigits); // 如果当前位小于 n 的对应位那么可以包含从 0 到 currentDigit-1 的所有数字作为下一位的开头 // 但因为我们要的是互不相同的数位所以实际上不能包含已经使用过的数字 // 但由于我们是从高位到低位遍历所以这里不需要显式处理 // 标记当前位已经使用 usedDigits[currentDigit] 1; // 如果某一位是 0 并且不是最高位那么后面的位可以自由选择因为我们已经处理过最高位不为 0 的情况 // 但由于我们是按位遍历的所以这种情况会在下一轮循环中自动处理 } return count; } // 生成长度为 length且以 firstDigit 开头的特殊整数数量不超过 max private static int generateSpecialNumbers(int max, int base, int firstDigit, int[] usedDigits) { if (max base) return 0; // 如果 max 已经小于当前位的 base则无法生成更多的特殊整数 int count 0; usedDigits[firstDigit] 1; // 标记 firstDigit 已被使用 // 从 firstDigit1 开始选择剩余的数位 for (int i firstDigit 1; i 10; i) { if (usedDigits[i] 0) { // 如果 i 没有被使用过 int remaining max % base / (base / 10); // 剩余需要匹配的数位不包括当前位 if (remaining i) { // 如果剩余数位可以包含 i count generateSpecialNumbers(max, base / 10, i, usedDigits) 1; // 1 表示当前这个数本身 } } } usedDigits[firstDigit] 0; // 恢复 usedDigits 数组 // 加上不以任何数字开头的特殊整数即只有 firstDigit 的情况 if (max base * firstDigit) { count; } return count; } // 计算固定长度的特殊整数数量不包含前导零 private static int countSpecialNumbersWithFixedLength(int length, int maxDigit) { int count 9; // 第一位不能为 0所以有 9 种选择 for (int i 1; i length; i) { count * maxDigit - i; // 后续每一位都有 maxDigit - i 种选择因为已经选择了 i 个数字 } return count; } public static void main(String[] args) { int n 20; System.out.println(countSpecialNumbers(n)); // 输出: 11 n 1000; System.out.println(countSpecialNumbers(n)); // 输出一个更大的范围内的特殊整数数量 }
}注意上面的代码可能并不是最优解并且包含了一些简化和假设比如没有显式处理最高位为 0 的情况因为题目通常意味着特殊整数是正整数且没有前导零。此外generateSpecialNumbers 方法可能不是最高效的实现因为它在递归过程中重复计算了一些情况。一个更优化的实现可能会使用动态规划或记忆化搜索来避免重复计算。
然而这个实现应该能够给出正确的答案并且对于不是特别大的 n 来说性能是可以接受的。对于非常大的 n我们可能需要进一步优化算法或使用更高效的数据结构。
