AlgoPressAppearance
OF43-1~n整数中1出现的次数
题目描述
https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof
输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：
输入：n = 12
输出：5
示例 2：
输入：n = 13
输出：6
限制：
1 <= n <2^31
注意：本题与主站 233 题相同：https://leetcode.cn/problems/number-of-digit-one/
思路：暴力法
每次求取一个数是否是1然后加入结果，将 pre 的数传入做优化 但是还是会超时
实现代码
csharp
public class Solution {
private int countOne(int pre, int n){
int rem = n % 10;
if(rem == 0){
return pre+1;
}
if(rem == 1){
return pre - 1;
}
if(rem > 1 && rem < 9){
return pre;
}
int count = 0;
while(n > 0){
int digit = n % 10;
if(digit == 1){
count++;
}
n = n / 10;
}
//Console.WriteLine("num:{0},one:{1}",n,count);
return count;
}
public int CountDigitOne(int n) {
int total = 0;
int pre = 0;
for(int i=1; i<=n; i++){
pre = countOne(pre,i);
total += pre;
}
return total;
}
}
思路2：动态规划
假设一个数字有n位，那么他含有1的个数应该是后n-1 的 第一位的个数，我们用动态规划先设置个位数的默认值，然后依次根据前面的值dp值计算
会产生空间内存溢出 ， 测试用例 824883294 // 划分数组数量过大，内存溢出。
参考代码
csharp
public class Solution {
public int CountDigitOne(int n) {
int sum = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i=2; i<=n; i++){
int latest = i % 10 == 1 ? 1 : 0; //计算个位数1的个数
dp[i] = latest + dp[ i / 10] ; // 个位数的+前面组成数字的1的个数
sum+=dp[i];
}
return sum;
}
}
思路3：官方，枚举
csharp
public class Solution {
public int CountDigitOne(int n) {
// mulk 表示 10^k
// 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
// 但为了让代码看起来更加直观，这里保留了 k
long mulk = 1;
int ans = 0;
for (int k = 0; n >= mulk; ++k) {
ans += (int) (n / (mulk * 10) * mulk) + (int) Math.Min(Math.Max(n % (mulk * 10) - mulk + 1, 0), mulk);
mulk *= 10;
}
return ans;
}
}