题目描述：JZ43 整数中1出现的次数（从1到n整数中1出现的次数）

思路1：动态规划

  • 状态表示：dp[i]
    • 集合：从 1～n 整数中 1 出现的次数
    • 属性：次数
  • 状态计算：依据当前数字是否包含 1
    • 包含 1：dp[i-1] + 1
    • 不包含 1：dp[i-1]
时间复杂度：O(n)，空间复杂度：O(n)

注意：当 n 的范围，超过2312^{31}，dp数组储存不下，过不了

#include <vector>
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if (!n) return 0;
        vector<int> dp(30001, 0);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int time = 0;
            int x = i;
            while (x) {
                int y = x % 10;
                if (y == 1) time++;
                x /= 10;
            }
            dp[i] = dp[i-1]+time;
        }
        return dp[n];
    }
};

思路2：按位统计法

时间复杂度：O(logn)，空间复杂度：O(1)

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        long long mulk = 1;
        int res = 0;
        for (int k = 0; n >= mulk; ++k) {
            res += (n / (mulk * 10)) * mulk + \
                min(max(n % (mulk * 10) - mulk + 1, 0LL), mulk);
            mulk *= 10;
        }
        return res;
    }
};

😿😿😿😿😿😿😿😿