第三十八题 简单？？暴力确实简单，但是复杂度超了啊！！！
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
// 第一种 暴力，拼接出一个超级无敌长的字符串，访问第n位。显然复杂度不对
// 第二种 相对暴力稍微优化，超级无敌长的字符串不用拼接出来，只需要每次将数字的长度累加求和，知道求得合超过了n，说明找到了数字，复杂度还是大
// 第三种如下，先找n所在的数字的位数长度，再去找所在的数字，最后返回指定的字符
int findNthDigit(int n) {
// write code here
// 先确定结果是几位数
// 不然从头开始找，复杂度超了
int weishu = 1;
long long start = 1, count = 9;
// 每多一位数 总共有的数字序列长度是：位数*总共有几个数（位数*9*10^（位数-1））
// 比如说 4位数，1000-9999 那就是4*9*1000
// count 就是当前计算位数 所含有的数字 循环结束条件就是count比n大 也就是说 n不需要count所在的那么长的位数
while(n > count) {
n -= count;
weishu += 1;
start *= 10;
count = start * weishu * 9;
}
// 知道了总共多少位
// cout<< weishu<endl;
// 下面是数学规律，找到所在的数字 和确定要返回的结果是哪一位
// 带图的解释可以看leetcode的第一个题解
// https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/
// 他没说清楚的一些补充 为什么除以位数？因为位数决定了是几个几个一组的
// n是当前位数所有数字排开来后所要找的数字
// 因为我前面算位数的时候，n是减掉了不要的低位数部分
// （也就是说当位数到了8，前面的7位数所有的数字的序列个数已经在n中减掉了。）
// （现在n是几，就代表我要在位数8的数字开始10000000,...向后找第n位）
// 用他图上的例子来解释：
// 现在位数是2，所以前面0-9有10个数字，n已经减掉了(前面n=n-10)
// 那么当我看到此时n=8的时候，就带表我要找从10，11,12,13开始的第八个数字也就是3
// 因为数字下标从0开始所以减了个0
// 然后解释为什么要除以位数
// 刚才说到 我要找第8-1个数，那我怎么确定这是10开始往后的哪一个数字呢？
// 就是利用/weishu来确定的。位数表示当前这个数有几位数字，像这里位数是2，就表示每个数有两位数字
// 所以当我要找第8-1个数字的时候，除以位数，就得到了他在第几个数字（8-1）/2 = 3，说明是第三个数字
// start是当前这个位数开始的数字（当位数是2的时候就是10）
// 最后得到 我要的数字是 当前开始的10后面第3个数就是13
// 再比说现在n是5，就是要找第5个数 第5个数在哪里？每个数两位所以5/2，得到是第二个数
// 最后得到 我要的数字是 当前开始的10后面第2个数就是12
// 换一个长一点的数字再给你举个例子
// 100 101 102 103 104 105 106 107 108 109
// 假设两位数都不能满足，现在到了三位数
// 此时n假设说是 11（要100开始，向后数第11个数字）
// 第一步 11-1=10 （因为下标从0开始算）
// 第二步 我要找的10/3=3 （除3是因为 每个数字有三位）也就是说 要找第三个数字
// 第三步 那我就知道了所要的数字是 从三位数的开始100开始向后第三个 103
// 100101102103 （自己数一下第10个数是不是在103）
int num=start +(n-1)/weishu;
// 知道数字后，确定具体在数字的哪一位，先转换成字符的格式，才能找位数
// 看上面10/3=3 是不是想到些什么？
// （11-1）/3=3....1
// 就说明是第三个数的1这个位置
// 103 （从0下标开始算 012,1的位置的数字是"0"）
// 100101102103 （再自己数一下第11个数字是不是103中的0）（或者说从0开始数，下标是10的时候是不是103的0）
// ok 得到数字了以后因为返回的是string[x] 变成了char（也就是这个复杂的原因上一题用的python写的）
// 那要吧char的数字变回去，在减去char '0' 的值就得想要的数字了
string str=to_string(num);
int ans = str[(n-1) % weishu ] - '0';
return ans;
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
// 第一种 暴力，拼接出一个超级无敌长的字符串，访问第n位。显然复杂度不对
// 第二种 相对暴力稍微优化，超级无敌长的字符串不用拼接出来，只需要每次将数字的长度累加求和，知道求得合超过了n，说明找到了数字，复杂度还是大
// 第三种如下，先找n所在的数字的位数长度，再去找所在的数字，最后返回指定的字符
int findNthDigit(int n) {
// write code here
// 先确定结果是几位数
// 不然从头开始找，复杂度超了
int weishu = 1;
long long start = 1, count = 9;
// 每多一位数 总共有的数字序列长度是：位数*总共有几个数（位数*9*10^（位数-1））
// 比如说 4位数，1000-9999 那就是4*9*1000
// count 就是当前计算位数 所含有的数字 循环结束条件就是count比n大 也就是说 n不需要count所在的那么长的位数
while(n > count) {
n -= count;
weishu += 1;
start *= 10;
count = start * weishu * 9;
}
// 知道了总共多少位
// cout<< weishu<endl;
// 下面是数学规律，找到所在的数字 和确定要返回的结果是哪一位
// 带图的解释可以看leetcode的第一个题解
// https://leetcode-cn.com/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/solution/mian-shi-ti-44-shu-zi-xu-lie-zhong-mou-yi-wei-de-6/
// 他没说清楚的一些补充 为什么除以位数？因为位数决定了是几个几个一组的
// n是当前位数所有数字排开来后所要找的数字
// 因为我前面算位数的时候，n是减掉了不要的低位数部分
// （也就是说当位数到了8，前面的7位数所有的数字的序列个数已经在n中减掉了。）
// （现在n是几，就代表我要在位数8的数字开始10000000,...向后找第n位）
// 用他图上的例子来解释：
// 现在位数是2，所以前面0-9有10个数字，n已经减掉了(前面n=n-10)
// 那么当我看到此时n=8的时候，就带表我要找从10，11,12,13开始的第八个数字也就是3
// 因为数字下标从0开始所以减了个0
// 然后解释为什么要除以位数
// 刚才说到 我要找第8-1个数，那我怎么确定这是10开始往后的哪一个数字呢？
// 就是利用/weishu来确定的。位数表示当前这个数有几位数字，像这里位数是2，就表示每个数有两位数字
// 所以当我要找第8-1个数字的时候，除以位数，就得到了他在第几个数字（8-1）/2 = 3，说明是第三个数字
// start是当前这个位数开始的数字（当位数是2的时候就是10）
// 最后得到 我要的数字是 当前开始的10后面第3个数就是13
// 再比说现在n是5，就是要找第5个数 第5个数在哪里？每个数两位所以5/2，得到是第二个数
// 最后得到 我要的数字是 当前开始的10后面第2个数就是12
// 换一个长一点的数字再给你举个例子
// 100 101 102 103 104 105 106 107 108 109
// 假设两位数都不能满足，现在到了三位数
// 此时n假设说是 11（要100开始，向后数第11个数字）
// 第一步 11-1=10 （因为下标从0开始算）
// 第二步 我要找的10/3=3 （除3是因为 每个数字有三位）也就是说 要找第三个数字
// 第三步 那我就知道了所要的数字是 从三位数的开始100开始向后第三个 103
// 100101102103 （自己数一下第10个数是不是在103）
int num=start +(n-1)/weishu;
// 知道数字后，确定具体在数字的哪一位，先转换成字符的格式，才能找位数
// 看上面10/3=3 是不是想到些什么？
// （11-1）/3=3....1
// 就说明是第三个数的1这个位置
// 103 （从0下标开始算 012,1的位置的数字是"0"）
// 100101102103 （再自己数一下第11个数字是不是103中的0）（或者说从0开始数，下标是10的时候是不是103的0）
// ok 得到数字了以后因为返回的是string[x] 变成了char（也就是这个复杂的原因上一题用的python写的）
// 那要吧char的数字变回去，在减去char '0' 的值就得想要的数字了
string str=to_string(num);
int ans = str[(n-1) % weishu ] - '0';
return ans;
}
};
暴力用python简单写一下 数字变字符串再全拼起来 最后返回指定位置
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def findNthDigit(self , n: int) -> int:
string_ans=""
# write code here
for i in range(n+1):
string_ans += str(i)
print(string_ans)
# return 1
return int(string_ans[n])
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param n int整型
# @return int整型
#
class Solution:
def findNthDigit(self , n: int) -> int:
string_ans=""
# write code here
for i in range(n+1):
string_ans += str(i)
print(string_ans)
# return 1
return int(string_ans[n])
京公网安备 11010502036488号