880.Decoded String at Index
思路
用size表示在i处，字符串进行解码后的长度。
如果有一个解码后的字符串为appleappleappleappleappleapple，且K=24，那么答案相当于在字符串apple中求K = 4的字符。即size=26,K=24的问题可转化为size=5，K=4的问题。
利用这一点可以先找到刚好size>=K的位置，再反向遍历S，不断化简问题，最后求得答案。
代码
class Solution {
public:
string decodeAtIndex(string S, int K) {
long size = 0; // 要用long，如果用int会数据溢出
int i = 0;
for (i = 0; i < S.size(); i++) {
if (!isdigit(S[i]))
size++;
else
size *= S[i] - '0';
if (size >= K)
break;
}
if (i == S.size()) // for循环时要注意越界问题
i = S.size() - 1;
for (int j = i; j >= 0; j--) { // 从后向前
if (isdigit(S[j])) { // 等价问题转化
size /= S[j] - '0';
K %= size;
}
else {
if (size == K || K == 0) // 刚好最后一个字符就是答案
return (string)"" + S[j];
else // 最后一个字符不是答案
size--;
}
}
}
};
