【C++数论】880. 索引处的解码字符串|2010
本文涉及知识点
数论:质数、最大公约数、菲蜀定理
LeetCode880. 索引处的解码字符串
给定一个编码字符串 s 。请你找出 解码字符串 并将其写入磁带。解码时,从编码字符串中 每次读取一个字符 ,并采取以下步骤:
如果所读的字符是字母,则将该字母写在磁带上。
如果所读的字符是数字(例如 d),则整个当前磁带总共会被重复写 d-1 次。
现在,对于给定的编码字符串 s 和索引 k,查找并返回解码字符串中的第 k 个字母。
示例 1:
输入:s = “leet2code3”, k = 10
输出:“o”
解释:
解码后的字符串为 “leetleetcodeleetleetcodeleetleetcode”。
字符串中的第 10 个字母是 “o”。
示例 2:
输入:s = “ha22”, k = 5
输出:“h”
解释:
解码后的字符串为 “hahahaha”。第 5 个字母是 “h”。
示例 3:
输入:s = “a2345678999999999999999”, k = 1
输出:“a”
解释:
解码后的字符串为 “a” 重复 8301530446056247680 次。第 1 个字母是 “a”。
提示:
2 <= s.length <= 100
s 只包含小写字母与数字 2 到 9 。
s 以字母开头。
1 <= k <= 109
题目保证 k 小于或等于解码字符串的长度。
解码后的字符串保证少于 263 个字母。
数论
str记录所有字符串,int数组d记录所有数字。比如:ab3e1,则str = {“ab”,“e”},d = {3,1}。
long long数组len[i]记录各操作后的字符串的长度。
len[0]=0
{ l e n [ 2 i + 1 ] = l e n [ 2 i ] + s t r [ i ] . l e n g t h 奇数 l e n [ 2 i + 2 ] = l e n [ 2 i + 1 ] ∗ d [ i ] 偶数 \begin{cases} len[2i+1] = len[2i] + str[i].length && 奇数\\ len[2i+2] = len[2i+1]*d[i] && 偶数\\ \end{cases} {len[2i+1]=len[2i]+str[i].lengthlen[2i+2]=len[2i+1]∗d[i]奇数偶数
f(x)函数的定义:
len[i1] > x ,且i1最小
如果i1是奇数,return str[i1/2][x-len[i1-1]]。
如果i1是偶数:return f(x % len[i1-1])。
最终调用:f(k-1)。
代码
核心代码
class Solution {public:string decodeAtIndex(string s, int k) {const int N = s.length();vector<string> strs;vector<int> d;for (int i = 0; i < N;) {string str;while ((i < N) && isalpha(s[i])) {str += s[i]; i++;}strs.emplace_back(str);if ((i < N) && isdigit(s[i])) {d.emplace_back(s[i] - '0'); i++;}}if (d.size() < strs.size()) {d.emplace_back(1);}vector<long long> lens = { 0 };for (int i = 0; i < strs.size(); i++) {lens.emplace_back(lens.back() + strs[i].length());lens.emplace_back(lens.back() * d[i]);}function<char(int)> f = [&](long long x) {int i1 = upper_bound(lens.begin(), lens.end(), x)-lens.begin();if (i1 & 1) {return strs[i1 / 2][x - lens[i1 - 1]];}return f(x % lens[i1 - 1]);};return string(1,f(k - 1));}};
单元测试
string s;int k;TEST_METHOD(TestMethod1){s = "a1", k = 1;auto res = Solution().decodeAtIndex(s, k);AssertEx(string("a"), res);}TEST_METHOD(TestMethod2){s = "abc", k = 1;auto res = Solution().decodeAtIndex(s, k);AssertEx(string("a"), res);}TEST_METHOD(TestMethod11){s = "leet2code3", k = 10;auto res = Solution().decodeAtIndex(s,k);AssertEx(string("o"), res);}TEST_METHOD(TestMethod12){s = "ha22", k = 5;auto res = Solution().decodeAtIndex(s, k);AssertEx(string("h"), res);}TEST_METHOD(TestMethod13){s = "a2345678999999999999999", k = 1;auto res = Solution().decodeAtIndex(s, k);AssertEx(string("a"), res);}

扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
| 学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
| 有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
| 子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙,那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

相关文章:
【C++数论】880. 索引处的解码字符串|2010
本文涉及知识点 数论:质数、最大公约数、菲蜀定理 LeetCode880. 索引处的解码字符串 给定一个编码字符串 s 。请你找出 解码字符串 并将其写入磁带。解码时,从编码字符串中 每次读取一个字符 ,并采取以下步骤: 如果所读的字符是…...
C++/stack_queue
目录 1.stack 1.1stack的介绍 1.2stack的使用 练习题: 1.3stack的模拟实现 2.queue的介绍和使用 2.1queue的介绍 2.2queue的使用 2.3queue的模拟实现 3.priority_queue的介绍和使用 3.1priority_queue的介绍 3.2priority_queue的使用 欢迎 1.stack 1.1stack…...
浅谈APP之历史股票通过echarts绘图
浅谈APP之历史股票通过echarts绘图 需求描述 今天我们需要做一个简单的历史股票收盘价格通过echarts进行绘图,效果如下: 业务实现 代码框架 代码框架如下: . 依赖包下载 我们通过网站下载自己需要的涉及的图标,勾选之后进…...
Ubuntu 20.04 x64下 编译安装ffmpeg
试验的ffmpeg版本 4.1.3 本文使用的config命令 ./configure --prefixhost --enable-shared --disable-static --disable-doc --enable-postproc --enable-gpl --enable-swscale --enable-nonfree --enable-libfdk-aac --enable-decoderh264 --enable-libx265 --enable-libx…...
【橘子Kibana】Kibana的分析能力Analytics简易分析
一、kibana是啥,能干嘛 我们经常会用es来实现一些关于检索,关于分析的业务。但是es本身并没有UI,我们只能通过调用api来完成一些能力。而kibana就是他的一个外置UI,你完全可以这么理解。 当我们进入kibana的主页的时候你可以看到这样的布局。…...
【STM32】-TTP223B触摸开关
前言 本文章旨在记录博主STM32的学习经验,我自身也在不断的学习当中,如果文章有写的不对的地方,欢迎各位大佬批评指正。 准备工作 今天这篇文章介绍的是触摸开关这一外围硬件。 ST-link调试器STM32最小系统板单路TTP223B触摸传感器模块LE…...
三星手机人脸识别解锁需要点击一下电源键,能够不用点击直接解锁吗
三星手机的人脸识别解锁功能默认需要滑动或点击屏幕来解锁。这是为了增强安全性,防止误解锁的情况。如果希望在检测到人脸后直接进入主界面,可以通过以下设置调整: 打开设置: 进入三星手机的【设置】应用。 进入生物识别和安全&a…...
Frida使用指南(三)- Frida-Native-Hook
1.Process、Module、Memory基础 1.Process Process 对象代表当前被Hook的进程,能获取进程的信息,枚举模块,枚举范围等 2.Module Module 对象代表一个加载到进程的模块(例如,在 Windows 上的 DLL,或在 Linux/Android 上的 .so 文件), 能查询模块的信息,如模块的基址、名…...
网络安全 | F5-Attack Signatures-Set详解
关注:CodingTechWork 创建和分配攻击签名集 可以通过两种方式创建攻击签名集:使用过滤器或手动选择要包含的签名。 基于过滤器的签名集仅基于在签名过滤器中定义的标准。基于过滤器的签名集的优点在于,可以专注于定义用户感兴趣的攻击签名…...
004 mybatis基础应用之全局配置文件
文章目录 配置内容properties标签typeAlias标签mappers标签 配置内容 SqlMapConfig.xml中配置的内容和顺序如下: properties(属性) settings(全局配置参数) typeAliases(类型别名) typeHandler…...
【岛屿个数——BFS / DFS,“外海”】
题目 推荐阅读 AcWing 4959. 岛屿个数(两种解法,通俗解释) - AcWing 1.岛屿个数 - 蓝桥云课 (lanqiao.cn) 代码 #include <bits/stdc.h> using namespace std; #define x first #define y second int dx4[4] {-1, 0, 1, 0}, dy4[4] …...
MySQL常用数据类型和表的操作
文章目录 (一)常用数据类型1.数值类2.字符串类型3.二进制类型4.日期类型 (二)表的操作1查看指定库中所有表2.创建表3.查看表结构和查看表的创建语句4.修改表5.删除表 (三)总代码 (一)常用数据类型 1.数值类 BIT([M]) 大小:bit M表示每个数的位数,取值范围为1~64,若…...
2025_1_27 C语言内存,递归,汉诺塔问题
1.c程序在内存中的布局 代码段(Code Segment) 位置:通常位于内存的最低地址。 用途:存储程序的可执行指令。 特点:只读,防止程序运行时被修改。数据段(Data Segment) 位置…...
开源音乐管理软件Melody
本文软件由网友 heqiusheng 推荐。不过好像已经是一年前了 😂 简介 什么是 Melody ? Melody 是你的音乐精灵,旨在帮助你更好地管理音乐。目前的主要能力是帮助你将喜欢的歌曲或者音频上传到音乐平台的云盘。 主要功能包括: 歌曲…...
Nginx开发01:基础配置
一、下载和启动 1.下载、使用命令行启动:Web开发:web服务器-Nginx的基础介绍(含AI文稿)_nginx作为web服务器,可以承担哪些基本任务-CSDN博客 注意:我配置的端口是81 2.测试连接是否正常 访问Welcome to nginx! 如果…...
【TCP 协议】确认应答机制 超时重传 三次握手 四次挥手
TCP报文首部 确认应答机制 TCP 是可靠的,指的是它能够确保数据从源端准确无误地传输到目的端。 当客户端和服务器通信时,客户端向服务器发送报文,那么,客户端怎么知道服务器已经收到报文了呢? 服务器收到客户端发的报…...
jenkins-k8s pod方式动态生成slave节点
一. 简述: 使用 Jenkins 和 Kubernetes (k8s) 动态生成 Slave 节点是一种高效且灵活的方式来管理 CI/CD 流水线。通过这种方式,Jenkins 可以根据需要在 Kubernetes 集群中创建和销毁 Pod 来执行任务,从而充分利用集群资源并实现更好的隔离性…...
基于vue和elementui的简易课表
本文参考基于vue和elementui的课程表_vue实现类似课程表的周会议列表-CSDN博客,原程序在vue3.5.13版本下不能运行,修改两处: 1)slot-cope改为v-slot 2)return background-color:rgb(24 144 255 / 80%);color: #fff; …...
可用的IPv6公共DNS(2025年1月更新)
境内IPv6 DNS: 1. 腾讯DNS:2402:4e00:: 2. 阿里DNS:2400:3200::1、2400:3200:baba::1 3. ISP(电信服务运营商)的IPv6 DNS,请以各ISP实际下发的为准,或拨打10000、10010、10086等号码询问人工…...
c高级复习
c高级复习...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
BLEU评分:机器翻译质量评估的黄金标准
BLEU评分:机器翻译质量评估的黄金标准 1. 引言 在自然语言处理(NLP)领域,衡量一个机器翻译模型的性能至关重要。BLEU (Bilingual Evaluation Understudy) 作为一种自动化评估指标,自2002年由IBM的Kishore Papineni等人提出以来,…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
