880索引处地解码字符串

我按照字符串解码的思路，超时了

class Solution {
public:
 string decodeAtIndex(string S, int K) {
        string res;
        string temp;
        stack<string>stk;
        for(auto c:S)
        {
            if(isalpha(c))
            {
                res+=c;
            } else if(isdigit(c))
            {
                stk.push(res);
                int cnt = c-'0';
                for(int i = 0;i<cnt-1;i++){
                    stk.top()+=res;
                }
                res = stk.top();
                stk.top();
            }
            if(res.size()>=K)
            {
               return string(1,res[K-1]);
            }
        }
        if(res.size()<K)
        {
            return string(1,res[K%S.size()-1]);
        }
        return "";
    }
};

注意，题目要求返回字符串，但这个字符串只有一个字母，所以用string封装的方法string(1,res[k-1])意思是返回n个res[k-1]处的字符组成的字符串

394字符串解码

class Solution {
public:
    map<long long,long long> rec;//记录每个下标对应的长度
    long long len,cnt;
    string res;//记录走过的路径
    string decodeAtIndex(string s, int k) {
        for(int i=0;i<s.length();i++) {
            if(isalpha(s[i])) {
                res.push_back(s[i]);
                len++;//len表示当前长度
                rec[i] = len; 
                if(len==k) return string(1,s[i]);//如果长度正好为k直接返回字母
            }else {
                cnt = len * (s[i]-'0');//翻s[i]倍后的长度
                if(cnt<k) {//翻s[i]倍后的当前长度没有到达k
                    res.push_back(s[i]);
                    rec[i] = len = cnt;
                }else {//翻s[i]倍后的当前长度大于等于k时即可回溯查找
                    cnt = k%len;
                    if(!cnt) cnt = len;
                    i--;
                    while(i>=0&&rec[i]!=cnt) {
                        if(isdigit(res[i])) {
                           cnt %= rec[i-1];
                           if(!cnt) cnt = rec[i-1];
                        }
                        i--;
                    }
                    while(i>=0&&isdigit(res[i])) i--;
                    return string(1,res[i]);
                }
            }
        }
        return "";
    }
};

class Solution {
public:
    string decodeAtIndex(string S, int K) {
        int num = 0, i = 0;
        string ans="";
        char x;
        while(i<S.length())
        {
            if(S[i]>='0' && S[i]<='9')
            {
                if ((S[i]-'0') < K*1.0/num)
                {
                    num *= (S[i]-'0');
                }
                else
                {
                    K %= num;
                    if (K == 0)
                    {
                        ans += x;
                        return ans;
                    }
                    num = 0;
                    i = 0;
                    continue;
                }
            }
            else
            {
                num++;
                x = S[i];
                if(num == K)
                {
                    ans+=S[i];
                    return ans;
                }
            }
            i++;
        }
        return ans;

    }
};