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 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 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;}
复制代码
![2023-07-11：给定正整数 n， 返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 输入：n = 100。 输出：10。_Go_福大大架构师每日一题_InfoQ写作社区](https://static001.infoq.cn/static/infoq/img/logo-121-75.yuij86g.png){kind=logo}
评论