880. 索引处的解码字符串

880. 索引处的解码字符串

给定一个编码字符串 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”。

int re;
int kt;

void f(char * s,int end,int epo){
    

    
            while(epo&&kt!=0){
    
                int j=0;
                while(j!=end&&kt!=0){
    
                     if(s[j]>='a'&&s[j]<='z'){
    
                         
                           kt--;
                          //printf("--%c %d ",s[j],kt);
                           if(kt==0){
    
                               s[j+1]='\0';
                                re=j;
                             }
                         }
                         else{
    
                             
                             f(s,j,s[j]-'0'-1);
                         }
                         

                    j++;

                }

                epo--;
            }

      

}

char * decodeAtIndex(char * s, int k){
    
    int i=0;
    kt=k;
    re=0;
  
 
 
     f(s,strlen(s),1);
     return s+re;
    // while(s[i]!='\0'){
    
    
        
    // if(s[i]>='a'&&s[i]<='z'){
    
    // k--;
    // printf("--%c %d",s[i],k);
    // if(k==0){
    
    // s[i+1]='\0';
    // return s+i;
    // }
    // }
    // else{
    
    // int epo=s[i]-'0'-1;
    // int end=i;
    // while(epo){
    
    // int j=0;
    // while(j!=i){
    
    // if(s[j]>='a'&&s[j]<='z'){
    
                         
    // k--;
    // printf("%c %d ",s[j],k,j);
    // if(k==0){
    
    // s[j+1]='\0';
    // return s+j;
    // }
    // }
                         

    // j++;

    // }

    // epo--;
    // }

    // }
    // i++;

// }

return 'a';
}

这还有一种比较厉害的算法，从后面开始计算非常棒：

// 逆向处理

char * decodeAtIndex(char * S, int K)
{
    
    if (S == NULL || strlen(S) == 0 || K < 1) {
    
        return NULL;
    }

    char* result = (char*)malloc(2 * sizeof(char));
    if (result != NULL) {
    
        memset(result, 0, 2 * sizeof(char));
    }

    int len = strlen(S);
    long strSize = 0;

    // 1. 计算展开后字符串长度
    for (int i = 0; i < len; i++) {
    
        char c = S[i];
        if (isalpha(c)) {
    
            strSize++;
            continue;
        }

        if (isdigit(c)) {
    
            strSize = strSize * (c - '0');
        }
    }

    if (K > strSize) {
    
        return NULL;
    }

    // 2. 从后处理
    for (int i = len - 1; i >= 0; i--) {
    
        K = K % strSize;
        if (K == 0 && isalpha(S[i])) {
    
		    result[0] = S[i];
            result[1] = '\0';
            return result;
        }

	    if (isdigit(S[i])) {
    
		    strSize /= S[i] - '0';
        } else {
    
		    strSize--;
        }
    }

    return NULL;
}