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上。
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上。
4.3.2.若first等于0,则直接跳过该步骤。
4.3.3.若first在0到9之间,则如果status的第first位为1,说明该数字可用,将offset/10和status的第first位取反异或,并调用递归函数计算剩余位和可用状态下的数字个数,将结果累加到变量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完整代码如下:
在这里插入图片描述rust完整代码如下:
在这里插入图片描述c++完整代码如下:
在这里插入图片描述c完整代码如下:
在这里插入图片描述
领取专属 10元无门槛券
私享最新 技术干货