哪个网站可以做前端项目,预约网站制作,沭阳县城乡建设局网站,久商推网站建设题目描述#xff1a;
给你一个整数 n #xff0c;请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1#xff1a;
输入#xff1a;n 3
输出#xff1a;3示例 2#xff1a;
输入#xff1a;n 11
输出#xff1…题目描述
给你一个整数 n 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1
输入n 3
输出3示例 2
输入n 11
输出0
解释第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 它是 10 的一部分。提示
1 n 231 - 1 解法
class Solution {public int findNthDigit(int n) {if(n 10) return n;long num (long)n;long sum 0;long posNum 0;long pos 0;for (long i 1; i num; i) {sum i * 9 * Math.pow(10, i - 1);if (sum num) {sum - i * 9 * Math.pow(10, i - 1);posNum i * 9 * (long) (Math.pow(10, i - 1));pos i;break;}}int targerNum -1;for (long i 0; i posNum; i) {if (sum num) {long target (long) (Math.pow(10, pos - 1)) (i - 1);long offset Math.abs(sum - pos - num);targerNum Long.toString(target).charAt((int)offset - 1) - 0;break;}sum pos;}return targerNum;}
}
思路
1.个位数直接返回
2.1位数的总个数为1*9
两位数的总位数为 2 * 90 (两位数占两个位,数量为90个)
三位数总位数为3*900((三位数占三个位,数量为900个))
四位数的总位数为3*9000((四位数占四个位,数量为9000个))
依次类推N位数的总位数为 N * 9 * 10 ^(N-1)
于是有了
sum i * 9 * Math.pow(10, i - 1);
前面所有位数的总和。
于是我们需要得到一个值那就是多少位之和大于等于(大于是因为目标值可能在某一个数的某一个位这个位我们称之为偏移值)我们目标值 for (long i 1; i num; i) {sum i * 9 * Math.pow(10, i - 1);if (sum num) {sum - i * 9 * Math.pow(10, i - 1);posNum i * 9 * (long) (Math.pow(10, i - 1));pos i;break;}}
这一段代码就是找到大于目标值的总位数之和其中sum是前面位数累计和posNum是未超过目标值的计算起始值比如目标值在7位数和8位数和的中间于是我们先计算出前面所有7位数之和然后新的计算值从10^8开始而这里得到的值就是当前需要统计的位数。 int targerNum -1;for (long i 0; i posNum; i) {if (sum num) {long target (long) (Math.pow(10, pos - 1)) (i - 1);long offset Math.abs(sum - pos - num);targerNum Long.toString(target).charAt((int)offset - 1) - 0;break;}sum pos;}return targerNum;
然后从10^N开始遍历每次偏移量就是N次方得到超过目标值的领界值,然后通过累计值减去目标值得到偏移量,
偏移的目标值是N次方的起始值遍历次数
这个值转化成字符串通过偏移量得到字符串中的字符然后转化成数字即可
Long.toString(target).charAt((int)offset - 1) - 0;
这里charAt是从0开始所以需要把我们计算出来的偏移量减去1
