Leetcode(884)-索引处的解码字符串
2024-09-01 02:58:15
给定一个编码字符串 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 <= 10^9
- 解码后的字符串保证少于
2^63
个字母。
思路:一开始的思路,是遍历字符串,如果是字母,就加到另外一个字符串上,如果是数字,就重复n-1次,当个数大于K时,就返回第K个字符,但是这种做法超时。这也应该是为什么难度是中等的原因吧。
上述的做法,还是要一个个遍历一个个的加字符,复杂度可想而知,无法满足题目的要求。
所以我们只能从下标考虑,就是我只记录我的索引,不涉及真正的字符串的空间,因为字符的操作是有规律的,只要找到其中的规律,我们就可以只通过索引来确定最终字符串的某个字符。
首先我们也是要一个个遍历,如果是字母,就将索引+1,如果碰到数字,就将这个索引乘以这个数字,当然同时要判断,索引与K的关系。如果索引小于K,就一直遍历下去,如果大于等于K,那么就不用了,这个时候我们可以找到第K个元素了。
这个时候要将索引往回退,如果是数字,就要除以这个数字,变成单倍数的字符串,相应的,第K个也要变成单倍数的
string decodeAtIndex(string S, int K)
{
long cur=0;
int i;
for(i=0;cur<K;++i)
{
if(isdigit(S[i]))
cur=cur*(S[i]-'0');
else
cur++;
}
while(i--)
{
if(isdigit(S[i]))
{
cur=cur/(S[i]-'0');
K=K%cur;
}
else if(K%(cur--)==0)
{
return string(1,S[i]);
}
}
}
最新文章
- 1Z0-053 争议题目解析694
- [No000085]C#反射Demo,通过类名(String)创建类实例,通过方法名(String)调用方法
- crawler4j 学习
- IIS配置php运行环境默认加载的php.ini路径
- Oracle 11g导入导出命令
- ecshop session机制
- pptp建立vpn
- 【转载】图解:二叉搜索树算法(BST)
- POJ C程序设计进阶 编程题#2:字符串中次数第2多的字母
- java实现附件预览(openoffice+swfTools+FlexPaper) (转载)
- 【杭州图铭科技有限公司招募贴】——“JUST DO IT”
- VS2010+Visual Assist X
- Ngnix技术研究系列2-基于Redis实现动态路由
- F# 之旅(下)
- 日志学习系列(三)——NLog基础知识
- C# Timer 定时任务
- Zynq系列程序逻辑固化方法
- 自学python 4.
- 【小玩意】time-passing-by clock
- 1173 - The Vindictive Coach
热门文章
- JavaSE 基础知识(常识概念 + 基础语法)问答总结/面试题 —— 讲给应届生的 Java 开源知识项目
- ROS教程(一):ROS安装教程(详细图文)
- Ubuntu14.04系统安装
- 报错:java.lang.ClassNotFoundException: io.opentracing.util.GlobalTracer
- 对话 CTO〡用声音在一起,听荔枝 CTO 丁宁聊 UGC 声音互动平台的技术世界 原创 王颖奇 极客公园 2018-12-01
- (001)每日SQL学习:关于UNION的使用
- DDD领域驱动设计:仓储
- Docker是如何实现隔离的
- Java中Socket的用法
- Docker (error getsockopt: connection refused ,使用http无法使用 docker login 登录的问题)