代码说明:
magic 函数:
该函数接受一个整数 n 作为输入。
如果 n 是一位数,直接返回 n。
否则,将 n 转换为字符串 numStr,然后遍历字符串,计算相邻字符的差的绝对值,并将结果存储在 resultStr 中。
最后将 resultStr 转换为整数并返回。
magicFingerprint 函数:
该函数接受一个整数 n 作为输入。
使用 while 循环,不断调用 magic 函数,直到 n 变为一位数。
返回最终的一位数,即 n 的 magic 指纹。
main 函数:
读取输入的 A 和 B。
使用 for 循环遍历 [A, B] 区间内的所有数。
对于每个数,调用 magicFingerprint 函数计算其 magic 指纹。
如果 magic 指纹为 7,则将幸运数计数 luckyCount 加 1。
最后输出幸运数的数量。
复杂度分析:
时间复杂度:对于每个数,计算 magic 指纹的时间复杂度为 O(log^10n),因为每次调用 magic 函数,数字的位数至少减少 1。遍历 [A, B] 区间内的所有数,总的时间复杂度为O((B−A+1)log^10 B)。
空间复杂度:主要是存储中间结果的字符串,空间复杂度为 O(log10n)。
不能白嫖
觉得好的花点个赞,谢谢