【困难】1~N 整数中出现 1 的次数（数位dp）

阳光穿透心脏的1/2处 2022-09-11 09:28 123阅读 0赞

#### 问题： ####

给你一个数 N 。问 1-N 之间有多少个 1

#### dp 模型 ####

1.  二叉树递归套路，树型 dp
2.  斐波那契 模型，矩阵dp
3.  从左往右的尝试模型（背包问题
4.  范围尝试模型
5.  行列模型（一个样本做行，一个做列）
6.  业务限制模型
7.  数位 dp

#### 【暴力解法】时间复杂度 O（N \* lgN） ####

遍历所有数字，计算每个数字包含 1 的个数累加返回

#### 【数位 dp 思路】时间复杂度 O（lgN^2） ####

> 采用数位 dp 的思路求解。 整体思路为计算每位为 1 的情况由多少种，然后将所有情况相加即为答案。 举例：N = 384361  
> 分布求解  
> 84362 - 384361 中多少个 1  
> 4362 - 84361 中多少个 1  
> 362 - 4361 有多少个 1  
> 62 - 361 有多少个 1  
> 2 - 61 有多少个 1  
> 1 - 1 有多少个 1
> 
> 定义一个递归函数 f(N) 返回 1-N 包含多少个 1  
> 该函数中分两个部分，递归部分和非递归部分  
> 对于 f(384361) = f(84361) + (84362 - 384361 有多少个1 非递归过程)
> 
> 这里 (84362 - 384361 有多少个1) 就是我们的算法部分。
> 
> 分类讨论： 最高位是 1 最高位不是 1

#### 题解 ####

package algorithmic.total.solution.common;
    
    /** * @program: algorithmic-total-solution * @description: 多少个 1 问题 * 给你一个数 N 。问 1-N 之间有多少个 1 * 数位 dp * @author: wangzibin **/
    public class Question3 { 
    
    
        public static void main(String[] args) { 
            /** * 对数器 */
            for (int i=10000;i<99999;i++){ 
                long oneNumberSimple = getOneNumberSimple(i);
                long oneNumber = getOneNumber(i);
                if (oneNumber!=oneNumberSimple){ 
                    System.out.println(i+" 错误：oneNumberSimple="+oneNumberSimple+" oneNumber="+oneNumber);
                }
            }
        }
    
    
        public static long getOneNumberSimpleWithLog(long num){ 
            long start=System.currentTimeMillis();
            long oneNumberSimple = getOneNumberSimple(num);
            System.out.println("getOneNumberSimpleWithLog 耗时："+(System.currentTimeMillis()-start));
            return oneNumberSimple;
        }
    
        public static long getOneNumberWithLog(long num){ 
            long start=System.currentTimeMillis();
            long oneNumberSimple = getOneNumber(num);
            System.out.println("getOneNumberWithLog 耗时："+(System.currentTimeMillis()-start));
            return oneNumberSimple;
        }
    
    
        /** * @Description: 计算 1-number 间有多少个 1 * 时间复杂度 O（lgN^2） * @Param number * @Return: long */
        public static long getOneNumber(long number) { 
            if (number < 10 && number > 0) { 
                return 1;
            }else if (number<=0){ 
                return 0;
            }
            //对于任意的 number 分类讨论最高位是 1 的情况
            int firstNum = getFirstNum(number);
            int len = getNumberLength(number);
            long result = 0;
            long firstCountOne = 0;
            long otherCountOne = 0;
            long tenPowerX = tenPowerX(len - 1);
            if (firstNum == 1) { 
                // 按位计算每一位为 1 所包含的数 假设 k 位
                // 最高位公式 N % 10^k-1 + 1
                // 其余位个数 (k-1) * 10^k-2 * 1
                firstCountOne = number % tenPowerX + 1;
            } else { 
                // 非 1
                // 最高位公式 10^k-1
                // 其余位个数 (k-1) * 10^k-2 * firstNum
                firstCountOne = tenPowerX;
            }
            otherCountOne = (len - 1) * tenPowerX(len - 2) * firstNum;
            // 总的 1 的数量
            result = firstCountOne + otherCountOne;
            // 需要递归的下一个数 例如 5472 则 next 为 472
            long nextNum = number % tenPowerX;
            return result + getOneNumber(nextNum);
        }
    
    
        /** * @Description: 计算 1-number 间有多少个 1 * 时间复杂度 O（N * lgN） * @Param number * @Return: long */
        public static long getOneNumberSimple(long number) { 
            long result = 0;
            for (int i = 1; i <= number; i++) { 
                result += countOne(i);
            }
            return result;
        }
    
        /** * @Description: 10 的 x 次方 * @Param x * @Return: long */
        private static long tenPowerX(int x) { 
            if (x == 0) { 
                return 1;
            }
            long num = 10;
            for (int i = 1; i < x; i++) { 
                num = num * 10;
            }
            return num;
        }
    
        /** * @Description: 获取 num 的长度 * @Param num * @Return: int */
        private static int getNumberLength(long num) { 
            int len = 0;
            while (num > 0) { 
                num = num / 10;
                len++;
            }
            return len;
        }
    
        /** * @Description: 获取最高位 * @Param number * @Return: int */
        private static int getFirstNum(long num) { 
            while (num >= 10) { 
                num = num / 10;
            }
            return Math.toIntExact(num);
        }
    
    
    
        /** * @Description: 计算 num 包含 1 的个数 * @Param num * @Return: long */
        private static long countOne(int num) { 
            long count = 0;
            while (num > 0) { 
                if (num % 10 == 1) { 
                    count++;
                }
                num = num / 10;
            }
            return count;
        }
    
    }

