題目

400. 第 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 的一部分。

• 提示：
  節(jié)點總數 <= 10000

解法

1. 由題目可知，一位數占用一位，兩位數占用倆位，以此類推，我們需要得知 n 是在幾位數上的，所以用 n 減去前面位數占用的位數的總和（一位數1-9共9位，二位數10-99共90×2=180位…）
2. 確定數字所在位數之后，確定 n 所在的實際數字究竟是哪個
3. 確定實際位數后，最后一步是確定所找數字在實際數字的第幾位

class Solution {
public:int findNthDigit(int n) {int numDigits = 1; // 初始化數字位數long long int numCount = 9; // 當前數字位數所包含的數字個數// 確定給定數字所在的位數while (n - numCount * numDigits > 0) {n -= numCount * numDigits;numDigits++;numCount *= 10;}// 確定實際數字int num = pow(10, numDigits - 1) + (n - 1) / numDigits;// 確定所找數字的位數int digitIndex = (n - 1) % numDigits;// 將數字轉換為字符串并獲取指定位上的數字std::string numStr = std::to_string(num);return numStr[digitIndex] - '0';}
};