2023-07-11：给定正整数 n，返回在 [1, n] 范围内具有至少 1|算法|偏移量|复杂度|二进制|offset

2023-07-11：给定正整数 n，返回在 [1, n] 范围内具有至少 1

2023-07-11 19:07:17　来源: moonfdd

北京举报

分享至

2023-07-11：给定正整数 n，返回在 [1, n] 范围内具有至少 1 位重复数字的正整数的个数。输入：n = 100。输出：10。

答案2023-07-11：

函数的主要思路如下：

1.若n小于等于10，则直接返回0，因为在[1, 10]范围内不存在重复数字的情况。

2.计算n的位数和偏移量。首先计算n的位数和一个偏移量offset，其中偏移量初始值为1，算法通过迭代计算tmp = n / 10的商，直到商为0为止，每次迭代位数加1，偏移量乘以10。

3.计算每个长度的非重复数字的个数。通过一个辅助函数计算不同位数下，每个位都是唯一的数字的个数，并将其累加到变量noRepeat上。

numAllLength

4.计算长度为len的非重复数字的个数。当长度小于等于10时，通过包含位运算的算法进行计算，具体步骤如下：

4.1.初始化一个十进制数status为2^10-1，二进制表示为0b1111111111，用于标记当前数字的可用状态，初始状态为每位都可用。（1表示不可用，0表示可用）

4.2.根据n的位数和偏移量计算出n除以offset的商，即当前数字的最高位first。

4.3.将分三种情况：

4.3.1.若first大于0，则对于0到first-1的数字cur，如果status的第cur位为1，说明该数字可用，将offset/10和status的第cur位取反异或，并调用辅助函数计算剩余位和可用状态下的数字个数，将结果累加到变量ans上。

numberRest

4.3.2.若first等于0，则直接跳过该步骤。

4.3.3.若first在0到9之间，则如果status的第first位为1，说明该数字可用，将offset/10和status的第first位取反异或，并调用递归函数计算剩余位和可用状态下的数字个数，将结果累加到变量ans上。

process

5.最后的结果为n加1减去noRepeat，即在[1, n]范围内至少有1位重复数字的正整数的个数。

该代码在给定正整数n的范围内采用了一种比较高效的算法，通过一系列的位运算和迭代计算，找出了每个位数下非重复数字的个数，然后根据n的位数和偏移量来计算在该位数下包含至少1位重复数字的正整数的个数，并将它们相加得出最终结果。

该代码的时间复杂度为O(log10(n) * 2 ^ 10)，其中n是输入的正整数。主要消耗时间的是计算每个位数下非重复数字的个数，该计算的时间复杂度为O(log10(n))，而计算每个长度为len的非重复数字的个数的时间复杂度为O(2 ^ len)。因为长度为len的数字有2 ^ len个，所以计算每个长度为len的非重复数字的个数的时间复杂度为O(2 ^ len)。

该代码的空间复杂度为O(1)，因为它只使用了常量级的额外空间来保存一些临时变量，不随输入规模的增长而增加。

go完整代码如下：

