number-of-digit-one.md

233. Number of Digit One - 数字 1 的个数

Tags - 题目标签

Description - 题目描述

EN:

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

 

Example 1:

Input: n = 13
Output: 6

Example 2:

Input: n = 0
Output: 0

 

Constraints:

• 0 <= n <= 109

ZH-CN:

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

 

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

 

提示：

• 0 <= n <= 109

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	56 ms	42.3 MB	2022/04/11 16:30

function countDigitOne(n: number): number {
  const numArr = n.toString().split('').reverse();
  const dp1: number[] = [];
  const dp2: number[] = [];

  dp1[0] = 1;

  dp2[0] = numArr[0] === '0' ? 0 : 1;

  for (let i = 1; i < numArr.length; i++) {
    dp1[i] = 10 * dp1[i-1] + Math.pow(10, i);

    if (numArr[i] === '0') {
      dp2[i] = dp2[i-1];
    } else if (numArr[i] === '1') {
      const rest = Number(numArr.slice(0, i).reverse().join('')) + 1;
      dp2[i] = dp2[i-1] + rest + dp1[i-1];
    } else {
      dp2[i] = (Number(numArr[i])) * dp1[i-1] + Math.pow(10, i) + dp2[i-1];
    }
  }

  return dp2[numArr.length-1];
};

My Notes - 我的笔记

与 剑指 Offer 43: 1～n 整数中 1 出现的次数 相同，解决方法应该是数位 dp 是最稳妥的。

可以去看看剑指 offer 的那道题的笔记。