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

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

摘要

剑指 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》

相关文章:

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

摘要 剑指 Offer 43. 1&#xff5e;n 整数中 1 出现的次数 一、数学思维解析 将1~ n的个位、十位、百位、...的1出现次数相加&#xff0c;即为1出现的总次数。 设数字n是个x位数&#xff0c;记n的第i位为ni​&#xff0c;则可将n写为 nxnx−1⋯n2n1&#xff1a; 称" …...

如何成为程序员中的牛人/高手?

目录 一、牛人是怎么成为牛人的&#xff1f; 二、关于牛人的一点看法 三、让程序员与业务接壤&#xff0c;在开发团队中“升级” 四、使用低代码平台 目标效果 五、最后 祝伟大的程序员们梦想成真、码到成功&#xff01; 一、牛人是怎么成为牛人的&#xff1f; 最近在某…...

云原生时代顶流消息中间件Apache Pulsar部署实操之轻量级计算框架

文章目录Pulsar Functions(轻量级计算框架)基础定义工作流程函数运行时处理保证和订阅类型窗口函数定义窗口类型滚动窗口滑动窗口函数配置函数示例有状态函数示例窗口函数示例自定义函数开发定义原生语言接口示例Pulsar函数SDK示例Pulsar Functions(轻量级计算框架) 基础定义 …...

数据结构刷题(十九):77组合、216组合总和III

1.组合题目链接过程图&#xff1a;先从集合中取一个数&#xff0c;再依次从剩余数中取k-1个数。思路&#xff1a;回溯算法。使用回溯三部曲进行解题&#xff1a;递归函数的返回值以及参数&#xff1a;n&#xff0c;k&#xff0c;startIndex(记录每次循环集合从哪里开始遍历的位…...

PyQt 做美*女GIF设置桌面,每天都很爱~

人生苦短&#xff0c;我用python 要说程序员工作的最大压力不是来自于工作本身&#xff0c; 而是来自于需要不断学习才能更好地完成工作&#xff0c; 因为程序员工作中面对的编程语言是在不断更新的&#xff0c; 同时还要学习熟悉其他语言来提升竞争力… 好了&#xff0c;学习…...

[渗透测试笔记] 54.日薪2k的蓝队hw中级定级必备笔记系列篇3之域渗透黄金票据和白银票据

前文链接 [渗透测试笔记] 52.告别初级,日薪2k的蓝队hw中级定级必备笔记 [渗透测试笔记] 53.日薪2k的蓝队hw中级定级必备笔记2 文章目录 Kerberos认证协议NTLM认证协议Kerberos和NTLM比较黄金票据原理黄金票据条件复现过程白银票据原理白银票据条件复现过程黄金票据和白银票据…...

【异常】Spring Cloud Gateway网关自定义过滤器无法获取到请求体body的内容?不存在的!

一、需求说明 项目要使用到网关SpringCloud Gateway进行验签,现在定义了一个过滤器ValidateSignFilter, 我希望,所以过网关SpringCloud Gateway的请求,都能够校验一下请求头,看看是否有Sign这个字段放在请求头中。 二、异常说明 但是,我遇到了SpringCloud Gateway网关…...

CNN 卷积神经网络对染色血液细胞分类(blood-cells)

目录 1. 介绍 2. 加载数据 3. 可视化 3.1 显示单幅图像 3.2 显示多幅图像...

Kubernetes学习(三)Service

Service对象 为什么需要Service 每个Pod都有自己的IP地址&#xff0c;但是在Deployment中&#xff0c;在同一时刻运行的Pod集合可能与稍后运行该应用程序的Pod集合不同。 这就导致了一个问题&#xff1a;如果一组Pod&#xff08;称为后端&#xff09;为集群内其他Pod&#x…...

数学小课堂:古德-图灵折扣估计法和插值法(防范黑天鹅事件的方法)

文章目录 引言I 黑天鹅事件产生的原因1.1 置信度1.2 数据的稀疏性1.3 零概率问题II 防范黑天鹅事件的方法2.1 古德-图灵折扣估计法2.2 插值法引言 防范黑天鹅事件的方法 古德-图灵折扣估计法:它主要是解决零概率的事件古德的方法虽然解决了零概率的问题,但是依然没有解决数据…...

