← 返回目录

算法笔试模拟题精解之“神奇数字在哪里”

第 47 / 74 卷日期：

算法笔试模拟题精解之“神奇数字在哪里”

贡献者 | 洪浩原

简介：注意读题，本题要求的数字中“只”含有 1，2，3 三个数字。

题目描述

等级：中等

知识点：搜索、递归

查看题目：神奇数字在哪里

请计算出 1-n(1<=n<=1000000000) 中有多少个数字中，只存在 '1','2','3' 这三

个数字，且这三个数字至少都要出现 1 次。

输入一个数 n。

输出 1-n 中符合要求的数字的个数。

示例 1

输入：

232

输出：

4

解题方法：

注意读题，本题要求的数字中“只”含有 1，2，3 三个数字

方法 1：暴力搜索

对本题，最简单的想法是针对每个数字，转为字符串，然后判断数字中是

否只同时包含 1，2，3 三个字符。鉴于本题输入是 int，n 最大可以达到 2^31-

1 ≈ 2*10^9，一个这么长的 for 循环，时间复杂度还是比较高的，不是最优解法。

时间复杂度：O(n)

方法 2：深度优先搜索

寻找这种神奇数字，暴力法可以说是从数字中“尝试”某个数字，是否符合我

们的标准，这个过程好比线性搜索。但换个思路想，我们也可以尝试用“构建”的方

式，构建出所有符合“神奇数字”标准的数字，并挨个计数，完成这个过程。

这个构建数字和搜索的过程，可以写一个递归做深度搜索实现：从 0 开始，给一

个较短的数字，不断让把的其它位数字移动 1 位，并把多出来的个位数设为 1，2，

3，并在搜索的范围超过 n 时，及时停下搜索。

时间复杂度：O(logn)（或者 O(k)，k 表示数字的位数）

方法 3：预热 + 查找

用过方法二后，我们发现，在限定了 n 是 int 类型的情况下，其实这种只含有 1，

2，3 的数字的数量并不多。甚至可以在静态初始化方法里，提前计算好所有这样的

数字，并按大小排列好。然后对输入的每个 n，直接在准备好的数组中二分查找，找

到比它小的数字的数量，就可以返回结果了。

看完之后是不是有了答题思路了呢，快来练练手吧：神奇数字在哪里

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”