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.计算每个长度的非重复数字的个数。通过一个辅助函数numAllLength计算不同位数下，每个位都是唯一的数字的个数，并将其累加到变量noRepeat上。

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位取反异或，并调用辅助函数numberRest计算剩余位和可用状态下的数字个数，将结果累加到变量ans上。

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

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

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完整代码如下：

package mainimport (    "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 lengthfunc 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 uniquefunc 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 digitsfunc 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 representationfunc 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++完整代码如下：

#include <iostream>#include <cmath>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完整代码如下：

#include <stdio.h>#include <stdbool.h>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;}

在这里插入图片描述

福大大架构师每日一题java当死，golang当立。最新面试题，涉及golang，rust，mysql，redis，云原生，算法，分布式，网络，操作系统。

公众号