我们将特殊数字定义为仅包含 4 和 7 的数字。
让我们看例子:447
, 477
, 444
和 777
是特殊数字 而 407
不是。
我需要帮助来理解生成Nth
特殊号码的法律/规则 是什么。
我试过下面的代码,但没有用
int x[2000];
int k=0;
void dfs( int a ) {
if(k==1021)
return;
x[k++]=a;
dfs(a*10+4);
dfs(a*10+7);
}
dfs(4);
dfs(7);
关于如何做的任何解决方案或想法?
最佳答案
为此我们可以使用二进制。将 4 称为 0,将 7 称为 1,因为 7>4。假设我们正在寻找第 n 个特殊号码。定义 k 为比第 n 个特殊数字位数少的特殊数字的个数。现在,我们看看如何使用二进制文件。假设我们知道第 10 个特殊数字有 3 个数字,并且 k=6。我们正在寻找3位特殊号码列表中的第10-6=4个号码。
4
- 0
77
- 11
7
- 1
444
- 000
44
- 00
447
- 001
47
- 01
474
- 010
74
- 10
477
- 011
<-这里
如图所示将它们映射到二进制文件,问题变得更容易了。 m 位特殊数字的个数为 2^m,请记住,2 的前 m 次幂之和为 2^(m+1)-1。如果我们有一个 3 位数字,那么我们通过将 1 位数字和 2 位数字相加来找到 k,剩下 2^0+2^1+2^2=2^3-1。排除 0 位数字,我们有 2^3-2 作为 k,这概括为 2^digits-2。为了找到位数,我们需要找出 n 以下有多少次 2 的幂。这只是 log2(n),但我们必须将它排成一行并得到一个整数,所以我们取 floor(log2(n+1))。从这里开始,我们简单地使用 n-k-1 的二进制表示,然后使用按位函数提取每个数字并将该数字添加到我们的答案中。
int nthspecialnum( int n )
{
int digits = (int)(log2(n+1));
int k = pow( 2, digits ) - 2;
int binary = n - k - 1;
int answer = 0;
for( int i = 0; i < digits; i++ ) {
bool is7 = ((binary >> i) % 2) == 1;
answer += (is7 ? 7 : 4)*pow( 10, i );
}
return answer;
}
这些数字会很快变大,所以如果您正在寻找较大的 n
并且不希望出现负数,您可以简单地将数字保存在数组中而不是整数中并按顺序打印出来。
关于algorithm - 如何生成仅包含 2 种数字的第 n 个数字?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32679935/