首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >880.Decoded String at Index

880.Decoded String at Index

作者头像
平凡的学生族
发布2019-05-25 09:57:16
3260
发布2019-05-25 09:57:16
举报
文章被收录于专栏:后端技术后端技术

880.Decoded String at Index

思路 用size表示在i处,字符串进行解码后的长度。 如果有一个解码后的字符串为appleappleappleappleappleapple,且K=24,那么答案相当于在字符串apple中求K = 4的字符。即size=26,K=24的问题可转化为size=5,K=4的问题。 利用这一点可以先找到刚好size>=K的位置,再反向遍历S,不断化简问题,最后求得答案。

代码

class Solution {
public:
    string decodeAtIndex(string S, int K) {
        long size = 0; // 要用long,如果用int会数据溢出
        int i = 0;
        for (i = 0; i < S.size(); i++) {
            if (!isdigit(S[i])) 
                size++;
            else
                size *= S[i] - '0';
        
            if (size >= K)
                break;
        }
        
        if (i == S.size()) // for循环时要注意越界问题
            i = S.size() - 1;
        
        for (int j = i; j >= 0; j--) { // 从后向前
            if (isdigit(S[j])) { // 等价问题转化
                size /= S[j] - '0';
                K %= size;
            }
            else {
                if (size == K || K == 0) // 刚好最后一个字符就是答案
                    return (string)"" + S[j];
                else // 最后一个字符不是答案
                    size--;
            }
        }
        
        
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.09.16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 880.Decoded String at Index
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档