死磕算法系列文章
干货 | 手撕十大经典排序算法
剑指offer | 认识面试
剑指offer | 面试题2:实现Singleton模式
剑指offer | 面试题3:二维数组的查找
剑指offer | 面试题4:替换空格
剑指offer | 面试题5:从尾到头打印链表
剑指offer | 面试题6:重建二叉树
剑指offer | 面试题7:用两个栈实现队列
剑指offer | 面试题8:旋转数组的最小数字
剑指offer | 面试题9:斐波那契数列
剑指offer | 面试题10:青蛙跳台阶问题
剑指offer | 面试题11:矩阵覆盖
剑指offer | 面试题12:二进制中1的个数
剑指offer | 面试题13:数值的整数次方
剑指offer | 面试题14:打印从1到最大的n位数
剑指offer | 面试题15:删除链表的节点
剑指offer | 面试题16:将数组中的奇数放在偶数前
剑指offer | 面试题17:链表中倒数第k个节点
剑指offer | 面试题18:反转链表
剑指offer | 面试题19:合并两个有序链表
剑指offer | 面试题20:判断二叉树A中是否包含子树B
剑指offer | 面试题21:二叉树的镜像
剑指offer | 面试题22:顺时针打印矩阵
剑指offer | 面试题23:包含min函数的栈
剑指offer | 面试题24:栈的压入、弹出序列
剑指offer | 面试题25:从上到下打印二叉树
剑指offer | 面试题26:二叉搜索树的后序遍历序列
剑指offer | 面试题27:二叉树中和为某一值的路径
剑指offer | 面试题28:复杂链表的复制
剑指offer | 面试题29:二叉搜索树转换为双向链表
剑指offer | 面试题30:字符串的排列
剑指offer | 面试题31:数组中出现次数超过一半的数字
剑指offer | 面试题32:最小的k个数
剑指offer | 面试题33:连续子数组的最大和
欢迎关注千羽的公众号
程序员千羽
“Leetcode : https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
“GitHub : https://github.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_34_countDigitOne/Solution.java
1~n 整数中 1 出现的次数
“题目描述 :输入一个整数 n ,求1~n这n个整数的十进制表示中1出现的次数。例如,输入12,1~12这些整数中包含1 的数字有1、10、11和12,1一共出现了5次。难度:困难示例 1:
输入:n = 12
输出:5
示例 2:
输入:n = 13
输出:6
读题->纸上钻研->半小时过去->打开题解->看到路飞->眼中泛光->阅读题解->发出感叹->”牛逼”
解题思路:
某位中1出现次数的计算方法: 根据当前位cur值的不同,分为以下三种情况:
当cur=0时:此位1的出现次数只由高位high决定,计算公式为: high x digit
“如下图所示,以 n = 2304 为例,求 digit = 10 (即十位)的 1 出现次数。
Picture1.png
当 cur = 1 时: 此位 1 的出现次数由高位 high和低位 low 决定,
high x digit + low+ 1
当cur=2,3,… ,9时:此位1的出现次数只由高位high决定,计算公式为: (high+ 1) x digit . 如下图所示,以n= 2324为例,求digit= 10 (即十位) 的1出现次数。
变量递推公式: . 设计按照“个位、十位、.. 的顺序计算,则high/cur/low/digit应初始化为: .
high = n // 10
cur = n % 10
low = 0
digit = 1 # 个位
因此,从个位到最高位的变量递推公式为:
while high != 0 or cur != 0: # 当 high 和 cur 同时为 0 时,说明已经越过最高位,因此跳出
low += cur * digit # 将 cur 加入 low ,组成下轮 low
cur = high % 10 # 下轮 cur 是本轮 high 的最低位
high //= 10 # 将本轮 high 最低位删除,得到下轮 high
digit *= 10 # 位因子每轮 × 10
复杂度分析:
时间复杂度O(logn) :循环内的计算操作使用O(1)时间;循环次数为数字n的位数,即log10n,因 此循环使用O(log n)时间。
空间复杂度0(1): 几个变量使用常数大小的额外空间。
package com.nateshao.sword_offer.topic_34_countDigitOne;
/**
- @date Created by 邵桐杰 on 2021/12/11 11:00
- @微信公众号 程序员千羽
- @个人网站 www.nateshao.cn
- @博客 https://nateshao.gitee.io
- @GitHub https://github.com/nateshao
- @Gitee https://gitee.com/nateshao
- Description: 剑指 Offer 43. 1~n 整数中 1 出现的次数
- https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
*/
public class Solution {
public static void main(String[] args) {
int n = 12;
System.out.println(“countDigitOne1(n) = ” + countDigitOne1(n));// countDigitOne1(n) = 5
System.out.println(“countDigitOne2(n) = ” + countDigitOne2(n));// countDigitOne2(n) = 5
System.out.println(“countDigitOne3(n) = ” + countDigitOne3(n));// countDigitOne3(n) = 5
} /**- 方法一:计算高低位
* - @param n
- @return
*/
public static int countDigitOne1(int n) {
int count = 0;
int i = 1;
int current = 0, after = 0, before = 0;
while ((n / i != 0)) {
before = n / (i * 10);// 高位
current = (n / i % 10);// 当前位
after = n – (n / i) * i;// 低位
// 如果为 0,出现 1 的次数由高位决定,等于高位数字 * 当前位数
if (current == 0) count = count + before * i;
// 如果为 1,出现 1 的次数由高位和低位决定,高位*当前位+低位+1
else if (current == 1) count = count + before * i + after + 1;
// 如果大于 1,出现 1 的次数由高位决定,(高位数字+1)* 当前位数
else if (current > 1) count = count + (before + 1) * i;
// 前移一位
i = i * 10;
}
return count;
}
- 方法二:公式法
* - @param n
- @return
*/
public static int countDigitOne2(int n) {
// mulk 表示 10^k
// 在下面的代码中,可以发现 k 并没有被直接使用到(都是使用 10^k)
// 但为了让代码看起来更加直观,这里保留了 k
long mulk = 1;
int ans = 0;
for (int k = 0; n >= mulk; ++k) {
ans += (n / (mulk * 10)) * mulk + Math.min(Math.max(n % (mulk * 10) – mulk + 1, 0), mulk);
mulk *= 10;
}
return ans;
}
- 方法三: 递归
- @param n
- @return
*/
public static int countDigitOne3(int n) {
return f(n);
}
private static int f(int n){
// 上一级递归 n = 20、10之类的整十整百之类的情况;以及n=0的情况
if(n== 0) return 0;
// n < 10 即为个位,这样子只有一个1
if(n < 10) return 1; - 方法一:计算高低位
String s = String.valueOf(n); //长度:按例子来说是4位 int length = s.length(); //这个base是解题速度100%的关键,本例中的是999中1的个数:300 // 99的话就是20 ; 9的话就是1 ;9999就是4000 这里大家应该发现规律了吧。 int base = (length-1)*(int)Math.pow(10,length-2); //high就是最高位的数字 int high = s.charAt(0) - '0'; //cur就是当前所数量级,即1000 int cur = (int)Math.pow(10,length -1); if(high == 1){ //最高位为1,1+n-cur就是1000~1234中由千位数提供的1的个数,剩下的f函数就是求1000~1234中由234产生的1的个数 return base + 1 + n - cur + f(n - high * cur); }else{ //这个自己思考 return base * high + cur + f(n- high * cur); }
}
}
参考文献:
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/1n-zheng-shu-zhong-1-chu-xian-de-ci-shu-umaj8/
声明:文中观点不代表本站立场。本文传送门:http://eyangzhen.com/213336.html