題目：輸入一個(gè)整數(shù)n姓建，求1 ~ n這n個(gè)整數(shù)的十進(jìn)制表示中1出現(xiàn)的次數(shù)诞仓。例如，輸入12速兔，1 ~ 12這些整數(shù)中包含1的數(shù)字有1墅拭、10、11和12涣狗，1一共出現(xiàn)了5次谍婉。
練習(xí)地址
https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
不考慮時(shí)間效率的解法，靠它想拿 Offer 有點(diǎn)難
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;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(nlogn)镀钓。
- 空間復(fù)雜度：O(1)穗熬。
從數(shù)字規(guī)律著手明顯提高時(shí)間效率的解法，能讓面試官耳目一新
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;
}
}
// 假設(shè) str 是 "21345"
// numFirst 是數(shù)字 10000~19999 的第一位中的數(shù)目
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 除第一位之外的數(shù)位中的數(shù)目
int numOthers = first * (length - 1) * power10(length - 2);
// numRecursive 是 1~1345 中的數(shù)目
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;
}
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(logn)丁溅。
- 空間復(fù)雜度：O(logn)唤蔗。
