880. 索引处的解码字符串

880. 索引处的解码字符串

给定一个编码字符串 S。请你找出 解码字符串 并将其写入磁带。解码时，从编码字符串中 每次读取一个字符 ，并采取以下步骤：

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

现在，对于给定的编码字符串 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';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

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

// 逆向处理

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53