redis getshell方法

前言 参考文章 https://paper.seebug.org/1169 https://blog.csdn.net/weixin_55843787/article/details/123829606 https://blog.csdn.net/chenglanqi6606/article/details/100909518 Redis是什么 Redis是一款基于键值对的NoSQL数据库&#xff0c;它的值支持多种数据结构 …...

【ONE·C || 程序编译简述】

总言 C语言&#xff1a;程序编译相关。    文章目录总言1、程序的翻译环境和运行环境1.1、简述1.2、翻译环境&#xff1a;程序编译与链接1.2.1、简介&#xff1a;程序如何从.c文件形成.exe可执行程序1.2.2、过程说明1.3、运行环境2、预处理详解2.1、预定义符号2.2、#define2.…...

MGAT: Multimodal Graph Attention Network for Recommendation

模型总览如下&#xff1a; 图1&#xff1a;多模态图注意力网络背景&#xff1a;本论文是对MMGCN&#xff08;Wei et al., 2019&#xff09;的改进。MMGCN简单地在并行交互图上使用GNN&#xff0c;平等地对待从所有邻居传播的信息&#xff0c;无法自适应地捕获用户偏好。 MMGCN…...

在SNAP中用sentinel-1数据做InSAR测量,以门源地震为例

在SNAP中用sentinel-1数据做InSAR0 写在前面1 数据下载2 处理步骤2.1 split2.2 apply orbit 导入精密轨道2.3 查看数据的时空基线base line2.4 back-geocoding 配准2.5 Enhanced Spectral Diversity2.6 Deburst2.7 Interogram Formation 生成干涉图2.8 Multilook 多视2.9 Golds…...

MySQL常用函数

什么是函数&#xff1f; 函数是指一段可以直接被另一段程序调用的程序或代码。 字符串函数 函数功能CONCAT(S1,S2,…Sn)字符串拼接&#xff0c;将S1&#xff0c;S2&#xff0c;… Sn拼接成一个字符串LOWER(str)将字符串str全部转为小写LOWER(str)将字符串str全部转为小写LPAD(…...

51单片机数字电子钟开题报告

目录 选题背景 初步设计方案 芯片的选型 编译环境 关键问题 策略 方案 参考文献 选题背景 数字电子钟是一种受到越来越多人喜爱的钟表&#xff0c;其准确性和稳定性成为设计和研发的重要考虑因素。在现代社会&#xff0c;时间的准确性对于各行各业都非常重要&#xff0…...

day7 HTTP协议

HTTP协议 什么是协议&#xff1f; 协议实际上是某些人&#xff0c;或者某些组织提前制定好的一套规范&#xff0c;大家都按照这个规范来&#xff0c;这样可以做到沟通无障碍。协议就是一套规范&#xff0c;就是一套标准。由其他人或其他组织来负责制定的。我说的话你能听懂&…...

3DCAT+一汽奥迪:共建线上个性化订车实时云渲染方案

近年来&#xff0c;随着5G网络和云计算技术的不断发展&#xff0c;交互式3D实时云看车正在成为一种新的看车方式。与传统的到4S店实地考察不同&#xff0c;消费者可以足不出户&#xff0c;通过网络与终端设备即可实现全方位展示、自选汽车配色、模拟效果、快捷选车并进行个性化…...

yii2项目使用frp https2http插件问题

yii2内网项目&#xff0c;使用frp进行内网穿透&#xff0c;使用 https2http插件把内网服务器http流量转成https&#xff0c;会存在一个问题&#xff1a;当使用 $this->redirect(...) 或 $this->goHome() &#xff08;其实用的也是前者&#xff09;等重定向时&#xff0c;…...

关于 interface{} 会有啥注意事项?下

我们一起来回顾一下上一次说到的 interface{} 可以用来做多态 接口类型分为空接口类型和非空接口类型&#xff0c;他们的底层数据结构不太一样 这里顺便说一下&#xff0c;用来作态需要满足这样的条件&#xff1a; 首先得有父类指针指向子类的对象这个接口还必须是非空接口…...

2026年最新英语单词AI辅助工具 帮英语学习者轻松提升背词效率

