NthDigit [source code]
public class NthDigit {
static
/******************************************************************************/
public class Solution {
public int findNthDigit(int n) {
if (n <= 9) return n;
int[] found = getLength(n);
int d = found[0], curSum = found[1];
int num = curSum / d;
int start = (int) Math.pow(10, d - 1);
if (curSum % d == 0) {
int end = start + num - 1;
return end % 10;
} else {
int end = start + num;
return getDigit(end, d, curSum % d);
}
}
public int[] getLength(int n) {
int[] res = new int[2];
long sum = 9;
int i = 2;
for (; sum < n; i++) {
sum += (Math.pow(10, i) - Math.pow(10, i - 1)) * i;
}
res[0] = i - 1;
int d = res[0];
res[1] = (int) (n - (sum - (int) (Math.pow(10, d) - Math.pow(10, d - 1)) * d));
return res;
}
public int getDigit(int value, int d, int pos) {
int index = d - pos;
while (index > 0) {
value = value / 10;
index--;
}
return value % 10;
}
}
/******************************************************************************/
public static void main(String[] args) {
NthDigit.Solution tester = new NthDigit.Solution();
int[] inputs = {
3, //3
180, //9
192, //0
500, //0
1000, //3
99999999, //8
199999999, //8
1000000000, //1
};
for (int i : inputs) {
System.out.println(Printer.seperator());
Printer.openColor("red");
System.out.print(i + " -> ");
Printer.closeColor();
System.out.println(tester.findNthDigit(i));
}
}
}
写循环分不清是 i 还是i-1的时候, 直接用例子来做, 比如就考虑 n 是189或者190的情况, 给最后的 i 一个具体的数值;
这个算法总体来说还是对的, 不过有点过于复杂. 不过这种 math 的题目, 如果现场就是不知道数学上的解法, 那么这种搜索的程序你还是要写的出来的, 总比发呆要强;
这个程序的逻辑其实很简单, 就是给 n 分段, 然后处理; 不过最后真正让你写出来这个程序, 也并不是那么轻松就写的出来的, 尤其是很多变量的 edge 的处理, 很费神. 现场如果要让你写这样的程序, 最好就是手边上始终有一个例子, 比如我写的时候就是用180, 189, 190这三个例子, 然后配合这三个例子模拟我的操作, 然后考虑应该设置到多少;
不过这个算法最后并没有AC, 被一个十位的 case 给溢出了;
//看 discussion 的时候受到启发, 你他妈不要看到溢出就直接放弃啊, 虽然有这个 case 故意用溢出来 break 你, 不代表这个溢出就无法修复! 这里的溢出就是因为getInterval里面的累加和造成的(这个你当时应该想到的! 当时做这个累加和的时候应该就要想到很可能会溢出(加, 乘, 想到溢出已经是本能), 更何况你会发现每个 i 对应的加项的增加速度非常的快), 只要把这个buffer sum 给做成 long 就行了(其他的, 尤其是主函数里面的, 都没有必要做成 long). 果然就过了, 最后的速度是6ms (38%), 不是不能接受;
按照 discussion 上面的总结, 这一题大体上的思路好像都差不多, 所以这个题目就是一个考你变量搜索和更新的硬基础的题目. discussion 上面的总结:
Straight forward way to solve the problem in 3 steps:
- find the length of the number where the nth digit is from
- find the actual number where the nth digit is from
- find the nth digit and return
这个总结的思路是比较清晰的, 不过这个作者最后的代码比我的简洁的多;
public int findNthDigit(int n) {
int len = 1;
long count = 9;
int start = 1;
while (n > len * count) {
n -= len * count;
len += 1;
count *= 10;
start *= 10;
}
start += (n - 1) / len;
String s = Integer.toString(start);
return Character.getNumericValue(s.charAt((n - 1) % len));
}
这个代码可以说是精炼到可怕了; 而且他这里还有一个技巧就是他没有用加法! 他直接转换成为了一个减法思路! 这个为什么我没有想到呢? 加法和减法本来就是反过来就行了, 尤其是这里最后的和是直接就 known 的. 这个人的脑子真的很灵光. 而且他的代码的整体思路也非常的清晰: 确定了想要找到什么东西之后, 一个循环直接跑到找到为止. 我这个感觉就是有一点overkill 了, 比如我一个功能写一个函数, 虽然说符合single responsibility了, 但是这个也带来了一个问题, 就是代码行数增加的很多(函数本身的头和尾, 然后你每一个函数本身还要重新设置好几个 temp var).
他还有一点值得我借鉴的地方就是, 他这里len, count, start分别用三个变量来维护, 这让最后的代码实际上简化了很多, 而我一个很直观的想法就是, 这三个值其实背后就是一个值(digit number, or len), 所以我就想很简化的一个变量来表达, 需要的时候再计算, 结果这样最后代码的复杂程度增加的很多;
他的 header 的写法也很聪明. 我的写法最后还要判断是否回头, 他这个就不需要: 有的减, 就继续减. Verbal Logic的角度就是这么简单; 而且用这个逻辑来理解, 等号的情况也完全没有处理的难度;
最后他这个转换成 string 然后直接取 digit 的做法其实我是想到了的, 不过后面觉得有点 low, 就没有用了, 也不知道是哪里来的骄傲的资本;
这个版本直接把乘法也去掉了:
public int findNthDigit(int n) {
n -= 1;
int digits = 1, first = 1;
while (n / 9 / first / digits >= 1) {
n -= 9 * first * digits;
digits++;
first *= 10;
}
return (first + n/digits + "").charAt(n%digits) - '0';
}
这样他就彻底没有用 long 了;
Problem Description
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 < 2^31).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
0
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.
Difficulty:Easy
Total Accepted:23.2K
Total Submissions:76.8K
Contributor: LeetCode
Companies
google
Related Topics
math