专栏首页后端技术880.Decoded String at Index

880.Decoded String at Index

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--;
            }
        }
        
        
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • EX2: 用CImg改写canny算法 EX2

    主要在于double newValue = (r * 0.2126 + g * 0.7152 + b * 0.0722);这句话,把每个点转为灰色

    平凡的学生族
  • 设置壁纸 适应各种分辨率 center-crop 适度裁剪

    参考stackoverflow上的android-wallpapermanager-crops-image 依旧是无效的,图片没失真,但屏幕的留白太多。如图3...

    平凡的学生族
  • Ex1:图像读取和显示以及像素操作

    dev下搭建环境,详情见https://www.jianshu.com/p/d5e18b9b0333

    平凡的学生族
  • android简单自定义View实现五子棋

    本文实例为大家分享了android自定义View实现五子棋的具体代码,供大家参考,具体内容如下

    砸漏
  • 55. 比较字符串

    比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母 样例 给出 A = "ABCD" B = "ACD",返回 tru...

    和蔼的zhxing
  • C语言中size_t和size_type 的区别

    1)size_tsize_t是用于数组的下标值类型,也可以用来“接收”sizeof操作符的返回值。

    ccf19881030
  • [开发技巧]·AdaptivePooling与Max/AvgPooling相互转换

    自适应池化Adaptive Pooling是PyTorch的一种池化层,根据1D,2D,3D以及Max与Avg可分为六种形式。

    小宋是呢
  • 短视频商城源码,制作彩色验证码

    yunbaokeji柯基
  • C 库函数 - fread()

    C 库函数 size_t fread(void *ptr, size_t size, size_t nmemb, FILE *stream) 从给定流 stre...

    心跳包
  • 递归与分治之棋盘覆盖问题

    在一个2^k * 2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘。 显然特殊方格在棋盘上出现的位置有4^...

    欠扁的小篮子

扫码关注云+社区

领取腾讯云代金券