讲的明白，但写的明白吗？

Alliot 发布于2019-07-24 18:08 / 1303人阅读

摘要：好多内容自己会但不一定讲的明白，讲的明白也不一定写的明白思路对于任意的一个页码数，将其分为两部分个位数部分数字和其他部分数字。

算法作业有一个小的题目：

一本书的页码从自然数1开始编码直到自然数n，按照通常的习惯，每个页码都不包含多余的前导数字0，例如第6页用数字6而不是06或者006表示。现在给定表示书的总页码的十进制整数n(1 =< n <= 10^9)，编程计算书的全部页码中分别用到多少次数字0, 1, 2, 3, 4, 5, 6, 7, 8, 9。

比如一本数有123页，那么各数字出现次数如下图：

解题思路不是很难想到，但是在写作业报告，发现很难清楚地把这个算法过程给写出来。于是就认真组织了语言，配上几幅图片，希望能把算法讲明白。（好多内容自己会但不一定讲的明白，讲的明白也不一定写的明白）

思路

对于任意的一个页码数，将其分为两部分：个位数部分数字和其他部分数字。那么对于总页码为N的书本，其所有的页码可以放在如下的一个表格中，绿色表格代表页码，里面的任意数字Xi = i * 10 + j(方便我们理解，这里假设N-3==0)：

现在要做的就是统计所有绿色表格中数字0到9出现的次数，绿色表格（也即任意一个页码）中数字组成其实可以拆分为对应的行和列的数字组成。例如对于页码123，其中1、2、3各出现1次，它对应的行的是123/10=12，列为123%10=3，12和3中1、2、3也是各出现一次。

要计算所有的页码中0到9出现的总次数，可以转换为所有行中0到9出现的次数和所有列中0到9出现的次数。对于每一个绿色表格，其对应的行和列中数字各出现一次。因此我们可以先统计每一行和每一列绿色方格的数目，然后就可以得出每一行和每一列中0数字出现的次数。如下图：

行的计数：注意由于页码没有01页、02页这一说法，所以行[0]中0出现0次，行[1]中1出现10次，行[2]中2出现10次...行[11]中11出现10次...；

列的计数：列[0]中0出现N/10次，列[1]中1出现N/10+1次...列[9]中9出现N/10次。

看上去每行每列数字出现的次数有点凌乱，其实稍微划分一下组成部分就可以了，如下分为五部分来计算（这里假设N-3==0，方便我们讲解）：

第一部分：第一行[0]中各列数字均出现1次；

第二部分：最后一行[N/10]中列[0]、列[1]、列[2]、列[3]中数字0、1、2、3各出现1次；

第三部分：列[0]到列[9]中0、1、2...9每个数字都出现N/10 - 1次。

第四部分：行[1]到行[N/10-1]中每个数字出现的次数（也就是总页码为N/10 - 1时各个数字出现的次数--这里要递归哦）乘以10。

第五部分：行[N/10]中每个数字均出现4次。

实现

Python实现如下：

def count_num(num):
    nums = [0 for x in range(10)]

    if num < 10:
        for i in range(1, num + 1):
            nums[i] = 1
        return nums
    
    # Part 1
    for i in range(1, 10):
        nums[i] += 1
        
    # Part 2
    units = num % 10
    for i in range(0, units + 1):
        nums[i] += 1
    
    # Part 3
    others = num / 10 - 1
    for i in range(0, 10):
        nums[i] += others
    
    # Part4
    count_others = count_num(others)
    for i in range(10):
        times_i = count_others[i] * 10
        nums[i] += times_i

    # Part 5
    digit_keep = []
    while num > 0:
        digit_keep.append(num % 10)
        num = num / 10
    times_units = digit_keep[0] + 1
    for digit in digit_keep[1:]:
        nums[digit] += times_units

    return nums

这篇文章没有什么技术干货，纯粹逼自己试着去把一些算法写的明白，大家觉得那块讲的不明白，我可以持续改进哈。

可以去我的主页看更多的博客。

GPU云服务器云服务器我明白了明白人对这些不太明白 python谁讲的好

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37609.html

JavaScript书籍测评

摘要：前言今天和大家一起聊聊的推荐书籍，每一本都是精选，做前端开发的朋友们如果没读过，可以尝试一下。如果怕麻烦，也可以关注晓舟报告，发送获取书籍，四个字，就可以得到电子书的提取码。前言今天和大家一起聊聊JavaScript的推荐书籍，每一本都是精选，做前端开发的朋友们如果没读过，可以尝试一下。下面给大家简单介绍了书的内容，还有读书的方法，希望可以帮大家提升读书效率。一、《JavaScr...

X1nFLY 2019-08-21 17:44 评论0 收藏0
轻量级桌面应用开发的捷径——nw.js

摘要：下面这张解决了怎么用完成任务的问题，最后，开发者怕你怀疑的强大，又提供了几个和许多成功的案例来打消我们的顾虑。拿下助攻决定用之后，就开始补充相应的知识啦。来欣赏一下一些应用的截图吧，不得不说开发出的应用一点不比原生的丑陋啊。博客地址每个程序员都希望用自己喜欢的语言，自己喜欢的平台、工具，写自己喜欢的程序。于是我们会看到有人在Win下用Visual Studio愉快地coding，也...

pumpkin9 2019-08-21 10:43 评论0 收藏0
Python爬虫之Scrapy学习（基础篇）

摘要：下载器下载器负责获取页面数据并提供给引擎，而后提供给。下载器中间件下载器中间件是在引擎及下载器之间的特定钩子，处理传递给引擎的。一旦页面下载完毕，下载器生成一个该页面的，并将其通过下载中间件返回方向发送给引擎。作者：xiaoyu微信公众号：Python数据科学知乎：Python数据分析师在爬虫的路上，学习scrapy是一个必不可少的环节。也许有好多朋友此时此刻也正在接触并学习sc...

pkhope 2019-07-31 11:05 评论0 收藏0
我的 2017 —— 一个 PHPer 的自白

摘要：大会年，我去了。小会值得一提的是，今年月份，我参加了一个的分享会。出游沙巴这是部门组织的出游，获得了最佳团队，拿到了一笔经费，于是有了这次出游。于是，我的下个目的地是西藏。转眼间 2017 年过去了。我已经不能说自己是去年的毕业生了，时光匆匆，感觉自己越来越老了。这一年，我所经历的，让我收获很多，让我懂得很多，让我明白了很多。也许是明确了某一个目标，也许是其它的什么，我觉得，201...

BenCHou 2019-06-28 14:36 评论0 收藏0
(原创)vue 学习笔记

摘要：菜鸟教程这是一个属性其值是字符串菜鸟教程同上这是一个属性其值是字符串用于定义的函数，可以通过来返回函数值。它们都有前缀，以便与用户定义的属性区分开来。开篇语我最近学习了js,取得进步,现在学习vue.js.建议新手学习,请不要用npm的方式(vue-cli,vue脚手架),太复杂了. 请直接下载vue.js文件本地引入,就上手学习吧参照菜鸟教程网站的vue.js教程http://...

layman 2019-08-22 18:09 评论0 收藏0