题目：输入一个整数n，求1 ~ n这n个整数的十进制表示中1出现的次数。例如，输入12，1 ~ 12这些整数中包含1的数字有1、10、11和12，1一共出现了5次。
练习地址
https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
不考虑时间效率的解法，靠它想拿 Offer 有点难
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int number = 0;
for (int i = 1; i <= n; i++) {
number += numberOf1(i);
}
return number;
}
private int numberOf1(int n) {
int number = 0;
while (n > 0) {
if (n % 10 == 1) {
number++;
}
n /= 10;
}
return number;
}
}
复杂度分析
- 时间复杂度：O(nlogn)。
- 空间复杂度：O(1)。
从数字规律着手明显提高时间效率的解法，能让面试官耳目一新
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if (n <= 0) {
return 0;
}
return numberOf1(String.valueOf(n), 0);
}
private int numberOf1(String str, int index) {
if (index == str.length()) {
return 0;
}
int first = str.charAt(index) - '0';
int length = str.length() - index;
if (length == 1) {
if (first == 0) {
return 0;
}
if (first > 0) {
return 1;
}
}
// 假设 str 是 "21345"
// numFirst 是数字 10000~19999 的第一位中的数目
int numFirst = 0;
if (first > 1) {
numFirst = power10(length - 1);
} else if (first == 1) {
numFirst = Integer.parseInt(str) % power10(length - 1) + 1;
}
// numOthers 是 1346~21345 除第一位之外的数位中的数目
int numOthers = first * (length - 1) * power10(length - 2);
// numRecursive 是 1~1345 中的数目
int numRecursive = numberOf1(str, index + 1);
return numFirst + numOthers + numRecursive;
}
private int power10(int n) {
int result = 1;
for (int i = 0; i < n; i++) {
result *= 10;
}
return result;
}
}
复杂度分析
- 时间复杂度：O(logn)。
- 空间复杂度：O(logn)。
