2023-05-02：如果一個(gè)正整數(shù)每一個(gè)數(shù)位都是 互不相同 的，我們稱它是 特殊整數(shù) 。 給
2023-05-02：如果一個(gè)正整數(shù)每一個(gè)數(shù)位都是 互不相同 的，我們稱它是 特殊整數(shù) 。
給你一個(gè)正整數(shù) n ，請(qǐng)你返回區(qū)間 [1, n] 之間特殊整數(shù)的數(shù)目。
輸入：n = 20。
輸出：19。
答案2023-05-02：
可以通過(guò)數(shù)字組合和狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃算法來(lái)解決。具體過(guò)程如下：
1.對(duì)于給定的正整數(shù) n，求出其位數(shù) len。
2.枚舉所有小于 len 位的數(shù)字，計(jì)算其中特殊整數(shù)的總數(shù)。如果數(shù)字為 i 位，則特殊整數(shù)個(gè)數(shù)為 9 * 8 * ... * (10 - i)。
3.對(duì)于第 len 位上的數(shù)字 x，在計(jì)算期間將其提取出來(lái)。
4.如果 x 是第一個(gè)數(shù)字，則區(qū)間 [1, n] 中，第 len 位之前的數(shù)字不受限制，因此可以選取任意一個(gè)非零數(shù)字，共有 9 種可能。
5.對(duì)于區(qū)間 [1, n] 中第 len 位之前的每個(gè)數(shù)字，考慮它們與 x 組合所能得到的所有特殊整數(shù)。如果某個(gè)數(shù)字已經(jīng)在當(dāng)前組合中出現(xiàn)過(guò)，則不能再重復(fù)使用。
6.遞歸求解所有滿足要求的數(shù)字組合，每次處理一位，直到組合中所有數(shù)字都確定下來(lái)。
7.對(duì)于區(qū)間 [1, n] 中的每個(gè)數(shù)字，檢查其是否為特殊整數(shù)，并統(tǒng)計(jì)個(gè)數(shù)。
8.返回特殊整數(shù)的總數(shù)。
該算法的時(shí)間復(fù)雜度為 O(n log n)，空間復(fù)雜度為 O(log n)。由于需要進(jìn)行大量的數(shù)字組合枚舉和狀態(tài)壓縮操作，實(shí)現(xiàn)起來(lái)較為復(fù)雜。
rust完整代碼如下：
const?OFFSET:?[i32;?11]?=?[
????0,?????//?0位數(shù)，一共能解決幾個(gè)位
????1,?????//?1位數(shù)，一共能解決幾個(gè)位
????10,????//?2位數(shù)，一共能解決幾個(gè)位
????100,???//?3位數(shù)，一共能解決幾個(gè)位
????1000,??//?4位數(shù)，一共能解決幾個(gè)位
????10000,?//?5位數(shù)，一共能解決幾個(gè)位
????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這個(gè)數(shù)字有幾位
fn?len(mut?n:?i32)?->?i32?{
????let?mut?ans?=?0;
????while?n?!=?0?{
????????ans?+=?1;
????????n?/=?10;
????}
????return?ans;
}
//?返回所有bits位數(shù)，有幾個(gè)特殊的
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?:?原始數(shù)?46531?固定
//?len?:?原始數(shù)有幾位，5位，固定
//?rest?:?還剩幾位沒(méi)決定，可變參數(shù)
//?num?:?46531
//???????4?_?_?_?_
//???????4?0~5
//???????4?6?_?_?_
//?status?:?4?6?_?_?_
//?哪些數(shù)字使用了，狀態(tài)！在status里：
//?體系學(xué)習(xí)班，狀態(tài)壓縮的動(dòng)態(tài)規(guī)劃！
//?int?status?32位
//?9?8?7?6?5?4?3?2?1?0
//???????1?0?1?0?0?0?0
//?4?6?_?_?_?還有幾個(gè)達(dá)標(biāo)的！
//?哪些數(shù)字選了都在status里，用一個(gè)status變量表示數(shù)字選沒(méi)選(位信息)
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完整代碼如下：
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++完整代碼如下：
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;
}