英语单词学习的核心痛点拆解我们团队做英语学习工具测评快5年了&#xff0c;后台收到最多的提问就是「有没有能真的提升背词效率的工具」&#xff0c;拆解下来行业的共性痛点其实很明确&#xff1a;第一是资源错配&#xff0c;80%的背词时间都花在已经掌握的词汇上&#xff0c;…...

从UHS-II到DDR4:2014年存储技术演进与工程实践启示

1. 项目概述&#xff1a;一次2014年秋的存储技术快照九月的风刚带起一丝凉意&#xff0c;存储半导体领域却热闹非凡。作为一名长期跟踪硬件发展的从业者&#xff0c;我习惯定期梳理行业动态&#xff0c;而2014年9月这份来自EE Times的“Memory Product Round Up”产品汇总&…...

OpenClaw vs Hermes Agent,谁是 2026 年 AI Agent 最优解?

OpenClaw+Hermes 全集成,一键调用所有 AI 技能:https://ai-skills.ai/?inviteCode=S2JV3NCK 前言 2026 年,AI Agent 已从 “实验玩具” 迈入 “工程化落地” 关键期。GitHub 上 OpenClaw 与 Hermes Agent 两大开源项目热度飙升,均宣称解决大模型 “失忆、弱执行、难沉淀”…...

动态自适应网络:让AI模型根据输入复杂度智能调节算力与精度

1. 项目概述&#xff1a;当计算机视觉遇见能效瓶颈在边缘计算和移动设备上部署深度神经网络&#xff08;DNN&#xff09;进行计算机视觉任务&#xff0c;比如人脸识别、物体检测&#xff0c;已经不是什么新鲜事了。但一个老生常谈的痛点始终横在那里&#xff1a;算力、功耗和精…...

React 安装指南

React 安装指南 引言 React 是一个用于构建用户界面的JavaScript库,由Facebook开发。它被广泛用于开发单页应用(SPA)和复杂的前端应用。React的核心库仅负责视图层,而React生态系统还包括了许多其他库和工具,如React Router、Redux等。本指南将详细介绍如何在不同的环境…...

实战案例:使用tsne-cuda加速CIFAR-10数据集的高维可视化分析

实战案例&#xff1a;使用tsne-cuda加速CIFAR-10数据集的高维可视化分析 【免费下载链接】tsne-cuda GPU Accelerated t-SNE for CUDA with Python bindings 项目地址: https://gitcode.com/gh_mirrors/ts/tsne-cuda t-SNE是机器学习领域常用的高维数据降维可视化工具&a…...

python网上书店系统vue

目录技术栈选择前端模块划分后端API设计关键实现细节开发流程示例代码片段项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作技术栈选择 前端采用Vue 3&#xff08;Composition API&#xff09; TypeScript Vite构建工具&#…...

搜极星破局:拆解企业 “看不见、控不住、比不过” 困局

引言&#xff1a;AI 时代&#xff0c;企业陷入三重信息绝境2026 年&#xff0c;生成式 AI 全面主导用户决策链路&#xff0c;品牌竞争从搜索排名转向 AI 认知权重。但多数企业正深陷看不见、控不住、比不过的三重困局&#xff1a;看不见自身在 AI 平台的真实曝光状态&#xff0…...

3分钟实现Zotero与Notion双向联动:Notero完整使用指南

3分钟实现Zotero与Notion双向联动&#xff1a;Notero完整使用指南 【免费下载链接】notero A Zotero plugin for syncing items and notes into Notion 项目地址: https://gitcode.com/gh_mirrors/no/notero 你是否曾为学术研究中的文献管理而烦恼&#xff1f;Zotero中精…...

从游戏角色到人脸分析:聊聊‘摇头、点头、转头’背后的欧拉角与万向节死锁

游戏角色控制与人脸分析的奇妙交汇&#xff1a;解码欧拉角与万向节死锁 想象一下你在玩一款3A级开放世界游戏&#xff1a;按下左摇杆&#xff0c;角色开始左右张望&#xff1b;推动右摇杆&#xff0c;角色抬头望向天空中的飞龙&#xff1b;同时扳动两个摇杆&#xff0c;角色做出…...