hiho一下第180周《Nature Numbers》题目分析

8
2

《Nature Numbers》题目分析

一个直观的解法是从1, 2, 3, ... 开始一个数一个数枚举。一开始count=0,保存位数之和。

假设当前枚举到K,我们就把count加上K的位数。如果这时count大于等于N,我们就知道第N位应为K的倒数第N-K+1位。

考虑到N=10^18时,K至少大于10^16,这个算法肯定会超时。

一种优化的思路是不要一个数一个数枚举,而是一批数一批数枚举:每次枚举所有的一位数、两位数、三位数……

一位数有10个(包括0),两位数有90个,三位数有900个……

假设当前枚举到K位数,我们就把count加上(K * K位数的个数)。如果这时count大于等于N,我们就知道第N位是一个K位数的某一位。

当然具体是第几个K位数的第几位,也可以计算出来。请大家自己算一算~

2 answer(s)

0

二分一下显得更简单暴力

0

只有80分,问题在哪里啊?大凶们....

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

    Scanner scanner = new Scanner(System.in);

    long N = scanner.nextLong();

    if (N < 10) {
        System.out.println(N);
    } else {
        long[] digit = new long[String.valueOf(N).length() + 1];

        int bit = 0;
        long n = 0;
        for (int i = 1; i < digit.length; i++) {
            digit[i] += (long) (9.0 * Math.pow(10, i - 1) * i + digit[i - 1]);

            if (digit[i] > N) {
                bit = i;
                n = N - digit[i - 1];
                break;
            }
        }

        if (n == 0) {
            // 前一个bit-1区间的最后一个数的最后一位
            System.out.println(9);
        } else {
            // bit位开始的第n个数
            // bit位的第一个数位a0 = pow(10, bit - 1)

            // 2 -> 10~99
            // a0 + ((n-1) / bit)的第k位
            long target = (long) (Math.pow(10, bit - 1) + (n - 1) / bit);
            System.out.println(String.valueOf(target).charAt((int) ((n - 1) % bit)) - '0');
        }
    }

    scanner.close();
}

}

write answer 切换为英文 切换为中文


转发分享