LeetCode Nth Digit

LeetCode Nth Digit Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … Note: n is positive and will fit within the range of a 32-bit signed integer (n < 231). Example 1:

Input:
3
Output:
3
Example 2:
Input:
11
Output:
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

自然数的连续序列中,第n个数字是什么。 简单的数学题,没有捷径,直接统计吧。
  • 1~9:宽度为1,数字个数1*9
  • 10~99:宽度为2,数字个数2*90
  • 100~999:宽度为3,数字个数3*900
首先不断累加1*9+2*90+3*900+…+k*9*pow(10,k-1)直到和大于n时停止,此时能定位到第n个数字所在的数的宽度width以及该宽度的第一个数start。然后计算在该宽度范围内,偏移了几个数字leftdigit=n-{1*9+2*90+…+(k-1)*9*pow(10,k-2)}。根据leftdigit和width又能定位到原始第n个数字所在的数target以及第n个数字在target中的第几个位置pos。最后把target转换为string取出第pos位数字即可。 代码如下,注意要把代码中的变量都定义为long long,否则大数可能溢出。 [cpp] class Solution { public: int findNthDigit(int n) { long long width = 1, start = 1, num = 9; while (n > num) { ++width; start *= 10; num += width * 9 * start; } long long leftdigit = n – (num – width * 9 * start); long long offset = leftdigit / width + ((leftdigit%width == 0) ? 0 : 1); long long target = start + offset – 1, pos = leftdigit%width; if (pos == 0)pos = width; string s = to_string(target); char c = s[pos – 1]; return atoi(&c); } }; [/cpp] 本代码提交AC,用时3MS。 最后定位到target之后,不转换成string,直接用除法和取模运算也能得到第pos位数字,代码如下: [cpp] class Solution { public: int findNthDigit(int n) { long long width = 1, start = 1, num = 9; while (n > num) { ++width; start *= 10; num += width * 9 * start; } long long leftdigit = n – (num – width * 9 * start); long long offset = leftdigit / width + ((leftdigit%width == 0) ? 0 : 1); long long target = start + offset – 1, pos = leftdigit%width; if (pos == 0)pos = width; int cnt = 0, ans; while (cnt < pos) { ans = target / start; target -= ans*start; start /= 10; ++cnt; } return ans; } }; [/cpp] 本代码提交AC,用时6MS。]]>

Leave a Reply

Your email address will not be published. Required fields are marked *