第 N 位数字
给你一个整数 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 < = 2 31 − 1 1 <= n <= 2^{31} - 1 1<=n<=231−1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution { public: int findNthDigit(int n) { int weishu = 1, sum = 1; while (n > (long long)9 * weishu * sum){ n -= 9 * weishu * sum; weishu++; sum *= 10; } int cnt = (n - 1) / weishu + sum; int ans = 0; for (int i = (n - 1) % weishu; i < weishu;i++){ ans = cnt % 10; cnt /= 10; } return ans; } };
思路:
n=11，其实是1234567891011…字符串第11个，就是0
已知 x x x 位数共有 9 × 1 0 x − 1 9 times 10^{x - 1} 9×10x−1个，所有 x x x 位数的位数之和是 x × 9 × 1 0 x − 1 x times 9 times 10^{x - 1} x×9×10x−1
使用 weishu 和 sum 分别表示 当前遍历到的位数 和 当前位的权重(
1
0
i
10^i
10i)，cnt是含有所找数字的那个数， 整个数列的第一个数是1，从低位向高位移动扫描，根据离末位的偏移量找到所找的数字。
最后
以上就是细心黑裤最近收集整理的关于2021-11-30【LeetCode】【第 N 位数字】【每日一题】的全部内容，更多相关2021-11-30【LeetCode】【第内容请搜索靠谱客的其他文章。
![【LeetCode】数字 1 的个数 [H]（动态规划）一、题目二、代码三、解题思路](/uploads/reation/bcimg9.png)
发表评论 取消回复