- 索引处的解码字符串
给定一个编码字符串 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”
Java代码：
class Solution {
public String decodeAtIndex(String s, int k) {
long cnt = 0;
int i = 0;
for (; i < s.length(); i++) {
cnt = Character.isDigit(s.charAt(i)) ? cnt*(s.charAt(i)-'0') : cnt+1;
}
for (i--; i >= 0; i--) {
if (Character.isDigit(s.charAt(i))) {
cnt /= (s.charAt(i)-'0');
k %= cnt;
} else {
if (k % cnt == 0) return s.charAt(i)+"";
cnt--;
}
}
return "";
}
}
C代码：
#define STK_SIZE 1000
typedef long long ll_t;
typedef struct _info_st
{
ll_t sum;
ll_t mul;
ll_t rem;
}info_st;
info_st stk[STK_SIZE];
char ss[100][100];
void my_str_cpy(char *d, char *s, int len)
{
for(int i = 0; i < len; i++)
{
d[i] = s[i];
}
d[len] = ' ';
}
char res[2] ={0};
// 【算法思路】栈。根据计算特点为分层结构，使用栈表示，栈元素表示：此层总数，上层的倍数，余数
// 判断k属于余数，则在余数字串中查找；
// 判断k属于倍数，则将K对倍数求余，转化到上一层求解。
// 逐层递推得到结果
char * decodeAtIndex(char * S, int K){
int slen = strlen(S);
//双指针将S拆解为字符串数组，作为各层的余数字串，同时获得栈结构
int ll = 0, rr = 0;
int level = 0;
ll_t mul = 0;
ll_t last_sum = 0;
while(rr < slen)
{
if(S[rr] >= 'a' && S[rr] <= 'z')
{
rr++;
continue;
}
my_str_cpy(ss[level], &S[ll], rr - ll);
stk[level].rem = rr - ll;
stk[level].mul = mul;
stk[level].sum = last_sum;
//记录本层长度，供下层使用
last_sum = last_sum * mul + rr - ll;
mul = S[rr] - '0';
level++;
rr++;
ll = rr;
}
//处理最后一层
my_str_cpy(ss[level], &S[ll], rr - ll);
stk[level].rem = rr - ll;
stk[level].mul = mul;
stk[level].sum = last_sum;
level++;
//根据栈结构进行推算
while(level > 0)
{
//printf("level = %d, K = %dn", level, K);
if(stk[level - 1].rem > 0 && stk[level - 1].sum * stk[level - 1].mul < K)
{
K -= stk[level - 1].sum * stk[level - 1].mul;
//printf("K = %dn", K);
res[0] = ss[level - 1][K - 1];
return res;
}
K = (K > stk[level - 1].sum * stk[level - 1].mul)? (K - stk[level - 1].rem - 1) % stk[level - 1].sum + 1 : (K - 1) % stk[level - 1].sum + 1;
level--;
}
return " ";
}
python3代码：
class Solution:
def decodeAtIndex(self, S: str, K: int) -> str:
stack = []
n = 0
while True:
for t in S:
if t.isalpha():
stack.append(t)
n = n + 1
if n == K:
return t
else:
stack.append(n)
c = int(t)
n = n * c
stack.append(n)
#print(stack)
if K <= n:
print("n = ", n)
print("K = ", K)
stack.pop()
K = K % stack[-1]
if K == 0:
K = stack[-1]
stack = []
n = 0
#print("len(stack) = ", len(stack))
break
作者：KJ.JK
本文仅用于交流学习，未经作者允许，禁止转载，更勿做其他用途，违者必究。
文章对你有所帮助的话，欢迎给个赞或者 star，你的支持是对作者最大的鼓励，不足之处可以在评论区多多指正，交流学习
