网站或站点的第一个网页,摄影大赛官网,昆明专业网站设计公司,linux wordpress 中文字体关键词#xff1a;找规律 数学
题目#xff1a;LCR 163. 找到第 k 位数字
虽然做出来了但是做了十万年#xff0c;我是猪。主要还是找到准确的规律。 思路#xff1a; //找规律 //0-9 占了10个位置 //10-99 占了90*2个位置 //100-999 占了900*3个位置 //1000-9999 占了90…关键词找规律 数学
题目LCR 163. 找到第 k 位数字
虽然做出来了但是做了十万年我是猪。主要还是找到准确的规律。 思路 //找规律 //0-9 占了10个位置 //10-99 占了90*2个位置 //100-999 占了900*3个位置 //1000-9999 占了9000*4个位置
总体求解顺序 1、 确定要求的数字的位数 2、再确定数字 3、再确定要求的数字的第b位
比如
k479 1、 确定要求的数字的位数 479-10-90*22890 说明大于99 479-10-90*2-900*3-24110 说明小于999 可以确定要求的数y是i2位数y在100-999区间内这个区间的每个数都得占3个字符。 并且说明y里我们要求的res排在100-999这个区间里的第289个字符。 long long xk;//注意这里不能用int 会爆long long rex 1;//10 100 1000int i 1;//存位数while (x 0)//确定位数:一点一点减减到合适的位置 xx-9*10^(i-1)*i{rex * 10;i;x x - (rex*9) * i;//479-10-90*2-900*3-2411}x x (rex * 9) * i;//479-10-90*2289 2、再确定数字是几 在100-999这个区间内每个数都得占3个字符。 ax/ia289/296y排在100-999这个区间里的第96个数字。 为什么/i因为这个区间一个数字由i个字符组成 得到a和i现在我们已经可以确定y了a加上这个区间的最小数rex100 即yrexa10096196
long long a x / i;//ax/ia289/296y排在100-999这个区间里的第96个数字//为什么/i因为这个区间一个数字由i个字符组成
long long res rex a;//现在我们已经可以确定y了a加上这个区间的最小数rex100 即yrexa10096196 3、再确定要求的数字的第b位 确定我们要求的数字在y里的位置b x % i1。 //因为求的是从左往右数的第b位而不是我们习惯的从右往左数所以要除的10的个数是i-b-2 //比如1234b是2那么得除两次10即i-b-24-2-11 j1 除了两次10 最后求模得到个位数就是我们需要的。 long long b x % i;//还需要确定我们要求的数字在y里的位置b x % i1//因为求的是从左往右数的第b位而不是我们习惯的从右往左数所以要除的10的个数是i-b-2//比如1234b是2那么得除两次10即i-b-24-2-11 j1 除了两次10for(int j0;ji-b-2;j){resres/10;}resres%10;//求模
复杂度计算
时间复杂度O(logk) 确定位数
空间复杂度O(1) 只用了常数个空间没有开辟新的空间存别的
代码
class Solution {
public://找规律//0-9 占了10个位置//10-99 占了90*2个位置//100-999 占了900*3个位置//1000-9999 占了9000*4个位置//可以先确定要求的数字的位数再确定数字再确定要求的数字的第b位//比如k479//479-10-90*22890 479-10-90*2-900*3-24110 可以确定要求的数y是i2位数//说明y里我们要求的res排在100-999这个区间里的第289个字符//ax/ia289/296y排在100-999这个区间里的第96个数字//为什么/i因为这个区间一个数字由i个字符组成//现在我们已经可以确定y了a加上这个区间的最小数rex100 即yrexa10096196//还需要确定我们要求的数字在y里的位置b x % i1//因为求的是从左往右数的第b位而不是我们习惯的从右往左数所以要除的10的个数是i-b-2//比如1234b是2那么得除两次10即i-b-24-2-11 j1 除了两次10//最后求模就可以啦int findKthNumber(int k) {if (k 10) return k;k k - 10;long long xk;//注意这里不能用int 会爆long long rex 1;//10 100 1000int i 1;//存位数while (x 0)//确定位数:一点一点减减到合适的位置 xx-9*10^(i-1)*i{rex * 10;i;x x - (rex*9) * i;//479-10-90*2-900*3-2411}x x (rex * 9) * i;//479-10-90*2289long long a x / i;//ax/ia289/296y排在100-999这个区间里的第96个数字//为什么/i因为这个区间一个数字由i个字符组成long long b x % i;//还需要确定我们要求的数字在y里的位置b x % i1long long res rex a;//现在我们已经可以确定y了a加上这个区间的最小数rex100 即yrexa10096196//因为求的是从左往右数的第b位而不是我们习惯的从右往左数所以要除的10的个数是i-b-2//比如1234b是2那么得除两次10即i-b-24-2-11 j1 除了两次10for(int j0;ji-b-2;j){resres/10;}resres%10;//求模return res;}
};
