1到n中1的出现次数

https://blog.csdn.net/yi_Afly/article/details/52012593?depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1 这篇博客讲的很清楚，然后要注意10的13次超出了int的表示范围

import java.util.Scanner;

/*
 *
 * https://www.nowcoder.com/practice/38af9b5a06ea4448ae9b2a488b6a991f?tpId=101&&tqId=33140&rp=1&ru=/activity/oj&qru=/ta/programmer-code-interview-guide/question-ranking
 *
 * */
public class Main {
    public static long count(long n) {
        if (n < 1) {
            return 0;
        }
        long count = 0;
        long round = n;
        long weight = 0;
        long base = 1;
        while (round > 0) {
            weight = round % 10;
            round = round / 10;
            count += round * base;
            if (weight == 1) {
                count += n % base + 1;
            } else if (weight > 1) {
                count += base;
            }
            base *=10;
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        System.out.println(count(n));
    }
}

#include<iostream>
#include<algorithm>
using  namespace  std;
int main(){
    long long N;
    while(cin>>N){
        long long base=10;
        long long mul=1;
        long long count=0;
        do{
            count+=(N/base)*mul;
            if(N%base+1-1*mul>=0)
                count+=min(N%base+1-1*mul,mul);
            mul*=10;
            base*=10;
        }while(N*10>=base);
        cout<<count<<endl;
    }
    return 0;
}

思路：分别统计k出现在个位，十位，百位，千位...的个数。
并给出一个通用解法：

1-n中，出现数字k的次数是多少。

left记录对于当前位的高位
right记录对于当前位的低位

当前位还用分:k三种情况讨论
参考：https://blog.csdn.net/qq_25024883/article/details/80337312

n = 2593, x = 5 为例来解释如何得到数学公式。从 1 至 2593中，数字 5 总计出现了 813 次，其中有 259次出现在个位，260次出现在十位，294次出现在百位，0次出现在千位。

• 现在依次分析这些数据，首先是个位。从 1 至 2590 中，包含了 259 个 10，因此任意的 x 都出现了 259 次。最后剩余的三个数 2531,2592,2593，因为它们最大的个位数字 3 < x。因此不会包含任何 5. (也可以这么看， 3 < x， 则个位上可能出现的 x 的位数由更高位决定，等于更高位数字 (259) * 101-1 = 259)。
• 然后是十位。从 1 至 2500中，包含了25个100，因此任意的 x 都出现了 25 * 10 = 250 次。剩下的数字从 2501 至 2593，它们最大的十位数是 9 > x，因此会包含全部 10 个 5。最后总计 250 + 10 = 260。(也可以这么看，9 > x，则十位上可能出现的 x 的位数由更高位决定，等于更高位数字(25 + 1) * 102-1 = 260。
• 接下来是百位。从1至2000中，包含了2个1000，因此任意x都出现了2 * 100 = 200次。剩下的数字从2001至2593，它们最大的百位数字5 == x，这时候情况就略微复杂，它们的百位肯定是包含5的，但是不会包含全部100个。如果把百位是5的列出来，是从2500至2593，数字的个数与十位和个位数字有关，是93 + 1 = 94。最后总计 200 + 94 = 294。(也可以这么看， 5 == x，则百位上可能出现的x次数不仅受跟高位影响，还受低位影响，等于更高位数字 2 * 103-1 + (93 + 1))。
• 最后是千位，现在已经没有更高位，因此直接看最大的千位数字 2 < x，因此不会包含任何 5 。(也可以这么看，2 < x，则千位上可能出现的x的次数仅由更高位决定，等于更高位数字 0 * 104-1 = 0)

n = int(input())
k = 1
l = []
res = 0
tmp = 1
while tmp < n:
    left = n // (tmp * 10)
    right = tmp
    res += left * right
    if n % (tmp * 10) // tmp > k:
        res += right
    if n % (tmp * 10) // tmp == k:
        res += n % tmp + 1
    tmp *= 10
print(res)