跟着姚桑学算法-数字序列中某一位的数字

简介: 剑指offer算法

题. 数字序列中某一位的数字

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中,第 5 位(从 0 开始计数)是 5,第 13 位是 1,第 19 位是 4,等等。

请写一个函数求任意位对应的数字。

数据范围
0≤ 输入数字 ≤2147483647

样例

输入:13

输出:1

【题解】--- 模拟

模拟一个实例,n = 1022,匹配到的数是377,对应它的第2位,也就是3后面的那个7,输出ans是7。

  1. 首先不断地对1022进行处理,也就是第1个while()循环做的事情,得到base = 100, i = 3, n = 833。那么得到的信息就是1022位数处于3位数的区间,那一位从100开始数,是第833位。
  2. 第二步,我们就可以通过100和3和833这三个信息推出1022位数字,具体落脚在了哪个3位数上。
  3. 我们来逆推下公式,比如377这个数,(377−100+1)∗3(377−100+1)∗3得到的就是100到377有多少位数字,结果是834。
  4. 我们上面求出的n是833,834指的是377最后一位的位数。所以为了求出377,我们通过(n + (i - 1)) / i,从而求出来它具体在第几位。然后得出在100后面的第278位,最后(278 + 100 - 1) = 377。
  5. 得到number后,我们通过 833 % i的结果,如果能除尽,就是number的最后一位,也就是i位;不然就是number中从第1位算起的第n % i位(下标从1开始哦)。
  6. 算出来r是2后,说明是377的第2位,也就是第1个7,我们让它除10,一次,除10的次数是[0 ~ i - r)
  7. 处理后的number的个位就是要求的答案,我们返回的时候number %10就ok。

复杂度分析:

1. 确定寻找的n处于几位数的范畴,1位数,2位数,还是3位数....这里的时度是O(1)。
2. 确定是i位数后,确定是i位数中的哪个,比如说4位数的第256个数,1000 + 256 - 1 = 1255,1255就是4位数的其中1个。
这里的时度是O(1),用到了除法。
3. 确定是哪个数以后(比如确定是1255这个数以后),看看数字n是这个数的第几位,拿1255来举例子,是1还是2还是5还是5。
这里是取余,时度是O(1)的,然后取出来是哪一位数,最多是10位,所以最多是10次操作,时间复杂度为O(log10n)。

C++代码实现:

class Solution {
public:
    int pow10(int x){
        int res=1;
        for(int i=0;i<x;i++){
            res*=10;
        }
        return res;
    }
    int digitAtIndex(int n) {
        if(n<10){
            return n;
        }

        int m=n-9;
        long long k=2;
        while(m>9*k*pow10(k-1)){
            m-=9*k*pow10(k-1);
            k++;
        }
        //t---第t个k位数
        int t=m/k;
        int s=m%k;
        int num=pow10(k-1);
        num+=t;
        if(s==0){
            return (num-1)%10;
        }
        else{
            for(int i=0;i<k-s;i++){
                num/=10;
            }
            return num%10;
        }
    }
};
目录
相关文章
|
9天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)
|
4月前
|
机器学习/深度学习 算法 数据挖掘
基于WOA鲸鱼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB 2022a/2024b实现,采用WOA优化的BiLSTM算法进行序列预测。核心代码包含完整中文注释与操作视频,展示从参数优化到模型训练、预测的全流程。BiLSTM通过前向与后向LSTM结合,有效捕捉序列前后文信息,解决传统RNN梯度消失问题。WOA优化超参数(如学习率、隐藏层神经元数),提升模型性能,避免局部最优解。附有运行效果图预览,最终输出预测值与实际值对比,RMSE评估精度。适合研究时序数据分析与深度学习优化的开发者参考。
|
4月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于GA遗传优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本内容包含基于BiLSTM与遗传算法(GA)的算法介绍及实现。算法通过MATLAB2022a/2024b运行,核心为优化BiLSTM超参数(如学习率、神经元数量),提升预测性能。LSTM解决传统RNN梯度问题,捕捉长期依赖;BiLSTM双向处理序列,融合前文后文信息,适合全局信息任务。附完整代码(含注释)、操作视频及无水印运行效果预览,适用于股票预测等场景,精度优于单向LSTM。
|
4月前
|
算法 数据安全/隐私保护
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
本项目实现了一种基于Logistic Map混沌序列的数字信息加解密算法,使用MATLAB2022A开发并包含GUI操作界面。支持对文字、灰度图像、彩色图像和语音信号进行加密与解密处理。核心程序通过调整Logistic Map的参数生成伪随机密钥序列,确保加密的安全性。混沌系统的不可预测性和对初值的敏感依赖性是该算法的核心优势。示例展示了彩色图像、灰度图像、语音信号及文字信息的加解密效果,运行结果清晰准确,且完整程序输出无水印。
基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
|
4月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。
|
4月前
|
算法 数据安全/隐私保护
基于混沌序列和小波变换层次化编码的遥感图像加密算法matlab仿真
本项目实现了一种基于小波变换层次化编码的遥感图像加密算法,并通过MATLAB2022A进行仿真测试。算法对遥感图像进行小波变换后,利用Logistic混沌映射分别对LL、LH、HL和HH子带加密,完成图像的置乱与扩散处理。核心程序展示了图像灰度化、加密及直方图分析过程,最终验证加密图像的相关性、熵和解密后图像质量等性能指标。通过实验结果(附图展示),证明了该算法在图像安全性与可恢复性方面的有效性。
|
4月前
|
机器学习/深度学习 数据采集 算法
基于GWO灰狼优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于Matlab 2022a/2024b实现,结合灰狼优化(GWO)算法与双向长短期记忆网络(BiLSTM),用于序列预测任务。核心代码包含数据预处理、种群初始化、适应度计算及参数优化等步骤,完整版附带中文注释与操作视频。BiLSTM通过前向与后向处理捕捉序列上下文信息,GWO优化其参数以提升预测性能。效果图展示训练过程与预测结果,适用于气象、交通等领域。LSTM结构含输入门、遗忘门与输出门,解决传统RNN梯度问题,而BiLSTM进一步增强上下文理解能力。
|
10月前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
342 80
|
7月前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于模糊神经网络的金融序列预测算法matlab仿真
本程序为基于模糊神经网络的金融序列预测算法MATLAB仿真,适用于非线性、不确定性金融数据预测。通过MAD、RSI、KD等指标实现序列预测与收益分析,运行环境为MATLAB2022A,完整程序无水印。算法结合模糊逻辑与神经网络技术,包含输入层、模糊化层、规则层等结构,可有效处理金融市场中的复杂关系,助力投资者制定交易策略。
|
10月前
|
机器学习/深度学习 算法
基于遗传优化的双BP神经网络金融序列预测算法matlab仿真
本项目基于遗传优化的双BP神经网络实现金融序列预测,使用MATLAB2022A进行仿真。算法通过两个初始学习率不同的BP神经网络(e1, e2)协同工作,结合遗传算法优化,提高预测精度。实验展示了三个算法的误差对比结果,验证了该方法的有效性。
112 10

热门文章

最新文章