建设银行杭州纪念币预约网站,长沙网站设计流程,织梦网站做404页面,创意手工摘要
剑指 Offer 43. 1#xff5e;n 整数中 1 出现的次数
一、数学思维解析
将1~ n的个位、十位、百位、...的1出现次数相加#xff0c;即为1出现的总次数。
设数字n是个x位数#xff0c;记n的第i位为ni#xff0c;则可将n写为 nxnx−1⋯n2n1#xff1a;
称 …摘要
剑指 Offer 43. 1n 整数中 1 出现的次数
一、数学思维解析
将1~ n的个位、十位、百位、...的1出现次数相加即为1出现的总次数。
设数字n是个x位数记n的第i位为ni则可将n写为 nxnx−1⋯n2n1
称 ni 为 当前位 记为 cur 将 ni−1ni−2⋯n2n1 称为 低位 记为low 将 nxnx−1⋯ni2ni1 称为高位 记为high 。将10i称为位因子 记为digit。
某位中1出现次数的计算方法根据当前位 cur值的不同分为以下三种情况
当 cur0时 此位1的出现次数只由高位 high决定计算公式为high×digit 当cur1时 此位1的出现次数由高位high和低位low决定计算公式为high×digitlow1 当cur2,3,⋯ ,9时 此位1的出现次数只由高位 high决定计算公式为(high1)×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(logn) 循环内的计算操作使用O(1)时间循环次数为数字n的位数即log10n因此循环使用O(logn)时间。空间复杂度 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的位数即log10n因此循环使用O(logn)时间。空间复杂度 O(n) 几个变量使用常数大小的额外空间。
博文参考
《leetcode》
