题目大意: 给一个数N,统计从1到N的所有数字中1出现的次数。
解题思路: 这道题是《编程之美》上面的一道题(第2.4节),需要通过分析来总结规律,然后总结出公式,如果暴力去“数”1的个数,显然会超时。但如果通过公式来算的话,时间复杂度就直接降到O(1)。具体分析过程比较复杂,详情参见《编程之美》2.4节“1的数目”,这里只给出结论——从右往左拆解数,逐位分析每个位出现1的数目,然后统计其规律与左右数存在的关系,最后累加,即为结果。
1 |
|
题目大意: 给一个数N,统计从1到N的所有数字中1出现的次数。
解题思路: 这道题是《编程之美》上面的一道题(第2.4节),需要通过分析来总结规律,然后总结出公式,如果暴力去“数”1的个数,显然会超时。但如果通过公式来算的话,时间复杂度就直接降到O(1)。具体分析过程比较复杂,详情参见《编程之美》2.4节“1的数目”,这里只给出结论——从右往左拆解数,逐位分析每个位出现1的数目,然后统计其规律与左右数存在的关系,最后累加,即为结果。
1 |
|