1
2023-05-02：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 输入：n = 20。 输出：19。
作者：福大大架构师每日一题
- 2023-05-02 北京
本文字数：3805 字
阅读完需：约 12 分钟
2023-05-02：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
输入：n = 20。
输出：19。
答案 2023-05-02：
可以通过数字组合和状态压缩的动态规划算法来解决。具体过程如下：
1.对于给定的正整数 n，求出其位数 len。
2.枚举所有小于 len 位的数字，计算其中特殊整数的总数。如果数字为 i 位，则特殊整数个数为 9 * 8 * ... * (10 - i)。
3.对于第 len 位上的数字 x，在计算期间将其提取出来。
4.如果 x 是第一个数字，则区间 [1, n] 中，第 len 位之前的数字不受限制，因此可以选取任意一个非零数字，共有 9 种可能。
5.对于区间 [1, n] 中第 len 位之前的每个数字，考虑它们与 x 组合所能得到的所有特殊整数。如果某个数字已经在当前组合中出现过，则不能再重复使用。
6.递归求解所有满足要求的数字组合，每次处理一位，直到组合中所有数字都确定下来。
7.对于区间 [1, n] 中的每个数字，检查其是否为特殊整数，并统计个数。
8.返回特殊整数的总数。
该算法的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。由于需要进行大量的数字组合枚举和状态压缩操作，实现起来较为复杂。
rust 完整代码如下：
const OFFSET: [i32; 11] = [ 0, // 0位数，一共能解决几个位 1, // 1位数，一共能解决几个位 10, // 2位数，一共能解决几个位 100, // 3位数，一共能解决几个位 1000, // 4位数，一共能解决几个位 10000, // 5位数，一共能解决几个位 100000, 1000000, 10000000, 100000000, 1000000000,];
fn count_special_numbers(n: i32) -> i32 { let len = len(n); let mut ans = 0; for i in 1..len { ans += all(i); } let first_number = n / OFFSET[len as usize]; ans += (first_number - 1) * small(len - 1, 9); ans += process(n, len, len - 1, 1 << first_number); return ans;}
// 返回n这个数字有几位fn len(mut n: i32) -> i32 { let mut ans = 0; while n != 0 { ans += 1; n /= 10; } return ans;}
// 返回所有bits位数，有几个特殊的fn all(bits: i32) -> i32 { let mut ans = 9; let mut cur = 9; for _ in 1..bits { ans *= cur; cur -= 1; } return ans;}
// bits : 8 7 6 5 4位// candidates : 8 可能性
// bits : _ _ _ 3位// candidates : 5 可能性fn small(bits: i32, candidates: i32) -> i32 { let mut ans = 1; let mut cur_candidate = candidates; for _ in 0..bits { ans *= cur_candidate; cur_candidate -= 1; } return ans;}
// num : 原始数 46531 固定// len : 原始数有几位，5位，固定// rest : 还剩几位没决定，可变参数// num : 46531// 4 _ _ _ _// 4 0~5// 4 6 _ _ _// status : 4 6 _ _ _// 哪些数字使用了，状态！在status里：// 体系学习班，状态压缩的动态规划！// int status 32位// 9 8 7 6 5 4 3 2 1 0// 1 0 1 0 0 0 0// 4 6 _ _ _ 还有几个达标的！// 哪些数字选了都在status里，用一个status变量表示数字选没选(位信息)fn process(num: i32, len: i32, rest: i32, status: i32) -> i32 { if rest == 0 { return 1; } // 46531 // ___ // 5 // 46531 / 100 -> 465 % 10 -> 5
// 比5小的有几股？0 1 2 3 4 // // n : 454012 // 45_ // 0... // 1... // 2... // 3... // 4 _ _ _ let cur = (num / OFFSET[rest as usize]) % 10; let mut cnt = 0; for i in 0..cur { if (status & (1 << i)) == 0 { cnt += 1; } } let mut ans = cnt * small(rest - 1, 9 - (len - rest)); if (status & (1 << cur)) == 0 { ans += process(num, len, rest - 1, status | (1 << cur)); } return ans;}
fn main() { let n = 135; let ans = count_special_numbers(n); println!( "The number of special numbers between 1 and {} is {}", n, ans );}
复制代码
go 完整代码如下：
package main
import "fmt"
var offset = []int{ 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,}
func countSpecialNumbers(n int) int { len := len(n) ans := 0 for i := 1; i < len; i++ { ans += all(i) } firstNumber := n / offset[len] ans += (firstNumber - 1) * small(len-1, 9) ans += process(n, len, len-1, 1<<firstNumber) return ans}
func len(n int) int { ans := 0 for n != 0 { ans++ n /= 10 } return ans}
func all(bits int) int { ans := 9 cur := 9 for i := 1; i < bits; i++ { ans *= cur cur-- } return ans}
func small(bits int, candidates int) int { ans := 1 for i := 0; i < bits; i++ { ans *= candidates candidates-- } return ans}
func process(num int, len int, rest int, status int) int { if rest == 0 { return 1 } cur := (num / offset[rest]) % 10 cnt := 0 for i := 0; i < cur; i++ { if (status & (1 << i)) == 0 { cnt++ } } ans := cnt * small(rest-1, 9-(len-rest)) if (status & (1 << cur)) == 0 { ans += process(num, len, rest-1, status|(1<<cur)) } return ans}
func main() { n := 135 ans := countSpecialNumbers(n) fmt.Printf("The number of special numbers between 1 and %d is %d\n", n, ans)}
复制代码
c 完整代码如下：
#include <stdio.h>
int offset[] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int len(int n) { int ans = 0; while (n != 0) { ans++; n /= 10; } return ans;}
int all(int bits) { int ans = 9; int cur = 9; while (--bits != 0) { ans *= cur--; } return ans;}
int small(int bits, int candidates) { int ans = 1; for (int i = 0; i < bits; i++, candidates--) { ans *= candidates; } return ans;}
int process(int num, int len, int rest, int status) { if (rest == 0) { return 1; } int cur = (num / offset[rest]) % 10; int cnt = 0; for (int i = 0; i < cur; i++) { if ((status & (1 << i)) == 0) { cnt++; } } int ans = cnt * small(rest - 1, 9 - (len - rest)); if ((status & (1 << cur)) == 0) { ans += process(num, len, rest - 1, status | (1 << cur)); } return ans;}
int countSpecialNumbers(int n) { int len0 = len(n); int ans = 0; for (int i = 1; i < len0; i++) { ans += all(i); } int firstNumber = n / offset[len0]; ans += (firstNumber - 1) * small(len0 - 1, 9); ans += process(n, len0, len0 - 1, 1 << firstNumber); return ans;}
int main() { int n = 135; int ans = countSpecialNumbers(n); printf("The number of special numbers between 1 and %d is %d\n", n, ans); return 0;}
复制代码
c++完整代码如下：
#include <iostream>using namespace std;
int offset[11] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int len(int n) { int ans = 0; while (n != 0) { ans++; n /= 10; } return ans;}
int all(int bits) { int ans = 9; int cur = 9; while (--bits != 0) { ans *= cur--; } return ans;}
int small(int bits, int candidates) { int ans = 1; for (int i = 0; i < bits; i++, candidates--) { ans *= candidates; } return ans;}
int process(int num, int len, int rest, int status) { if (rest == 0) { return 1; } int cur = (num / offset[rest]) % 10; int cnt = 0; for (int i = 0; i < cur; i++) { if ((status & (1 << i)) == 0) { cnt++; } } int ans = cnt * small(rest - 1, 9 - (len - rest)); if ((status & (1 << cur)) == 0) { ans += process(num, len, rest - 1, status | (1 << cur)); } return ans;}
int countSpecialNumbers(int n) { int len0 = len(n); int ans = 0; for (int i = 1; i < len0; i++) { ans += all(i); } int firstNumber = n / offset[len0]; ans += (firstNumber - 1) * small(len0 - 1, 9); ans += process(n, len0, len0 - 1, 1 << firstNumber); return ans;}
int main() { int n = 135; int ans = countSpecialNumbers(n); cout << "The number of special numbers between 1 and " << n << " is " << ans << endl; return 0;}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【福大大架构师每日一题】的原创文章。
原文链接:【http://xie.infoq.cn/article/0e37db2b7af5ae10690428f0a】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
福大大架构师每日一题
关注
公众号：福大大架构师每日一题 2021-02-15 加入
公众号：福大大架构师每日一题
![2023-05-02：如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。 给你一个正整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。 输入：n = 20。 输出：19。_Go_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论