网站建设技术咨询协议,内蒙古建设厅设计处网站,网件路由器怎么恢复出厂设置,免费简约ppt模板目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介… 目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题 从1到n的自然数组中1出现的次数如何计算 如 [1…11] 中有1的有 1,10,11结果为4
解决方案
原问题 首先给一个示例n 114时求[1…114]之间1的个数 首先我们求15 - 114之间1的个数然后再求[1…14]之间1的个数为什么这么来可以看下面的感 1 15-114之间1的个数如何求 1、首先百位是1时的数一共有14个如果百位是2时则百位是1的个数就是100-199也就是 10^2个 2、其次求10位是1的个数百位首先范围只能是1如果百位是2那么范围就是[1…2]按照除了十位和百位以外其他的可以随便取所以就是10^1个如果百位是2就是 2 * 10^1个 3、接下来算个位时同十位相同那么这个时候你可能会问个位时1时十位难道不限制吗哎就是不用限制为什么看下面1 先看下代码怎么写然后咱们讨论一下巧妙之处~
代码编写
java语言版本
原问题 方法一 /*** 二轮测试 给定整数num求1-num中1出现的次数* param num* return*/public static int oneNumCp1(int num) {if (num 1) {return 0;}if (num 10) {// 10以内的数只有一个1return 1;}// 计算位数int len 0;int tem num;while (tem ! 0) {len ;tem / 10;}// 求起点tem num;// 最高位int height (int)(tem / Math.pow(10, len-1));// 当前轮的起点int start (int)(tem - (height) * Math.pow(10, len-1)) 1;// 计算当前层的1的个数int oneNum 0;// 先计算最高位是1的情况if (height 1) {// 最高位是1oneNum start;}else {oneNum Math.pow(10, len-1);}// 剩余的自由组合oneNum Math.pow(10, len-2) * height * (len-1);return oneNum oneNumCp1(start-1);}public static void main(String[] args) {System.out.println(oneNumCp1(114));}c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津 首先这个答案可以解释上面两个疑惑 为什么偏偏计算15-114呢就是因为我们在计算个位后面可能是低位的时候以为十位可能会被限制为1不能为2这样计算起来很麻烦所以这里取巧了将15-99的数字全部加载114的后面这样就凑齐了100-199这样计算个位就不会被10位限制很显然后续的计算直接计算1-15也不会再计算15-99了。 2、现在114并不典型我们需要注意一下214的情况 214的解法仍然是求15 - 214先我们发现15-99能够填充214到299首先算十位是没有变化的注意十位是1时百位是2时219等价于 019 虽然219不存在但是019能够作为代替这也解释了为什么百位不能为1只能是1-2的范围。 3、还有一个容易误会的地方就是刚开始我会觉得当十位是1的时候个位会有1的时候那么计算个位1的时候十位也会有1的时候是否会有重复 这里是一个理解误区我们在计算1的个数时如果有一个数是111那么这个数应该被计数三次才对很显然我们在排列组合的时候会计算三次完全没有问题 ↩︎ ↩︎
