当前位置: 首页 > news >正文

黔西县城市建设局网站免费网站做seo

黔西县城市建设局网站,免费网站做seo,大连网站建设公司,唐山哪个公司做网站摘要 剑指 Offer 43. 1~n 整数中 1 出现的次数 一、数学思维解析 将1~ n的个位、十位、百位、...的1出现次数相加,即为1出现的总次数。 设数字n是个x位数,记n的第i位为ni​,则可将n写为 nxnx−1⋯n2n1: 称" …

摘要

剑指 Offer 43. 1~n 整数中 1 出现的次数

一、数学思维解析

将1~ n的个位、十位、百位、...的1出现次数相加,即为1出现的总次数。

设数字n是个x位数,记n的第i位为ni​,则可将n写为 nxnx−1⋯n2n1:

  • 称" ni" 为 当前位 ,记为 cur ,
  • 将" ni−1ni−2⋯n2n1​ " 称为 低位 ,记为low ;
  • 将" nxnx−1⋯ni+2ni+1​ " 称为高位 ,记为high 。
  • 将10i称为位因子 ,记为digit。

某位中1出现次数的计算方法:根据当前位 cur值的不同,分为以下三种情况:

当 cur=0时: 此位1的出现次数只由高位 high决定,计算公式为:high×digit:

 当cur=1时: 此位1的出现次数由高位high和低位low决定,计算公式为:high×digit+low+1

当cur=2,3,⋯ ,9时 此位1的出现次数只由高位 high决定,计算公式为:(high+1)×digit:

package Math;/*** @Classname JZ43整数中1出现的次数* @Description TODO* @Date 2023/3/7 20:55* @Created by xjl*/
public class JZ43整数中1出现的次数 {/*** @description 整数中1出现的次数 * @param: n* @date: 2023/3/7 20:56* @return: int* @author: xjl*/public int countDigitOne(int n) {int digit = 1, res = 0;int high = n / 10, cur = n % 10, low = 0;while (high != 0 || cur != 0) {if (cur == 0) {res += high * digit;} else if (cur == 1) {res += high * digit + low + 1;} else {res += (high + 1) * digit;}low += cur * digit;cur = high % 10;high /= 10;digit *= 10;}return res;}
}

复杂度分析

  • 时间复杂度O(log⁡n): 循环内的计算操作使用O(1)时间;循环次数为数字n的位数,即log⁡10n,因此循环使用O(log⁡n)时间。
  • 空间复杂度 O(1) : 几个变量使用常数大小的额外空间。

二、暴力解析

一般是超时的选择

    /*** @description 相当于的暴力求解的顺序* @param: n* @date: 2023/3/7 21:15* @return: int* @author: xjl*/public int countDigitOne2(int n) {String result = "";for (int i = 1; i <= n; i++) {result += String.valueOf(i);}int count = 0;for (int i = 0; i < result.length(); i++) {if (result.charAt(i) == '1') {count++;}}return count;}

复杂度分析

  • 时间复杂度O(n): 循环内的计算操作使用O(1)时间;循环次数为数字n的位数,即log⁡10n,因此循环使用O(log⁡n)时间。
  • 空间复杂度 O(n) : 几个变量使用常数大小的额外空间。

博文参考

《leetcode》

http://www.zhongyajixie.com/news/17772.html

相关文章:

  • 南京做网站优化的企业seo排名app
  • 规划阿里巴巴网站怎么做百度网盘搜索引擎
  • 杭州做网站企业专业培训机构
  • 上海网站制作网站建设利尔化学股票
  • 搜网站网seo网站快排
  • 创意摄影网站网络营销的企业有哪些
  • 自己的网站做app济南优化网站的哪家好
  • 如何高效率的建设网站济南疫情最新消息
  • 阿里巴巴怎么做自己的免费网站哈尔滨seo优化培训
  • 微信公众号做视频网站指数基金定投怎么买
  • 芜湖设计公司排名关键词seo优化公司
  • 适合大网站做安全性测试的工具产品推广策略
  • 郑州做网站要多少钱网站快速排名优化价格
  • 肯德基的网站建设学校招生网络营销方案
  • godaddy服务器做网站seo网站快速排名软件
  • 做平台交易网站怎么收款引擎搜索器
  • 建的企业网站如何在百度搜到重庆百度地图
  • 微信官网网站网络服务器是指什么
  • 免费优化推广网站的软件百度推广深圳分公司
  • 网页托管平台慧达seo免登录发布
  • 集团网站建设工作方案搜索
  • 网站设计是什么专业seo网站内部优化
  • 互联国际网站代刷网站推广快速
  • 网站频道策划seo网站自动推广
  • 回龙观做网站太原seo代理商
  • 那个网站做的好快速学电脑培训班
  • 时时彩的网站怎么做国际实时新闻
  • 重庆知名商城网站建设公司软件推广的渠道是哪里找的
  • wordpress带灯箱的主题企业seo职位
  • 网站放到iis如何做指向四年级的简短新闻播报