2023-07-11：給定正整數(shù) n， 返回在 [1, n] 范圍內(nèi)具有 至少 1 位 重復(fù)數(shù)字的正整數(shù)的
2023-07-11：給定正整數(shù) n， 返回在 [1, n] 范圍內(nèi)具有 至少 1 位 重復(fù)數(shù)字的正整數(shù)的個數(shù)。 輸入：n = 100。 輸出：10。
答案2023-07-11：
函數(shù)的主要思路如下：
1.若n小于等于10，則直接返回0，因?yàn)樵赱1, 10]范圍內(nèi)不存在重復(fù)數(shù)字的情況。
2.計(jì)算n的位數(shù)和偏移量。首先計(jì)算n的位數(shù)和一個偏移量offset，其中偏移量初始值為1，算法通過迭代計(jì)算tmp = n / 10的商，直到商為0為止，每次迭代位數(shù)加1，偏移量乘以10。
3.計(jì)算每個長度的非重復(fù)數(shù)字的個數(shù)。通過一個輔助函數(shù)numAllLength計(jì)算不同位數(shù)下，每個位都是唯一的數(shù)字的個數(shù)，并將其累加到變量noRepeat上。
4.計(jì)算長度為len的非重復(fù)數(shù)字的個數(shù)。當(dāng)長度小于等于10時，通過包含位運(yùn)算的算法進(jìn)行計(jì)算，具體步驟如下：
4.1.初始化一個十進(jìn)制數(shù)status為2^10-1，二進(jìn)制表示為0b1111111111，用于標(biāo)記當(dāng)前數(shù)字的可用狀態(tài)，初始狀態(tài)為每位都可用。（1表示不可用，0表示可用）
4.2.根據(jù)n的位數(shù)和偏移量計(jì)算出n除以offset的商，即當(dāng)前數(shù)字的最高位first。
4.3.將分三種情況：
4.3.1.若first大于0，則對于0到first-1的數(shù)字cur，如果status的第cur位為1，說明該數(shù)字可用，將offset/10和status的第cur位取反異或，并調(diào)用輔助函數(shù)numberRest計(jì)算剩余位和可用狀態(tài)下的數(shù)字個數(shù)，將結(jié)果累加到變量ans上。
4.3.2.若first等于0，則直接跳過該步驟。
4.3.3.若first在0到9之間，則如果status的第first位為1，說明該數(shù)字可用，將offset/10和status的第first位取反異或，并調(diào)用遞歸函數(shù)process計(jì)算剩余位和可用狀態(tài)下的數(shù)字個數(shù)，將結(jié)果累加到變量ans上。
5.最后的結(jié)果為n加1減去noRepeat，即在[1, n]范圍內(nèi)至少有1位重復(fù)數(shù)字的正整數(shù)的個數(shù)。
該代碼在給定正整數(shù)n的范圍內(nèi)采用了一種比較高效的算法，通過一系列的位運(yùn)算和迭代計(jì)算，找出了每個位數(shù)下非重復(fù)數(shù)字的個數(shù)，然后根據(jù)n的位數(shù)和偏移量來計(jì)算在該位數(shù)下包含至少1位重復(fù)數(shù)字的正整數(shù)的個數(shù)，并將它們相加得出最終結(jié)果。
該代碼的時間復(fù)雜度為O(log10(n) * 2 ^ 10)，其中n是輸入的正整數(shù)。主要消耗時間的是計(jì)算每個位數(shù)下非重復(fù)數(shù)字的個數(shù)，該計(jì)算的時間復(fù)雜度為O(log10(n))，而計(jì)算每個長度為len的非重復(fù)數(shù)字的個數(shù)的時間復(fù)雜度為O(2 ^ len)。因?yàn)殚L度為len的數(shù)字有2 ^ len個，所以計(jì)算每個長度為len的非重復(fù)數(shù)字的個數(shù)的時間復(fù)雜度為O(2 ^ len)。
該代碼的空間復(fù)雜度為O(1)，因?yàn)樗皇褂昧顺Ａ考壍念~外空間來保存一些臨時變量，不隨輸入規(guī)模的增長而增加。
go完整代碼如下：
package?main
import?(
????"fmt"
)
func?numDupDigitsAtMostN(n?int)?int?{
????if?n?<=?10?{
????????return?0
????}
????//?Calculate?the?length?of?n?and?the?offset
????len,?offset?:=?1,?1
????tmp?:=?n?/?10
????for?tmp?>?0?{
????????len++
????????offset?*=?10
????????tmp?/=?10
????}
????//?Calculate?the?count?of?non-repeating?numbers?of?each?length
????noRepeat?:=?0
????for?i?:=?1;?i?<?len;?i++?{
????????noRepeat?+=?numAllLength(i)
????}
????//?Calculate?the?count?of?non-repeating?numbers?for?length?len
????if?len?<=?10?{
????????status?:=?0b1111111111
????????noRepeat?+=?((n?/?offset)?-?1)?*?numberRest(offset/10,?status^1)
????????noRepeat?+=?process(offset/10,?status^(1<<(n/offset)),?n)
????}
????return?n?+?1?-?noRepeat
}
//?Returns?the?count?of?numbers?where?each?digit?is?unique?for?a?given?length
func?numAllLength(len?int)?int?{
????if?len?>?10?{
????????return?0
????}
????if?len?==?1?{
????????return?10
????}
????ans,?cur?:=?9,?9
????for?len--;?len?>?0;?len--?{
????????ans?*=?cur
????????cur--
????}
????return?ans
}
//?Returns?the?count?of?numbers?where?the?remaining?digits?are?unique
func?process(offset,?status,?n?int)?int?{
????if?offset?==?0?{
????????return?1
????}
????ans?:=?0
????first?:=?(n?/?offset)?%?10
????for?cur?:=?0;?cur?<?first;?cur++?{
????????if?(status?&?(1?<<?cur))?!=?0?{
????????????ans?+=?numberRest(offset/10,?status^(1<<cur))
????????}
????}
????if?(status?&?(1?<<?first))?!=?0?{
????????ans?+=?process(offset/10,?status^(1<<first),?n)
????}
????return?ans
}
//?Returns?the?count?of?numbers?with?remaining?length?and?available?digits
func?numberRest(offset,?status?int)?int?{
????c?:=?hammingWeight(status)
????ans?:=?1
????for?offset?>?0?{
????????ans?*=?c
????????c--
????????offset?/=?10
????}
????return?ans
}
//?Returns?the?number?of?set?bits?(1s)?in?a?binary?representation
func?hammingWeight(n?int)?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)
????return?n
}
func?main()?{
????n?:=?1000
????result?:=?numDupDigitsAtMostN(n)
????fmt.Println(result)
}
rust完整代碼如下：
pub?fn?num_dup_digits_at_most_n(n:?i32)?->?i32?{
????if?n?<=?10?{
????????return?0;
????}
????let?len?=?get_length(n);
????let?mut?offset?=?1;
????let?mut?tmp?=?n?/?10;
????while?tmp?>?0?{
????????offset?*=?10;
????????tmp?/=?10;
????}
????let?mut?no_repeat?=?0;
????for?i?in?1..len?{
????????no_repeat?+=?num_all_length(i);
????}
????if?len?<=?10?{
????????let?status?=?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
}
fn?get_length(n:?i32)?->?i32?{
????let?mut?len?=?1;
????let?mut?tmp?=?n?/?10;
????while?tmp?>?0?{
????????len?+=?1;
????????tmp?/=?10;
????}
????len
}
fn?num_all_length(len:?i32)?->?i32?{
????if?len?>?10?{
????????return?0;
????}
????if?len?==?1?{
????????return?10;
????}
????let?mut?ans?=?9;
????let?mut?cur?=?9;
????let?mut?len?=?len?-?1;
????while?len?>?0?{
????????ans?*=?cur;
????????cur?-=?1;
????????len?-=?1;
????}
????ans
}
fn?process(offset:?i32,?status:?i32,?n:?i32)?->?i32?{
????if?offset?==?0?{
????????return?1;
????}
????let?mut?ans?=?0;
????let?first?=?(n?/?offset)?%?10;
????for?cur?in?0..first?{
????????if?(status?&?(1?<<?cur))?!=?0?{
????????????ans?+=?number_rest(offset?/?10,?status?^?(1?<<?cur));
????????}
????}
????if?(status?&?(1?<<?first))?!=?0?{
????????ans?+=?process(offset?/?10,?status?^?(1?<<?first),?n);
????}
????ans
}
fn?number_rest(offset:?i32,?status:?i32)?->?i32?{
????let?mut?c?=?hamming_weight(status);
????let?mut?ans?=?1;
????let?mut?offset?=?offset;
????while?offset?>?0?{
????????ans?*=?c;
????????c?-=?1;
????????offset?/=?10;
????}
????ans
}
fn?hamming_weight(mut?n:?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
}
fn?main()?{
????let?n?=?1000;
????let?result?=?num_dup_digits_at_most_n(n);
????println!("Result:?{}",?result);
}
c++完整代碼如下：
int?numAllLength(int?len);
int?process(int?offset,?int?status,?int?n);
int?numberRest(int?offset,?int?status);
int?hammingWeight(int?n);
int?numDupDigitsAtMostN(int?n)?{
????if?(n?<=?10)?{
????????return?0;
????}
????int?len?=?1;
????int?offset?=?1;
????int?tmp?=?n?/?10;
????while?(tmp?>?0)?{
????????len++;
????????offset?*=?10;
????????tmp?/=?10;
????}
????int?noRepeat?=?0;
????for?(int?i?=?1;?i?<?len;?i++)?{
????????noRepeat?+=?numAllLength(i);
????}
????if?(len?<=?10)?{
????????int?status?=?0b1111111111;
????????noRepeat?+=?((n?/?offset)?-?1)?*?numberRest(offset?/?10,?status?^?1);
????????noRepeat?+=?process(offset?/?10,?status?^?(1?<<?(n?/?offset)),?n);
????}
????return?n?+?1?-?noRepeat;
}
int?numAllLength(int?len)?{
????if?(len?>?10)?{
????????return?0;
????}
????if?(len?==?1)?{
????????return?10;
????}
????int?ans?=?9;
????int?cur?=?9;
????while?(--len?>?0)?{
????????ans?*=?cur;
????????cur--;
????}
????return?ans;
}
int?process(int?offset,?int?status,?int?n)?{
????if?(offset?==?0)?{
????????return?1;
????}
????int?ans?=?0;
????int?first?=?(n?/?offset)?%?10;
????for?(int?cur?=?0;?cur?<?first;?cur++)?{
????????if?((status?&?(1?<<?cur))?!=?0)?{
????????????ans?+=?numberRest(offset?/?10,?status?^?(1?<<?cur));
????????}
????}
????if?((status?&?(1?<<?first))?!=?0)?{
????????ans?+=?process(offset?/?10,?status?^?(1?<<?first),?n);
????}
????return?ans;
}
int?numberRest(int?offset,?int?status)?{
????int?c?=?hammingWeight(status);
????int?ans?=?1;
????while?(offset?>?0)?{
????????ans?*=?c;
????????c--;
????????offset?/=?10;
????}
????return?ans;
}
int?hammingWeight(int?n)?{
????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);
????return?n;
}
int?main()?{
????int?n?=?1000;
????int?result?=?numDupDigitsAtMostN(n);
????std::cout?<<?"Result:?"?<<?result?<<?std::endl;
????return?0;
}
c完整代碼如下：
int?numAllLength(int?len);
int?process(int?offset,?int?status,?int?n);
int?numberRest(int?offset,?int?status);
int?hammingWeight(int?n);
int?numDupDigitsAtMostN(int?n)?{
????if?(n?<=?10)?{
????????return?0;
????}
????int?len?=?1;
????int?offset?=?1;
????int?tmp?=?n?/?10;
????while?(tmp?>?0)?{
????????len++;
????????offset?*=?10;
????????tmp?/=?10;
????}
????int?noRepeat?=?0;
????for?(int?i?=?1;?i?<?len;?i++)?{
????????noRepeat?+=?numAllLength(i);
????}
????if?(len?<=?10)?{
????????int?status?=?0b1111111111;
????????noRepeat?+=?((n?/?offset)?-?1)?*?numberRest(offset?/?10,?status?^?1);
????????noRepeat?+=?process(offset?/?10,?status?^?(1?<<?(n?/?offset)),?n);
????}
????return?n?+?1?-?noRepeat;
}
int?numAllLength(int?len)?{
????if?(len?>?10)?{
????????return?0;
????}
????if?(len?==?1)?{
????????return?10;
????}
????int?ans?=?9;
????int?cur?=?9;
????while?(--len?>?0)?{
????????ans?*=?cur;
????????cur--;
????}
????return?ans;
}
int?process(int?offset,?int?status,?int?n)?{
????if?(offset?==?0)?{
????????return?1;
????}
????int?ans?=?0;
????int?first?=?(n?/?offset)?%?10;
????for?(int?cur?=?0;?cur?<?first;?cur++)?{
????????if?((status?&?(1?<<?cur))?!=?0)?{
????????????ans?+=?numberRest(offset?/?10,?status?^?(1?<<?cur));
????????}
????}
????if?((status?&?(1?<<?first))?!=?0)?{
????????ans?+=?process(offset?/?10,?status?^?(1?<<?first),?n);
????}
????return?ans;
}
int?numberRest(int?offset,?int?status)?{
????int?c?=?hammingWeight(status);
????int?ans?=?1;
????while?(offset?>?0)?{
????????ans?*=?c;
????????c--;
????????offset?/=?10;
????}
????return?ans;
}
int?hammingWeight(int?n)?{
????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);
????return?n;
}
int?main()?{
????int?n?=?1000;
????int?result?=?numDupDigitsAtMostN(n);
????printf("Result:?%d\n",?result);
????return?0;
}