#### leetcode AC 代码 ####

题目地址：  
[1～n 整数中 1 出现的次数][1_n _ 1]

class Solution { 
        public int countDigitOne(int n) { 
            return getOneNumber(n);
        }
        public static int getOneNumber(int number) { 
            if (number < 10 && number > 0) { 
                return 1;
            }else if (number<=0){ 
                return 0;
            }
            //对于任意的 number 分类讨论最高位是 1 的情况
            int firstNum = getFirstNum(number);
            int len = getNumberLength(number);
            int result = 0;
            int firstCountOne = 0;
            int otherCountOne = 0;
            int tenPowerX = tenPowerX(len - 1);
            if (firstNum == 1) { 
                // 按位计算每一位为 1 所包含的数 假设 k 位
                // 最高位公式 N % 10^k-1 + 1
                // 其余位个数 (k-1) * 10^k-2 * 1
                firstCountOne = number % tenPowerX + 1;
            } else { 
                // 非 1
                // 最高位公式 10^k-1
                // 其余位个数 (k-1) * 10^k-2 * firstNum
                firstCountOne = tenPowerX;
            }
            otherCountOne = (len - 1) * tenPowerX(len - 2) * firstNum;
            // 总的 1 的数量
            result = firstCountOne + otherCountOne;
            // 需要递归的下一个数 例如 5472 则 next 为 472
            int nextNum = number % tenPowerX;
            return result + getOneNumber(nextNum);
        }
    
         /** * @Description: 10 的 x 次方 * @Param x * @Return: long */
        private static int tenPowerX(int x) { 
            if (x == 0) { 
                return 1;
            }
            int num = 10;
            for (int i = 1; i < x; i++) { 
                num = num * 10;
            }
            return num;
        }
    
        /** * @Description: 获取 num 的长度 * @Param num * @Return: int */
        private static int getNumberLength(long num) { 
            int len = 0;
            while (num > 0) { 
                num = num / 10;
                len++;
            }
            return len;
        }
    
        /** * @Description: 获取最高位 * @Param number * @Return: int */
        private static int getFirstNum(long num) { 
            while (num >= 10) { 
                num = num / 10;
            }
            return Math.toIntExact(num);
        }
    }

[1_n _ 1]: https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/submissions/