剑指Offer Java版 面试题43：1~n整数中1出现的次数

题目：输入一个整数n，求1 ~ n这n个整数的十进制表示中1出现的次数。例如，输入12，1 ~ 12这些整数中包含1的数字有1、10、11和12，1一共出现了5次。

练习地址

https://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6

不考虑时间效率的解法，靠它想拿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)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题