packagemain
import(
"fmt"
)
funcnumDupDigitsAtMostN(nint)int{
ifn<=10{
return0
}
//Calculatethelengthofnandtheoffset
len,offset:=1,1
tmp:=n/10
fortmp>0{
len++
offset*=10
tmp/=10
}
//Calculatethecountofnon-repeatingnumbersofeachlength
noRepeat:=0
fori:=1;inoRepeat+=numAllLength(i)
}
//Calculatethecountofnon-repeatingnumbersforlengthlen
iflen<=10{
status:=0b1111111111
noRepeat+=((n/offset)-1)*numberRest(offset/10,status^1)
noRepeat+=process(offset/10,status^(1<<(n/offset)),n)
}
returnn+1-noRepeat
}
//Returnsthecountofnumberswhereeachdigitisuniqueforagivenlength
funcnumAllLength(lenint)int{
iflen>10{
return0
}
iflen==1{
return10
}
ans,cur:=9,9
forlen--;len>0;len--{
ans*=cur
cur--
}
returnans
}
//Returnsthecountofnumberswheretheremainingdigitsareunique
funcprocess(offset,status,nint)int{
ifoffset==0{
return1
}
ans:=0
first:=(n/offset)%10
forcur:=0;curif(status&(1<ans+=numberRest(offset/10,status^(1<}
}
if(status&(1<ans+=process(offset/10,status^(1<}
returnans
}
//Returnsthecountofnumberswithremaininglengthandavailabledigits
funcnumberRest(offset,statusint)int{
c:=hammingWeight(status)
ans:=1
foroffset>0{
ans*=c
c--
offset/=10
}
returnans
}
//Returnsthenumberofsetbits(1s)inabinaryrepresentation
funchammingWeight(nint)int{
n=(n&0x55555555)+((n>>1)&0x55555555)
n=(n&0x33333333)+((n>>2)&0x33333333)
n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f)
n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff)
n=(n&0x0000ffff)+((n>>16)&0x0000ffff)
returnn
}
funcmain(){
n:=1000
result:=numDupDigitsAtMostN(n)
fmt.Println(result)
}

rust完整代码如下：

pubfnnum_dup_digits_at_most_n(n:i32)->i32{
ifn<=10{
return0;
}
letlen=get_length(n);
letmutoffset=1;
letmuttmp=n/10;
whiletmp>0{
offset*=10;
tmp/=10;
}
letmutno_repeat=0;
foriin1..len{
no_repeat+=num_all_length(i);
}
iflen<=10{
letstatus=0b1111111111;
no_repeat+=((n/offset)-1)*number_rest(offset/10,status^1);
no_repeat+=process(offset/10,status^(1<<(n/offset)),n);
}
n+1-no_repeat
}
fnget_length(n:i32)->i32{
letmutlen=1;
letmuttmp=n/10;
whiletmp>0{
len+=1;
tmp/=10;
}
len
}
fnnum_all_length(len:i32)->i32{
iflen>10{
return0;
}
iflen==1{
return10;
}
letmutans=9;
letmutcur=9;
letmutlen=len-1;
whilelen>0{
ans*=cur;
cur-=1;
len-=1;
}
ans
}
fnprocess(offset:i32,status:i32,n:i32)->i32{
ifoffset==0{
return1;
}
letmutans=0;
letfirst=(n/offset)%10;
forcurin0..first{
if(status&(1<ans+=number_rest(offset/10,status^(1<}
}
if(status&(1<ans+=process(offset/10,status^(1<}
ans
}
fnnumber_rest(offset:i32,status:i32)->i32{
letmutc=hamming_weight(status);
letmutans=1;
letmutoffset=offset;
whileoffset>0{
ans*=c;
c-=1;
offset/=10;
}
ans
}
fnhamming_weight(mutn:i32)->i32{
n=(n&0x55555555)+((n>>1)&0x55555555);
n=(n&0x33333333)+((n>>2)&0x33333333);
n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff);
n=(n&0x0000ffff)+((n>>16)&0x0000ffff);
n
}
fnmain(){
letn=1000;
letresult=num_dup_digits_at_most_n(n);
println!("Result:{}",result);
}

c++完整代码如下：

#include
#include
intnumAllLength(intlen);
intprocess(intoffset,intstatus,intn);
intnumberRest(intoffset,intstatus);
inthammingWeight(intn);
intnumDupDigitsAtMostN(intn){
if(n<=10){
return0;
}
intlen=1;
intoffset=1;
inttmp=n/10;
while(tmp>0){
len++;
offset*=10;
tmp/=10;
}
intnoRepeat=0;
for(inti=1;inoRepeat+=numAllLength(i);
}
if(len<=10){
intstatus=0b1111111111;
noRepeat+=((n/offset)-1)*numberRest(offset/10,status^1);
noRepeat+=process(offset/10,status^(1<<(n/offset)),n);
}
returnn+1-noRepeat;
}
intnumAllLength(intlen){
if(len>10){
return0;
}
if(len==1){
return10;
}
intans=9;
intcur=9;
while(--len>0){
ans*=cur;
cur--;
}
returnans;
}
intprocess(intoffset,intstatus,intn){
if(offset==0){
return1;
}
intans=0;
intfirst=(n/offset)%10;
for(intcur=0;curif((status&(1<ans+=numberRest(offset/10,status^(1<}
}
if((status&(1<ans+=process(offset/10,status^(1<}
returnans;
}
intnumberRest(intoffset,intstatus){
intc=hammingWeight(status);
intans=1;
while(offset>0){
ans*=c;
c--;
offset/=10;
}
returnans;
}
inthammingWeight(intn){
n=(n&0x55555555)+((n>>1)&0x55555555);
n=(n&0x33333333)+((n>>2)&0x33333333);
n=(n&0x0f0f0f0f)+((n>>4)&0x0f0f0f0f);
n=(n&0x00ff00ff)+((n>>8)&0x00ff00ff);
n=(n&0x0000ffff)+((n>>16)&0x0000ffff);
returnn;
}
intmain(){
intn=1000;
intresult=numDupDigitsAtMostN(n);
std::cout<<"Result:"<return0;
}

c完整代码如下：

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.