AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

LeetCode 880. Decoded String at Index    原题链接    中等

作者: 作者的头像   wzc1995 ,  2019-01-15 04:24:59 ,  所有人可见 ,  阅读 1524


2


1

题目描述

给定一个编码字符串 S。为了找出 解码 字符串并将其写入磁带,从编码字符串中每次读取一个字符,并采取以下步骤:

  • 如果所读的字符是字母,则将该字母写在磁带上。
  • 如果所读的字符是数字(例如 d),则整个当前磁带总共会被重复写 d-1 次。

现在,对于给定的编码字符串 S 和索引 K,查找并返回解码字符串中的第 K 个字母。

样例

输入:S = "leet2code3", K = 10
输出:"o"
解释:
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。
输入:S = "ha22", K = 5
输出:"h"
解释:
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
输入:S = "a2345678999999999999999", K = 1
输出:"a"
解释:
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。

注意

  • 2 <= S.length <= 100
  • S 只包含小写字母与数字 2 到 9 。
  • S 以字母开头。
  • 1 <= K <= 10^9
  • 解码后的字符串保证少于 2^63 个字母。

算法

(回溯) $O(n)$
  1. 首先计算出解码后的字符串的长度 len。
  2. 然后倒序遍历字符:(1) 当前字符为小写字母,若 K == len,则说明当前字母就是索引 K,直接返回;否则 len 自减 1。(2) 当前字符为数字,则先将 len = len / S[i],找到重复之前的长度。若 K % len == 0,则说明索引 K 是循环节的最后一个字母,则直接从 i 开始向前找到第一个字母并返回即可。否则,K = K % len。

时间复杂度

  • 计算长度的只需要遍历一遍,倒序找答案也最多只需要遍历一次,故总时间复杂为 $O(n)$。

空间复杂度

  • 仅使用的常数的额外空间,故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    #define LL long long
    string decodeAtIndex(string S, int K) {
        int n = S.length();
        LL len = 0;
        for (auto &c : S) {
            if (isalpha(c))
                len++;
            else
                len *= c - '0';
        }

        for (int i = n - 1; i >= 0; i--) {
            if (isalpha(S[i])) {
                if (K == len)
                    return S.substr(i, 1);
                len--;
            }
            else {
                len /= S[i] - '0';
                if (K % len == 0) {
                    for (int j = i - 1; j >= 0; j--)
                        if (isalpha(S[j]))
                            return S.substr(j, 1);
                }
                K %= len;
            }
        }

        return "";
    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息